Kahn's Algorithm

Kahn's algorithm is used to find a topological ordering of a directed acyclic graph (DAG).

Introduction

Kahn’s Algorithm is a Breadth-First Search (BFS) based approach used to find a Topological Order of a Directed Acyclic Graph (DAG). Topological sorting of a DAG is a linear ordering of its vertices such that for every directed edge (u → v), vertex u appears before vertex v in the ordering.

How Kahn’s Algorithm Works?

1

Compute the indegree of each node.

  • Traverse the graph and count incoming edges for each node.
2

Initialize a Queue with Nodes Having Zero In-Degree.

3

Process the Nodes Using BFS

  • Remove a node from the queue and add it to the topological order.
  • Decrement the in-degree of its neighbor nodes.
  • If any node’s in-degree becomes zero, add it to the queue.
4

Termination

  • If all nodes are included in the result, a valid topological ordering exists.
  • If not, the graph contains a cycle, meaning topological sorting is not possible.

Indegree

Indegree of node in directed graph is the number of incoming edges to that node.

Example

Carousel image 1
Carousel image 2
Carousel image 3
Carousel image 4
Carousel image 5
Carousel image 6
Carousel image 7
Carousel image 8

Implementation of Kahn’s Algorithm

//kahn's.cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void kahns(vector<vector<int>>&adjlist,vector<int> &indegree){
queue<int> q;
for(int i=0;i<indegree.size();i++){
    if(indegree[i]==0){
        q.push(i);
    }
}
while(!q.empty()){
    int node=q.front();
    q.pop();
    cout<<node<<" ";
    for(int &v:adjlist[node]){
        indegree[v]--;
        if(indegree[v]==0){
            q.push(v);
        }
    }
}
}
int main()
{
int vertex, edge;
cin >> vertex >> edge;
vector<vector<int>> adjlist(vertex);
int u, v;
for (int i = 0; i < edge; i++)
{
    cin >> u >> v;
    adjlist[u].push_back(v);
}
vector<int> indegree(vertex);
for(int i=0;i<vertex;i++){
    for(int &v:adjlist[i]){
        indegree[v]++;
    }
}
kahns(adjlist,indegree);
}

Time Complexity

Computing in-degree: O(V + E)
Processing nodes using BFS: O(V + E)
Time Complexity: O(V + E)

Space Complexity

In-Degree Array: O(V)
Queue: O(V)
Space Complexity: O(V)