forked from mission-peace/interview
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathtopologicalsort.py
More file actions
38 lines (29 loc) · 905 Bytes
/
topologicalsort.py
File metadata and controls
38 lines (29 loc) · 905 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#topological sort
# java code https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/TopologicalSort.java
from graph import Graph
def top_sort(graph):
stack = []
visited = set()
for vertex in graph.all_vertex.values():
if vertex in visited:
continue
top_sort_util(vertex, stack, visited)
return stack
def top_sort_util(vertex, stack, visited):
visited.add(vertex)
for adjacent in vertex.adjacent_vertices:
if adjacent in visited:
continue
top_sort_util(adjacent, stack, visited)
stack.append(vertex)
if __name__ == '__main__':
graph = Graph(True)
graph.add_edge(1,3)
graph.add_edge(1,2)
graph.add_edge(3,4)
graph.add_edge(5,6)
graph.add_edge(6,3)
graph.add_edge(3,8)
graph.add_edge(8,11)
stack = top_sort(graph)
print(stack[::-1])