Topological Sort Using Kahn's Algorithm (BFS) - Visualization

Problem Statement❯

Topological Sort of a directed graph is a linear ordering of its vertices such that for every directed edge u → v, vertex u comes before v in the ordering.

Kahn’s Algorithm uses a BFS-based approach and is suitable for Directed Acyclic Graphs (DAGs). It efficiently produces a valid topological ordering or detects the presence of a cycle.

Examples❯

Graph (Edges) Topological Order Description
[[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]] [4, 5, 2, 3, 1, 0] Valid topological sort respecting all dependencies
[[0, 1], [1, 2], [2, 3]] [0, 1, 2, 3] Simple linear DAG
[] [] Empty graph has no vertices to sort
[[0, 1], [1, 0]] null Graph contains a cycle, so topological sort is not possible
[[1, 3], [2, 3], [3, 4]] [1, 2, 3, 4] Multiple valid orderings possible

Solution❯

Understanding the Problem

Topological Sort is used to linearly order the vertices of a Directed Acyclic Graph (DAG) such that for every directed edge u → v, vertex u comes before v in the order. This is often used in scheduling problems, like task execution order based on dependencies.

We will solve this using Kahn’s Algorithm, which uses a Breadth-First Search (BFS) approach based on indegree counts.

Step-by-Step Solution with Example

Step 1: Represent the Graph

We represent the graph using an adjacency list and also track the indegree (number of incoming edges) for each node.

Example: Given edges: [[5, 0], [4, 0], [5, 2], [2, 3], [3, 1], [4, 1]]

This means:

  • 5 → 0
  • 4 → 0
  • 5 → 2
  • 2 → 3
  • 3 → 1
  • 4 → 1

Step 2: Compute Indegrees

We loop over all edges and count how many edges point to each vertex.

After processing the above edges, indegrees would look like:


0: 2
1: 2
2: 1
3: 1
4: 0
5: 0

Step 3: Initialize Queue

We add all vertices with indegree 0 to a queue. These are the starting points because they have no dependencies.

Queue: [4, 5]

Step 4: BFS Traversal

While the queue is not empty:

  • Dequeue a node and add it to the result.
  • For each of its neighbors, reduce their indegree by 1.
  • If a neighbor’s indegree becomes 0, add it to the queue.

Progress:


Queue: [4, 5] → [5, 0] → [0, 2] → [2, 3] → [3, 1] → [1]
Result: [4, 5, 0, 2, 3, 1]

Step 5: Check for Cycles

If at the end, the result does not contain all nodes, it means a cycle exists and topological sort is not possible. If the size of the result equals the number of vertices, we have a valid topological order.

Edge Cases

Case 1: Empty Graph

If the graph has no vertices, return an empty list. No work to be done.

Case 2: Single Node with No Edges

The output is simply the node itself.

Case 3: Multiple Starting Nodes

When multiple nodes have indegree 0, the result may vary depending on which is dequeued first. All are valid topological orders.

Case 4: Cycle in Graph

If there's a cycle, like 1 → 2 → 3 → 1, no topological sort is possible. Our result will have fewer nodes than expected, indicating a cycle.

Finally

Kahn’s Algorithm is a simple yet powerful way to solve topological sorting using a queue and indegree tracking. It not only provides the topological order but also helps in detecting cycles in the graph. This is especially useful in real-life applications like course prerequisites, task scheduling, and build systems.

Algorithm Steps❯

  1. Compute the indegree of each vertex.
  2. Initialize a queue and enqueue all vertices with indegree 0.
  3. Initialize an empty list to store the topological order.
  4. While the queue is not empty:
    1. Dequeue a vertex u and add it to the result list.
    2. For each neighbor v of u:
      1. Decrease indegree[v] by 1.
      2. If indegree[v] == 0, enqueue v.
  5. If the result contains all vertices, return the result.
  6. Else, return null (cycle detected).

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>
#define MAX 100

void topologicalSortKahn(int V, int edges[][2], int E) {
    int indegree[MAX] = {0};
    int adj[MAX][MAX] = {0};
    int queue[MAX], front = 0, rear = 0;
    int result[MAX], idx = 0;

    for (int i = 0; i < E; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        adj[u][v] = 1;
        indegree[v]++;
    }

    for (int i = 0; i < V; i++) {
        if (indegree[i] == 0)
            queue[rear++] = i;
    }

    while (front < rear) {
        int node = queue[front++];
        result[idx++] = node;
        for (int i = 0; i < V; i++) {
            if (adj[node][i]) {
                indegree[i]--;
                if (indegree[i] == 0)
                    queue[rear++] = i;
            }
        }
    }

    if (idx != V) {
        printf("Cycle detected\n");
        return;
    }

    printf("Topological Sort: ");
    for (int i = 0; i < idx; i++)
        printf("%d ", result[i]);
    printf("\n");
}

int main() {
    int V = 6;
    int edges[][2] = {{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}};
    int E = sizeof(edges)/sizeof(edges[0]);
    topologicalSortKahn(V, edges, E);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(V + E)Even in the best case, we must visit all vertices and all edges once to compute indegrees and process the graph structure.
Average CaseO(V + E)For any valid DAG, each vertex and edge is processed exactly once.
Worst CaseO(V + E)Regardless of graph structure (as long as it is a DAG), we always have to check every node and every edge at least once.

Space Complexity❯

O(V + E)

Explanation: We use additional space for the adjacency list (O(E)), indegree array (O(V)), the queue (O(V)), and result list (O(V)).

Mallikarjuna Mallisetty, author
About the author

Mallikarjuna Mallisetty

General programming

Mallikarjuna shares practical programming tutorials and foundational concepts designed to help developers learn by building and experimenting.

View LinkedIn profile ↗