Topological sorting Algorithm.

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.

Topological Sorting Algorithm.


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]





See also related topics: