Topological Sort Algorithm: Python, C++ Example

What is Topological Sort Algorithm?

Topological Sorting is also known as Kahn’s algorithm and is a popular Sorting Algorithm. Using a directed graph as input, Topological Sort sorts the nodes so that each appears before the one it points to.

This algorithm is applied on a DAG (Directed Acyclic Graph) so that each node appears in the ordered array before all other nodes that are pointed to by it. This algorithm follows some rules repeatedly until the sort is completed.

To simplify, look at the following example:

Directed Graph

Here, we can see that “A” has no indegree. Indegree means the edge that points to a node. “B” and “C” have a pre-requisite of “A”, then “E” has a pre-requisite of “D” and “F” nodes. Some of the nodes are dependent on other nodes.

Here is another representation of the above Graph:

Dependency of each node (Linear Ordering)

So, when we pass the DAG (Directed Acyclic Graph) to the topological sort, it will give us an array with linear ordering, where the first element has no dependency.

Here are the steps to do this:

Step 1) Find the node with zero incoming edges, a node with zero degrees.

Step 2) Store that zero in-degree node in a Queue or Stack and remove the node from the Graph.

Step 3) Then delete the outgoing edge from that node. This will decrement the in-degree count for the next node.

Topological ordering requires that the graph data structure will not have any cycle. A graph will be considered a DAG if it follows these requirements:

• One or more nodes with an indegree value of zero.
• The graph does not contain any cycle.

As long as there are nodes in the Graph and the Graph is still a DAG, we will run the above three steps. Otherwise, the algorithm will fall into the cyclic dependency, and Kahn’s Algorithm will not be able to find a node with zero in-degree.

How Topological Sort Works

Here, we will use “Kahn’s Algorithm” for the topological sort. Let us say we have the following Graph:

Here are the steps for Kahn’s Algorithm:

Step 1) Calculate the indegree or incoming edge of all nodes in the Graph.

Note:

• Indegree means the directed edges pointing to the node.
• Outdegree means the directed edges that come from a node.

Here is the indegree and outdegree of the above Graph:

Step 2) Find the node with zero indegrees or zero incoming edges. The node with zero indegree means no edges are coming toward that node. Node “A” has zero indegrees, meaning there is no edge pointing to node “A”. So, we will do the following actions:

• Remove this node and its outdegree edges (outgoing edges).
• Place the node in the Queue for ordering.
• Update the in-degree count of the neighbor node of “A”.

Step 3) We need to find a node with an indegree value of zero. In this example, “B” and “C” have zero indegree. Here, we can take either of these two. Let us take “B” and delete it from the Graph. Then update the indegree values of other nodes. After performing these operations, our Graph and Queue will look like the following:

Step 4) Node “C” has no incoming edge. So, we will remove node “C” from the Graph and push it into the Queue. We can also delete the edge that is outgoing from “C”. Now, our Graph will look like this:

Step 5) We can see that nodes “D” and “F” have the indegree of zero. We will take a node and put it in the Queue. Let us take out “D” first. Then the indegree count for node “E” will be 1. Now, there will be no node from D to E. We need to do the same for node “F”, and our result will be like the following:

Step 6) The indegree (ingoing edges) and outdegree (outgoing edges) of node “E” became zero. So, we have met all the pre-requisites for node “E”. Here, we will put “E” at the end of the Queue. So, we do not have any nodes left, and the algorithm ends here.

Pseudo Code for Topological Sorting

Here is the pseudo-code for the topological sort while using Kahn’s Algorithm.

function TopologicalSort( Graph G ):
  for each node in G:
    calculate the indegree
  start = Node with 0 indegree
  G.remove(start)
  topological_list = [start]
  while node with 0 indegree present:
    topological_list.append(node)
    G.remove(node)
    // Update indegree of present nodes
  return topological_list

Topological sort can also be implemented using the DFS (Depth First Search) method. However, that approach is the recursive method. Kahn’s algorithm is more efficient than the DFS approach.

C++ Implementation of Topological Sorting

#include<bits/stdc++.h>
using namespace std;
class graph{
  int vertices;
  list<int> *adjecentList;
public:
  graph(int vertices){
    this->vertices = vertices;
    adjecentList = new list<int>[vertices];
  }
  void createEdge(int u, int v){
    adjecentList[u].push_back(v);
  }
  void TopologicalSort(){
    // filling the vector with zero initially
    vector<int> indegree_count(vertices,0);

    for(int i=0;i<vertices;i++){
      list<int>::iterator itr;
      for(itr=adjecentList[i].begin(); itr!=adjecentList[i].end();itr++){
        indegree_count[*itr]++;
      }
    }
    queue<int> Q;
    for(int i=0; i<vertices;i++){
      if(indegree_count[i]==0){
        Q.push(i);
      }
    }
    int visited_node = 0;
    vector<int> order;
    while(!Q.empty()){
      int u = Q.front();
      Q.pop();
      order.push_back(u);

      list<int>::iterator itr;
      for(itr=adjecentList[u].begin(); itr!=adjecentList[u].end();itr++){
        if(--indegree_count[*itr]==0){
          Q.push(*itr);
        }
      }
      visited_node++;
    }
    if(visited_node!=vertices){
      cout<<"There's a cycle present in the Graph.\nGiven graph is not DAG"<<endl;
      return;
    }
    for(int i=0; i<order.size();i++){
      cout<<order[i]<<"\t";
    }
  }
};
int main(){
  graph G(6);
  G.createEdge(0,1);
  G.createEdge(0,2);
  G.createEdge(1,3);
  G.createEdge(1,5);
  G.createEdge(2,3);
  G.createEdge(2,5);
  G.createEdge(3,4);
  G.createEdge(5,4);
  G.TopologicalSort();
}

