Topological Sort Using Kahn's Algorithm BFS in DSA Java

Mental Model

We find an order to do tasks so that all prerequisites come before the task itself. We start with tasks that have no prerequisites and remove them step by step.

Analogy: Imagine you have to bake a cake but must first prepare ingredients. You start with tasks that need no preparation, then remove them from the list, unlocking the next tasks that depended on them.

Graph nodes with arrows showing dependencies:

  5 -> 0 ← 4
  ↓         ↑
  2 -> 3 -> 1

Nodes with no incoming arrows are ready to process first.

Dry Run Walkthrough

Input: Graph edges: 5->0, 5->2, 4->0, 4->1, 2->3, 3->1

Goal: Find a valid order to complete all tasks respecting dependencies

Step 1: Calculate in-degree (number of incoming edges) for each node

in-degree: 0=2, 1=2, 2=1, 3=1, 4=0, 5=0

Why: We need to know which nodes have no prerequisites to start with

Step 2: Add nodes with in-degree 0 (4,5) to the queue

queue: [4, 5]

Why: These nodes can be processed first as they have no dependencies

Step 3: Remove 4 from queue and add to result; reduce in-degree of its neighbors (0,1)

result: [4]
in-degree updated: 0=1, 1=1
queue: [5]

Why: Processing 4 unlocks its dependent tasks

Step 4: Remove 5 from queue and add to result; reduce in-degree of its neighbors (0,2)

result: [4, 5]
in-degree updated: 0=0, 2=0
queue: [0, 2]

Why: Processing 5 unlocks more tasks

Step 5: Remove 0 from queue and add to result; it has no neighbors

result: [4, 5, 0]
queue: [2]

Why: 0 is done, no further unlocks

Step 6: Remove 2 from queue and add to result; reduce in-degree of neighbor (3)

result: [4, 5, 0, 2]
in-degree updated: 3=0
queue: [3]

Why: Processing 2 unlocks task 3

Step 7: Remove 3 from queue and add to result; reduce in-degree of neighbor (1)

result: [4, 5, 0, 2, 3]
in-degree updated: 1=0
queue: [1]

Why: Processing 3 unlocks task 1

Step 8: Remove 1 from queue and add to result; no neighbors left

result: [4, 5, 0, 2, 3, 1]
queue: []

Why: All tasks processed in valid order

Result:

4 -> 5 -> 0 -> 2 -> 3 -> 1

Annotated Code

DSA Java

import java.util.*;

public class KahnTopologicalSort {

    static List<Integer> topologicalSort(int n, List<List<Integer>> graph) {
        int[] inDegree = new int[n];
        // Calculate in-degree for each node
        for (int u = 0; u < n; u++) {
            for (int v : graph.get(u)) {
                inDegree[v]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        // Add all nodes with in-degree 0 to queue
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        List<Integer> result = new ArrayList<>();

        while (!queue.isEmpty()) {
            int u = queue.poll();
            result.add(u);
            // Decrease in-degree of neighbors
            for (int v : graph.get(u)) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue.add(v);
                }
            }
        }

        // If result size != n, graph has cycle (not handled here)
        return result;
    }

    public static void main(String[] args) {
        int n = 6;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // Edges: 5->0, 5->2, 4->0, 4->1, 2->3, 3->1
        graph.get(5).add(0);
        graph.get(5).add(2);
        graph.get(4).add(0);
        graph.get(4).add(1);
        graph.get(2).add(3);
        graph.get(3).add(1);

        List<Integer> order = topologicalSort(n, graph);

        for (int node : order) {
            System.out.print(node + " -> ");
        }
        System.out.print("null\n");
    }
}

for (int u = 0; u < n; u++) { for (int v : graph.get(u)) { inDegree[v]++; } }

Calculate in-degree for each node to find prerequisites

for (int i = 0; i < n; i++) { if (inDegree[i] == 0) { queue.add(i); } }

Add all nodes with no prerequisites to the queue

