Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge (u, v), vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG. The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no incoming edges).

Algorithm 1

  1. Identify vertices that have no incoming edge (in-degree is 0).
  2. Delete this vertex of in-degree 0 and all its outgoing edges from the graph, place it in the output.
  3. Repeat 1 and 2 until graph is empty.

We can store each vertex’s in-degree in an array. While there are vertices remaining in the array, find one with in-degree zero and output it, and reduce in-degrees of all vertices adjacent to it by 1, and then delete the vertex (or mark its in-degree to -1).

Time complexity:

  • Initialize in-degree array: \(O(E)\);
  • Find vertex with in-degree 0: \(O(V)\) to search for one. It performs \(V\) times for a total of \(O(V^2)\).
  • Reduce in-degree of all vertices adjacent to a vertex: \(O(E)\);
  • Output and mark vertex: \(O(V)\)

For a total of \(O(V^2 + E)\). To improve the time complexity, we can memorize the vertices with in-degree of 0 in a queue or stack while decrementing in-degrees of adjacent vertices. This way we can reduce the time complexity to \(O(V + E)\).

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
      self.graph = defaultdict(list) #dictionary containing adjacency List
      self.V = vertices #No. of vertices
      self.in_degree = [0] * self.V

    # function to add an edge to graph
    def addEdge(self, u, v):
        self.graph[u].append(v)
        self.in_degree[v] += 1

    def topologicalSort(self):
        stack = [v for v, d in enumerate(self.in_degree) if d == 0]
        while len(stack) > 0:
          v = stack.pop()
          print(v)
          self.in_degree[v] = -1
          for w in self.graph[v]:
            self.in_degree[w] -= 1
            if self.in_degree[w] == 0:
              stack.append(w)

Topological Sorting via Depth First Search (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. 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.

Implementation

This implementation assumes the input graph is DAG, otherwise it will not work. It can be fixed by having two marks: one temporary and one permanent. If a node is marked as temporarily visited and is visited again, it means the graph is not DAG.

#Python program to print topological sorting of a DAG
from collections import defaultdict

#Class to represent a graph
class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list) #dictionary containing adjacency List
        self.V = vertices #No. of vertices

    # function to add an edge to graph
    def addEdge(self, u, v):
        self.graph[u].append(v)

    # A recursive function used by topologicalSort
    def topologicalSortUtil(self, v, visited, stack):

        # Mark the current node as visited.
        visited[v] = True

        # Recur for all the vertices adjacent to this vertex
        for i in self.graph[v]:
            if visited[i] == False:
                self.topologicalSortUtil(i, visited, stack)

        # Push current vertex to stack which stores result
        stack.append(v)

    # The function to do Topological Sort. It uses recursive
    # topologicalSortUtil()
    def topologicalSort(self):
        # Mark all the vertices as not visited
        visited = [False] * self.V
        stack =[]

        # Call the recursive helper function to store Topological
        # Sort starting from all vertices one by one
        for i in range(self.V):
            if visited[i] == False:
                self.topologicalSortUtil(i, visited, stack)

        # Print contents of the stack
        print(stack[::-1])