Output

0       1       2       3       5       4

Python Implementation of Topological Sorting

from collections import defaultdict
class graph:
    def __init__(self, vertices):
        self.adjacencyList = defaultdict(list)
        self.Vertices = vertices  # No. of vertices
    # function to add an edge to adjacencyList
    def createEdge(self, u, v):
        self.adjacencyList[u].append(v)
    # The function to do Topological Sort.
    def topologicalSort(self):
        total_indegree = [0]*(self.Vertices)
        for i in self.adjacencyList:
            for j in self.adjacencyList[i]:
                total_indegree[j] += 1
        queue = []
        for i in range(self.Vertices):
            if total_indegree[i] == 0:
                queue.append(i)
        visited_node = 0
        order = []
        while queue:
            u = queue.pop(0)
            order.append(u)
            for i in self.adjacencyList[u]:
                total_indegree[i] -= 1

                if total_indegree[i] == 0:
                    queue.append(i)
            visited_node += 1
        if visited_node != self.Vertices:
            print("There's a cycle present in the Graph.\nGiven graph is not DAG")
        else:
            print(order)
G = graph(6)
G.createEdge(0,1)
G.createEdge(0,2)
G.createEdge(1,3)
G.createEdge(1,5)
G.createEdge(2,3)
G.createEdge(2,5)
G.createEdge(3,4)
G.createEdge(5,4)
G.topologicalSort()

Output

[0, 1, 2, 3, 5, 4]

Cyclic Graphs of Topological Sort Algorithm

A graph containing a cycle cannot be topologically ordered, as the cyclic Graph has the dependency in a cyclic manner. For example, check this Graph:

This Graph is not a DAG (Directed Acyclic Graph) because A, B, and C create a cycle. If you notice, there is no node with zero in-degree value. According to Kahn’s Algorithm, if we analyze the above Graph:

• Find a node with zero indegrees (no incoming edges).
• Remove that node from the Graph and push it to the Queue. However, in the above Graph, there is no node with zero in-degrees. Every node has an in-degree value greater than 0.
• Return an empty queue, as it could not find any node with zero in-degrees.

We can detect cycles using the topological ordering with the following steps:

Step 1) Perform topological Sorting.

Step 2) Calculate the total number of elements in the topologically sorted list.

Step 3) If the number of elements equals the total number of vertices, then there is no cycle.

Step 4) If it is not equal to the number of vertices, then there is at least one cycle in the given graph data structure.

Complexity Analysis of Topological Sort

There are two types of complexity in algorithms. They are:

1. Time Complexity
2. Space Complexity

These complexities are represented with a function that provides a general complexity.

Time Complexity: All time complexity is the same for Topological Sorting. There are worst, average, and best-case scenarios for time complexity. The time complexity for topological Sorting is O(E + V), where E means the number of Edges in the Graph, and V means the number of vertices in the Graph.

Let us break through this complexity:

Step 1) At the beginning, we will calculate all the indegrees. To do that, we need to go through all the edges, and initially, we will assign all V vertex indegrees to zero. So, the incremental steps we complete will be O(V+E).

Step 2) We will find the node with zero indegree value. We need to search from the V number of the vertex. So, the steps completed will be O(V).

Step 3) For each node with zero indegrees, we will remove that node and decrement the indegree. Performing this operation for all the nodes will take O(E).

Step 4) Finally, we will check if there is any cycle or not. We will check whether the total number of elements in the sorted array is equal to the total number of nodes. It will take O(1).

So, these were the individual time complexities for each step of the topological Sorting or topological ordering. We can say that the time complexity from the above calculation will be O(V + E); here, O means the complexity function.

Space Complexity: We needed O(V) spaces for running the topological sorting algorithm. Here are the steps where we needed the space for the program:

• We had to calculate all the indegrees of nodes present in the Graph. As the Graph has a total of V nodes, we need to create an array of size V. So, the space required was O(V).
• A Queue data structure was used to store the node with zero indegree. We removed the nodes with zero indegree from the original Graph and placed them in the Queue. For this, the required space was O(V).
• The array is named “order”, which stored the nodes in topological order. That also required O(V) spaces.

These were the individual space complexities. So, we need to maximize these spaces in the run time. Space complexity stands for O(V), where V means the number of the vertex in the Graph.

Application of Topological Sort

There is a huge use for Topological Sorting. Here are some of them:

• It is used when an Operating system needs to perform the resource allocation.
• Finding a cycle in the Graph. We can validate if the Graph is a DAG or not with topological sort.
• Sentence ordering in the auto-completion apps.
• It is used for detecting deadlocks.
• Different types of Scheduling or course scheduling use the topological sort.
• Resolving dependencies. For example, if you try to install a package, that package might also need other packages. Topological ordering finds out all the necessary packages to install the current package.
• Linux uses the topological sort in the “apt” to check the dependency of the packages.

FAQs