1. from typing import Any, Optional, List, Dict, Callable
2.  
3.  
4. class Vertex:
5.     def __init__(self, data, index):
6.         self.data = data  # wartosc
7.         self.index = index # index
8.  
9.  
10. # przechowuje krawedzie grafu
11. class Edge:
12.     source: Vertex  # od krawedzi
13.     destination: Vertex  # do krawedzi
14.     weight: Optional[float]  # opcjonalna waga krawedzi
15.  
16.     def __init__(self, source, destination, weight):
17.         self.source = source
18.         self.destination = destination
19.         self.weight = weight
20.  
21.  
22. class Graph:
23.     adjacencies: Dict[Vertex, List[Edge]]
24.  
25.     def __init__(self) -> None:
26.         self.adjacencies = {}
27.  
28.     def create_vertex(self, data: Any) -> Vertex:
29.         temp: Vertex = Vertex(data, len(self.adjacencies))
30.         self.adjacencies[temp] = []
31.         return temp
32.  
33.     def add_undirected_edge(self, source: Vertex, destination: Vertex, weight: Optional[float] = None) -> None:
34.         new_edge = Edge(source, destination, weight)
35.         new_edge_revers = Edge(destination, source, weight)
36.         self.adjacencies[source].append(new_edge)
37.         self.adjacencies[destination].append(new_edge_revers)
38.  
39.     def add_directed_edge(self, source, destination, weight=None):
40.         new_edge = Edge(source, destination, weight)
41.         self.adjacencies[source].append(new_edge)
42.  
43.     def print(self):
44.         for vertex_edges in self.adjacencies.values():
45.             source = list(self.adjacencies.keys())[list(self.adjacencies.values()).index(vertex_edges)]
46.             print(f"{source.data} -> ", end='')
47.             print("[", end='')
48.             for edge in vertex_edges:
49.                 print(f"{edge.destination.data}, ", end='')
50.             print("]")
51. def dead_path(g: Graph, cross_id: Any, visit: Callable[[Any], None]) -> Optional[List[Vertex]]:
52.     vertex = None
53.     for elem in list(graph.adjacencies.keys()):
54.         if elem.data == cross_id:
55.             vertex = elem
56.     path: List[List[Vertex]] = [[]]
57.     road: List[Vertex] = []
58.     recursion(g, path, vertex, vertex, [], road, visit)
59.     return path
60.  
61.  
62. def recursion(g: Graph, path, begin, v: Vertex, visited: List[Vertex], road, visit: Callable[[Any], None]) -> None:
63.     visited.append(v)
64.     if g.adjacencies[v]:
65.         road.append(v)
66.     for elem in g.adjacencies[v]:
67.         if elem.destination == begin and not path[0]:
68.             path[0] = road.copy()
69.             path[0].append(begin)
70.         if elem.destination not in visited:
71.             recursion(g, path, begin, elem.destination, visited, road, visit)
72.  
73.  
74. def visit(node: Vertex):
75.     print(node.data)
76.  
77.  
78. if __name__ == '__main__':
79.  
80.     graph = Graph()
81.     a = graph.create_vertex("A")
82.     b = graph.create_vertex("B")
83.     c = graph.create_vertex("C")
84.  
85.     d = graph.create_vertex("D")
86.     e = graph.create_vertex("E")
87.  
88.     graph.add_directed_edge(a, b)
89.     graph.add_directed_edge(b, c)
90.     graph.add_directed_edge(c, d)
91.     graph.add_directed_edge(d, e)
92.     graph.add_directed_edge(e, a)
93.     graph.print()
94.  
95.     path = dead_path(graph, "A", visit)
96.     for elem in path[0]:
97.         print(elem.data)