Topological Sort using Kahn's Algorithm

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.

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.

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

#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;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void topologicalSortKahn(int V, vector<pair<int, int>> &edges) {
    vector<int> indegree(V, 0);
    vector<vector<int>> graph(V);
    for (auto &[u, v] : edges) {
        graph[u].push_back(v);
        indegree[v]++;
    }

    queue<int> q;
    for (int i = 0; i < V; ++i)
        if (indegree[i] == 0) q.push(i);

    vector<int> result;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        result.push_back(node);
        for (int neighbor : graph[node]) {
            if (--indegree[neighbor] == 0)
                q.push(neighbor);
        }
    }

    if (result.size() != V)
        cout << "Cycle detected" << endl;
    else {
        cout << "Topological Sort: ";
        for (int node : result) cout << node << " ";
        cout << endl;
    }
}

int main() {
    int V = 6;
    vector<pair<int, int>> edges = {{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}};
    topologicalSortKahn(V, edges);
    return 0;
}

from collections import deque, defaultdict

def topological_sort_kahn(V, edges):
    indegree = [0] * V
    graph = defaultdict(list)

    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque([i for i in range(V) if indegree[i] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    if len(result) == V:
        print("Topological Sort:", result)
    else:
        print("Cycle detected")

V = 6
edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]
topological_sort_kahn(V, edges)

import java.util.*;

public class TopologicalSortKahn {
    public static void main(String[] args) {
        int V = 6;
        int[][] edges = {{5,2}, {5,0}, {4,0}, {4,1}, {2,3}, {3,1}};
        topologicalSortKahn(V, edges);
    }

    public static void topologicalSortKahn(int V, int[][] edges) {
        int[] indegree = new int[V];
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < V; i++) graph.add(new ArrayList<>());

        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            indegree[edge[1]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < V; i++) if (indegree[i] == 0) queue.add(i);

        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result.add(node);
            for (int neighbor : graph.get(node)) {
                if (--indegree[neighbor] == 0)
                    queue.add(neighbor);
            }
        }

        if (result.size() != V)
            System.out.println("Cycle detected");
        else
            System.out.println("Topological Sort: " + result);
    }
}

function topologicalSortKahn(V, edges) {
  const indegree = Array(V).fill(0);
  const graph = Array.from({ length: V }, () => []);
  const result = [];

  for (const [u, v] of edges) {
    graph[u].push(v);
    indegree[v]++;
  }

  const queue = [];
  for (let i = 0; i < V; i++) {
    if (indegree[i] === 0) queue.push(i);
  }

  while (queue.length) {
    const node = queue.shift();
    result.push(node);
    for (const neighbor of graph[node]) {
      indegree[neighbor]--;
      if (indegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  console.log(result.length === V ? "Topological Sort: " + result : "Cycle detected");
}

const V = 6;
const edges = [[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]];
topologicalSortKahn(V, edges);

package main

import (
    "fmt"
)

func topologicalSortKahn(V int, edges [][2]int) {
    indegree := make([]int, V)
    graph := make([][]int, V)
    for _, e := range edges {
        u, v := e[0], e[1]
        graph[u] = append(graph[u], v)
        indegree[v]++
    }

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

    result := []int{}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        result = append(result, node)
        for _, neighbor := range graph[node] {
            indegree[neighbor]--
            if indegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }

    if len(result) != V {
        fmt.Println("Cycle detected")
    } else {
        fmt.Println("Topological Sort:", result)
    }
}

func main() {
    V := 6
    edges := [][2]int{{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}}
    topologicalSortKahn(V, edges)
}

use std::collections::VecDeque;

fn topological_sort_kahn(v: usize, edges: &[(usize, usize)]) {
    let mut indegree = vec![0; v];
    let mut graph = vec![vec![]; v];

    for &(u, w) in edges {
        graph[u].push(w);
        indegree[w] += 1;
    }

    let mut queue: VecDeque<usize> = (0..v).filter(|&i| indegree[i] == 0).collect();
    let mut result = vec![];

    while let Some(node) = queue.pop_front() {
        result.push(node);
        for &neighbor in &graph[node] {
            indegree[neighbor] -= 1;
            if indegree[neighbor] == 0 {
                queue.push_back(neighbor);
            }
        }
    }

    if result.len() == v {
        println!("Topological Sort: {:?}", result);
    } else {
        println!("Cycle detected");
    }
}

fn main() {
    let v = 6;
    let edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)];
    topological_sort_kahn(v, &edges);
}

fun topologicalSortKahn(V: Int, edges: List<Pair<Int, Int>>) {
    val indegree = IntArray(V)
    val graph = List(V) { mutableListOf<Int>() }

    for ((u, v) in edges) {
        graph[u].add(v)
        indegree[v]++
    }

    val queue = ArrayDeque<Int>()
    for (i in 0 until V) if (indegree[i] == 0) queue.add(i)

    val result = mutableListOf<Int>()
    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        result.add(node)
        for (neighbor in graph[node]) {
            indegree[neighbor]--
            if (indegree[neighbor] == 0) queue.add(neighbor)
        }
    }

    if (result.size != V)
        println("Cycle detected")
    else
        println("Topological Sort: $result")
}

fun main() {
    val V = 6
    val edges = listOf(5 to 2, 5 to 0, 4 to 0, 4 to 1, 2 to 3, 3 to 1)
    topologicalSortKahn(V, edges)
}

import Foundation

func topologicalSortKahn(_ V: Int, _ edges: [(Int, Int)]) {
    var indegree = [Int](repeating: 0, count: V)
    var graph = [[Int]](repeating: [], count: V)

    for (u, v) in edges {
        graph[u].append(v)
        indegree[v] += 1
    }

    var queue = [Int]()
    for i in 0..<V where indegree[i] == 0 {
        queue.append(i)
    }

    var result = [Int]()
    while !queue.isEmpty {
        let node = queue.removeFirst()
        result.append(node)
        for neighbor in graph[node] {
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0 {
                queue.append(neighbor)
            }
        }
    }

    if result.count != V {
        print("Cycle detected")
    } else {
        print("Topological Sort:", result)
    }
}

let V = 6
let edges = [(5,2), (5,0), (4,0), (4,1), (2,3), (3,1)]
topologicalSortKahn(V, edges)

function topologicalSortKahn(V: number, edges: [number, number][]): number[] | null {
  const indegree = Array(V).fill(0);
  const graph: number[][] = Array.from({ length: V }, () => []);
  const result: number[] = [];

  for (const [u, v] of edges) {
    graph[u].push(v);
    indegree[v]++;
  }

  const queue: number[] = [];
  for (let i = 0; i < V; i++) {
    if (indegree[i] === 0) queue.push(i);
  }

  while (queue.length) {
    const node = queue.shift()!;
    result.push(node);
    for (const neighbor of graph[node]) {
      indegree[neighbor]--;
      if (indegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return result.length === V ? result : null;
}

const V = 6;
const edges: [number, number][] = [[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]];
const result = topologicalSortKahn(V, edges);
console.log(result ? "Topological Sort: " + result : "Cycle detected");

Time complexity

Space complexity

O(V + E)

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