Kahn's Algorithm (BFS topological sort): in-degree array + zero-degree queue

• In-degree tracking – count incoming edges for each node; nodes with zero in-degree have no pending dependencies.
• Queue of ready nodes – enqueue all zero-in-degree nodes as the starting batch.
• Emit and update – dequeue a node, append it to the order, and decrement successors' in-degrees.
• Cycle detection – if the emitted count is less than the total node count, a cycle exists.
• O(V + E) time – each node is enqueued once and each edge is processed once.

What is topological sorting?

Topological sorting produces a linear ordering of nodes in a directed acyclic graph (DAG) such that for every directed edge u to v, node u appears before node v. In a banking context, Pankaj manages end-of-day settlement tasks at National Bank of India where some tasks depend on others, and he needs a valid execution order.

How does Kahn's algorithm work?

Build the adjacency list and compute each node's in-degree. Enqueue every node whose in-degree is zero. Repeatedly dequeue a node, append it to the order, and for each successor decrement its in-degree, enqueueing it when the in-degree hits zero.

package com.bank.service;

import java.util.*;

public class SettlementScheduler {

    public static List<Integer> topologicalSort(int numTasks, int[][] dependencies) {
        List<List<Integer>> adj = new ArrayList<>();
        int[] inDegree = new int[numTasks];
        for (int i = 0; i < numTasks; i++) adj.add(new ArrayList<>());

        for (int[] dep : dependencies) {
            adj.get(dep[0]).add(dep[1]);
            inDegree[dep[1]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numTasks; i++) {
            if (inDegree[i] == 0) queue.add(i);
        }

        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int task = queue.poll();
            order.add(task);
            for (int next : adj.get(task)) {
                inDegree[next]--;
                if (inDegree[next] == 0) queue.add(next);
            }
        }

        if (order.size() != numTasks) {
            throw new IllegalStateException("Cycle detected: no valid schedule");
        }
        return order;
    }

    public static void main(String[] args) {
        // Tasks: 0=Load accounts, 1=Compute interest, 2=Apply fees,
        //        3=Generate statements, 4=Send notifications
        int[][] deps = {{0,1}, {0,2}, {1,3}, {2,3}, {3,4}};
        List<Integer> schedule = topologicalSort(5, deps);
        String[] names = {"Load accounts", "Compute interest",
            "Apply fees", "Generate statements", "Send notifications"};
        System.out.println("Settlement schedule:");
        for (int task : schedule) {
            System.out.println("  " + task + ": " + names[task]);
        }
    }
}

Settlement schedule:
  0: Load accounts
  1: Compute interest
  2: Apply fees
  3: Generate statements
  4: Send notifications

How does cycle detection work?

If the graph has a cycle, some nodes never reach zero in-degree because they are locked in a circular dependency. The emitted count will be less than the total node count. This check comes for free from the algorithm.

What is the time and space complexity?

• Time: O(V + E) because each node is enqueued once and each edge is processed once.
• Space: O(V + E) for the adjacency list, in-degree array, queue, and output list.

How is Kahn's different from DFS-based topological sort?

| Aspect | Kahn's (BFS) | DFS-based |
|---|---|---|
| Approach | Remove zero-in-degree nodes | Post-order reversal |
| Cycle detection | Emitted count < total | Gray node re-visited |
| Iterative | Naturally iterative | Needs explicit stack for large graphs |
| Lex-smallest order | Use PriorityQueue | Not straightforward |

How do you get the lexicographically smallest order?

Replace the plain Queue with a PriorityQueue so that among nodes with zero in-degree, the smallest one is always chosen first.

Queue<Integer> queue = new PriorityQueue<>();
// Rest of algorithm unchanged

What are common mistakes?

The most common mistake is forgetting to initialise the in-degree array, leading to all nodes being enqueued immediately. Another is not checking the emitted count for cycle detection.

// Wrong: missing cycle check
return order; // may return partial order if cycle exists

// Correct: verify all nodes were emitted
if (order.size() != numTasks) {
    throw new IllegalStateException("Cycle detected");
}

What should a senior engineer know?

A senior engineer knows that Kahn's algorithm is naturally iterative, avoiding the recursion-depth limits a DFS-based sort can hit on large graphs. The senior also knows that the algorithm is the foundation for build systems (Maven, Gradle) that resolve dependency order, and for database migration tools that order schema changes. In the settlement pipeline at National Bank of India, Pankaj uses this to produce a deterministic execution order for hundreds of interdependent tasks.