Python-powered perfection: 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.
Topological Sorting Algorithm meme.

Python Knowledge Base: Make coding great again.
- Updated: 2024-07-23 by Andrey BRATUS, Senior Data Analyst.



    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.



  1. Topological sorting Algorithm Python code:


  2. 
    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()
    
  3. Topological sorting Algorithm code output:


  4. OUT: Topological Sort:
    [1, 5, 3, 2, 0, 4]





See also related topics: