Topological Sorting (위상 정렬)

Topological sorting for Directed Acyclic Graph(DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

Topological Sorting vs Depth First Traversal (DFS)

In DFS, we print a vertex and then recursively call DFS for its adjacent vertices. In topological sorting, we need to print a vertex before its adjacent vertices.

Ex) In the given graph, the vertex '5' should be printed before vertex '0', but unlike DFS, the vertex '4' should also be printed before vertex '0'. So Topological sorting is different from DFS.

A DFS of the shown graph is "5 2 3 1 0 4", but it is not a topological sorting.

Algorithm to find Topological Sorting

We can modify DFS to find Topological Sorting of a graph. In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack. We don't print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack.

Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.

from collections import defaultdict
 
class Graph :
    def __init__(self, vertices) :
        self.graph = defaultdict(list)
        self.V = vertices
    
    def addEdge(self, u, v):
        self.graph[u].append(v)
    
    def helper(self, v, visited, stack) :
 
        visited[v] = True
 
        for i in self.graph[v] :
            if visited[i] == False :
                self.helper(i, visited, stack)
 
        stack.append(v)
 
    def topologicalSort(self) :
 
        visited = [False]*self.V
        stack = []
 
        for i in range(self.V) :
            if visited[i] == False:
                self.helper(i, visited, stack)
 
        while stack:
            print(stack.pop())

Time Complexity

The above algorithm is simply DFS with an extra stack. So time complexity is same as DFS which is O(V+E).

References:

https://www.geeksforgeeks.org/topological-sorting/