Algorithm

geekquad · geekquad · commit 9efddebc2732 · 2020-09-29T19:23:42.000+05:30
diff --git a/python/sorting/topological_sort.py b/python/sorting/topological_sort.py
@@ -0,0 +1,59 @@
+#topological sort
+
+adjacent = {}
+Vertex = []
+parent = {}
+#stores the topological sort in reverse order.
+topological_sort = []
+
+def initalizeVertex():
+    n = int(input('Enter the no. of vertices.\n'))
+    print("Enter the vertexes.")
+    for i in range(n):
+        vertex = input()
+        Vertex.append(vertex)
+        adjacent[vertex] = []
+
+def initalizeDirectedEdges():
+    n = int(input("Enter the no. of edges.\n"))
+    print("Enter the space seperated edges.")
+    for i in range(n):
+        a,b = input().split()
+        adjacent[a].append(b)    
+
+def showVertex():
+    print('The vertexes are: ')
+    print(vertex)
+    print('\n')
+
+def showEdges():
+    print('The dictionary of edges are: ')
+    print(adjacent)
+    print('\n')
+
+def t_sort(s):
+    for neighbour in adjacent[s]:
+        if neighbour not in parent.keys():
+            parent[neighbour] = s
+            #stack.append(neighbour)
+            t_sort(neighbour)
+    topological_sort.append(s)      
+
+
+# Driver Code
+
+initalizeVertex()
+initalizeDirectedEdges()  
+#showVertex()
+#showEdges()
+print('Implementing Topological Sort.')
+#for a well connected grapgh, we don't need the below for loop.
+#dfs(starting_vertex) will give correct result.
+#the below for loop is used for unconnected graphs.
+for v in Vertex:
+    if v not in parent.keys():
+        parent[v] = None
+        t_sort(v)
+
+print('Topological sort order is: ')
+print(topological_sort[::-1])
