Topological sort use case.
In Computer Sciense a topological sort of a directed graph (Directed Acyclic Graph - DAG) is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. The method applicable for graphs that have no directed cycles - directed acyclic graphs. Topological sort is a graph bypassing mode in which each node v is visited only after all its dependencies are visited.
The typical use case of topological sorting is a tasks scheduling based on their relations. The Python code can be implemented in recursive and non-recursive way, below recursive code is presented.
Topological sorting Algorithm Python code:
from collections import defaultdict #Class for a graph class Graph: def __init__(self,vertices): self.graph = defaultdict(list) self.V = vertices # add an edge to graph def addEdge(self,u,v): self.graph[u].append(v) # A recursive function used by Main function def TopologicalSortUtil(self,v,visited,stack): visited[v] = True # adjacent vertices recursion for i in self.graph[v]: if visited[i] == False: self.TopologicalSortUtil(i,visited,stack) stack.insert(0,v) # Main function def TopologicalSort(self): visited = [False]*self.V stack = for i in range(self.V): if visited[i] == False: self.TopologicalSortUtil(i,visited,stack) print (stack) g = Graph(6) g.addEdge(2,0) g.addEdge(1,2) g.addEdge(5,3) g.addEdge(1,5) g.addEdge(3,4) g.addEdge(0,4) print ("Topological Sort:") g.TopologicalSort()
OUT: Topological Sort:
[1, 5, 3, 2, 0, 4]