For topological sorting of graph the graph needs to be DAG (Directed Acyclic Graph).The topological sorting of DAG is the ordering of the vertices for edge uv, such that vertex u is placed before v in ordering.
from collections import defaultdict class Graph: def __init__(self,v): self.graph = defaultdict(list) self.V = v def append(self,u,v): self.graph[u].append(v) def sort_util(self,v,visited,ele_stack): visited[v] = True for ele in self.graph[v]: if visited[ele] == False: self.sort_util(ele,visited,ele_stack) ele_stack.insert(0,v) def topological_sort(self): visited = [False]*self.V ele_stack = for ele in range(self.V): if visited[ele] == False: self.sort_util(ele,visited,ele_stack) print(ele_stack) g = Graph(4) g.append(4,1); g.append(4,2); g.append(3,2); g.append(4,3); g.append(1,3); print("The Topological Sort is: ") g.topological_sort()
In the above code, we have followed below steps:
- Create an adjacency list containing the vertices and their associated node vertices.
- Create one list visited, with the vertices and there visited value as false.
- Now, we will focus on topological sorting. Visit the vertex(i) and mark is true in visited list and recur all its adjacent vertex. Append the current vertex to the result stack.
- Follow the above step for the vertex elements and return the stack from top to bottom.