while (!queue.isEmpty()) { int u = queue.poll(); result.add(u);

Process nodes with no prerequisites and add to result

for (int v : graph.get(u)) { inDegree[v]--; if (inDegree[v] == 0) { queue.add(v); } }

Reduce in-degree of neighbors and add newly free nodes to queue

Output

4 -> 5 -> 0 -> 2 -> 3 -> 1 -> null

Complexity Analysis

Time: O(V + E) because we visit each node and edge once during in-degree calculation and BFS

Space: O(V + E) for storing the graph and in-degree array

vs Alternative: Compared to DFS-based topological sort, Kahn's algorithm uses BFS and explicit in-degree tracking, which can be easier to understand and detect cycles.

Edge Cases

Empty graph (no nodes)

Returns empty order immediately

DSA Java

for (int i = 0; i < n; i++) { if (inDegree[i] == 0) { queue.add(i); } }

Graph with single node and no edges

Returns list with that single node

DSA Java

for (int i = 0; i < n; i++) { if (inDegree[i] == 0) { queue.add(i); } }

Graph with cycle

Result list size less than n, indicating cycle (not explicitly handled)

DSA Java

return result;

When to Use This Pattern

When you need to order tasks with dependencies and want to process nodes with no prerequisites first, use Kahn's algorithm BFS for topological sorting.

Common Mistakes

Mistake: Not updating in-degree of neighbors after removing a node
Fix: Decrease in-degree of all neighbors and add those with zero in-degree to the queue

Mistake: Not adding initial zero in-degree nodes to the queue
Fix: Scan all nodes and add those with zero in-degree before starting BFS

Summary

Finds a valid order of tasks respecting dependencies using BFS and in-degree counts.

Use when you want to process tasks only after their prerequisites are done.

Start with tasks having no prerequisites and remove them stepwise, unlocking dependent tasks.

Practice

1. What is the main purpose of Kahn's Algorithm in graph theory?

easy

A. To find a topological ordering of a Directed Acyclic Graph (DAG)

B. To detect cycles in an undirected graph

C. To find the shortest path between two nodes

D. To calculate the minimum spanning tree

Solution

1. Step 1: Understand Kahn's Algorithm goal

   Kahn's Algorithm is designed to produce a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u -> v, u comes before v in the ordering.

2. Step 2: Compare with other graph algorithms

   Other options describe different algorithms: cycle detection, shortest path, and minimum spanning tree are unrelated to Kahn's Algorithm.

3. Final Answer:

   To find a topological ordering of a Directed Acyclic Graph (DAG) -> Option A

4. Quick Check:

   Topological sort = Kahn's Algorithm purpose [OK]

Hint: Kahn's Algorithm always finds order in DAGs [OK]

Common Mistakes:

• Confusing topological sort with shortest path
• Thinking it detects cycles in undirected graphs
• Mixing with minimum spanning tree algorithms

2. Which Java data structure is typically used to store nodes with zero incoming edges in Kahn's Algorithm?

easy

A. Queue

B. HashSet

C. Stack

D. PriorityQueue

Solution

1. Step 1: Identify the data structure for zero in-degree nodes

   Kahn's Algorithm uses a queue to process nodes with zero incoming edges in FIFO order to maintain correct topological order.

2. Step 2: Eliminate other options

   Stack is LIFO, which can change order; HashSet does not maintain order; PriorityQueue is not required for basic Kahn's Algorithm.

3. Final Answer:

   Queue -> Option A

4. Quick Check:

   Zero in-degree nodes stored in queue [OK]

Hint: Use queue for BFS order in Kahn's Algorithm [OK]

Common Mistakes:

• Using stack instead of queue
• Choosing unordered sets instead of ordered structures
• Confusing with priority queue usage

3. What is the output of the following Java code snippet using Kahn's Algorithm on this graph?

Graph edges: 5->0, 5->2, 4->0, 4->1, 2->3, 3->1

// After running Kahn's Algorithm, print the topological order.

medium

A. [5, 4, 2, 3, 1, 0]

B. [4, 5, 2, 3, 1, 0]

C. [4, 5, 0, 2, 3, 1]

D. [5, 4, 3, 2, 1, 0]

Solution

1. Step 1: Calculate in-degree and start nodes

   Nodes 4 and 5 have zero in-degree. Start queue with [4,5] (assuming ascending order).

2. Step 2: Process nodes in queue

   Process 4: output [4], reduce 0 to 1, 1 to 1. Process 5: output [4,5], reduce 0 to 0 (add 0), 2 to 0 (add 2); queue=[0,2]. Process 0: [4,5,0], no neighbors. Process 2: [4,5,0,2], reduce 3 to 0 (add 3). Process 3: [4,5,0,2,3], reduce 1 to 0 (add 1). Process 1: [4,5,0,2,3,1].

3. Final Answer:

   [4, 5, 0, 2, 3, 1] -> Option C

4. Quick Check:

   Topological order = [4,5,0,2,3,1] [OK]

Hint: Start with zero in-degree nodes, process neighbors, repeat [OK]

Common Mistakes:

• Mixing order of nodes with zero in-degree
• Not updating in-degree after removing edges
• Adding nodes to queue too early or late

4. Identify the bug in this Java snippet implementing Kahn's Algorithm:

while (!queue.isEmpty()) {
  int node = queue.poll();
  result.add(node);
  for (int neighbor : graph.get(node)) {
    inDegree[neighbor]--;
    if (inDegree[node] == 0) {
      queue.add(neighbor);
    }
}

medium

A. Neighbors should not be iterated in this loop

B. Queue should be a stack for correct order

C. Result list should be cleared inside the loop

D. Incorrect check: should check inDegree[neighbor] == 0, not inDegree[node]

Solution

1. Step 1: Analyze the in-degree update and condition

   After decrementing inDegree[neighbor], the code incorrectly checks if inDegree[node] == 0 instead of inDegree[neighbor] == 0.

2. Step 2: Correct the condition to add neighbors with zero in-degree

   The correct condition is if (inDegree[neighbor] == 0) to add that neighbor to the queue for processing.

3. Final Answer:

   Incorrect check: should check inDegree[neighbor] == 0, not inDegree[node] -> Option D

4. Quick Check:

   Check zero in-degree on neighbor, not current node [OK]

Hint: Check in-degree of neighbor after decrement [OK]

Common Mistakes:

• Checking in-degree of wrong node
• Using stack instead of queue
• Clearing result inside loop mistakenly

5. Given a graph with edges: 1->2, 1->3, 3->4, 2->4, 4->5, and 5->6, which of the following is a valid topological order using Kahn's Algorithm?

hard

A. [1, 2, 3, 5, 4, 6]

B. [1, 3, 2, 4, 5, 6]

C. [6, 5, 4, 3, 2, 1]

D. [1, 2, 3, 4, 6, 5]

Solution

1. Step 1: Identify nodes with zero in-degree and dependencies

   Node 1 has zero in-degree. Nodes 2 and 3 depend on 1; 4 depends on 2 and 3; 5 depends on 4; 6 depends on 5.

2. Step 2: Validate each option for correct order

   [1, 3, 2, 4, 5, 6] respects dependencies: 1 before 2 and 3, 3 and 2 before 4, 4 before 5, 5 before 6. [1, 2, 3, 4, 6, 5] places 6 before 5, invalid. [6, 5, 4, 3, 2, 1] reverses order, invalid. [1, 2, 3, 5, 4, 6] places 5 before 4, invalid.

3. Final Answer:

   [1, 3, 2, 4, 5, 6] -> Option B

4. Quick Check:

   Dependencies respected in order D [OK]

Hint: Parents always appear before children in topological order [OK]

Common Mistakes:

• Placing dependent nodes before their parents
• Reversing the order of edges
• Ignoring multiple valid topological orders