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

Graphs

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

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)).


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...