Topological Sort Using Kahn's Algorithm BFS in DSA Java - Execution Trace

Concept Flow - Topological Sort Using Kahn's Algorithm BFS

Calculate in-degree of all nodes

↓

Add nodes with in-degree 0 to queue

↓

While queue not empty

↓

Remove node from queue

↓

Add node to topological order

↓

Decrease in-degree of neighbors

↓

If neighbor in-degree is 0, add to queue

↓

Repeat until queue empty

↓

Check if topological order includes all nodes

↓

Done or cycle detected

This flow shows how Kahn's algorithm uses in-degree counts and a queue to build a topological order step-by-step.

Execution Sample

DSA Java

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

This code calculates in-degree for each node and adds nodes with zero in-degree to the queue.

Execution Table

Step	Operation	Node Processed	Queue State	In-degree Array	Topological Order	Visual State
0	Calculate in-degree	N/A	[]	[0, 1, 1, 2, 0, 1]	[]	Graph with nodes 0-5, edges: 0->1,0->2,1->3,2->3,4->5
1	Add nodes with in-degree 0 to queue	N/A	[0,4]	[0, 1, 1, 2, 0, 1]	[]	Queue initialized with nodes 0 and 4
2	Remove node from queue	0	[4]	[0, 1, 1, 2, 0, 1]	[]	Processing node 0
3	Add node to topological order	0	[4]	[0, 1, 1, 2, 0, 1]	[0]	Topological order updated
4	Decrease in-degree of neighbors	0	[4]	[0, 0, 0, 2, 0, 1]	[0]	Neighbors 1 and 2 in-degree decremented
5	Add neighbors with in-degree 0 to queue	0	[4,1,2]	[0, 0, 0, 2, 0, 1]	[0]	Nodes 1 and 2 added to queue
6	Remove node from queue	4	[1,2]	[0, 0, 0, 2, 0, 1]	[0]	Processing node 4
7	Add node to topological order	4	[1,2]	[0, 0, 0, 2, 0, 1]	[0,4]	Topological order updated
8	Decrease in-degree of neighbors	4	[1,2]	[0, 0, 0, 2, 0, 0]	[0,4]	Neighbor 5 in-degree decremented
9	Add neighbors with in-degree 0 to queue	4	[1,2,5]	[0, 0, 0, 2, 0, 0]	[0,4]	Node 5 added to queue
10	Remove node from queue	1	[2,5]	[0, 0, 0, 2, 0, 0]	[0,4]	Processing node 1
11	Add node to topological order	1	[2,5]	[0, 0, 0, 2, 0, 0]	[0,4,1]	Topological order updated
12	Decrease in-degree of neighbors	1	[2,5]	[0, 0, 0, 1, 0, 0]	[0,4,1]	Neighbor 3 in-degree decremented
13	Add neighbors with in-degree 0 to queue	1	[2,5]	[0, 0, 0, 1, 0, 0]	[0,4,1]	No new nodes added
14	Remove node from queue	2	[5]	[0, 0, 0, 1, 0, 0]	[0,4,1]	Processing node 2
15	Add node to topological order	2	[5]	[0, 0, 0, 1, 0, 0]	[0,4,1,2]	Topological order updated
16	Decrease in-degree of neighbors	2	[5]	[0, 0, 0, 0, 0, 0]	[0,4,1,2]	Neighbor 3 in-degree decremented to 0
17	Add neighbors with in-degree 0 to queue	2	[5,3]	[0, 0, 0, 0, 0, 0]	[0,4,1,2]	Node 3 added to queue
18	Remove node from queue	5	[3]	[0, 0, 0, 0, 0, 0]	[0,4,1,2]	Processing node 5
19	Add node to topological order	5	[3]	[0, 0, 0, 0, 0, 0]	[0,4,1,2,5]	Topological order updated
20	Decrease in-degree of neighbors	5	[3]	[0, 0, 0, 0, 0, 0]	[0,4,1,2,5]	No neighbors
21	Add neighbors with in-degree 0 to queue	5	[3]	[0, 0, 0, 0, 0, 0]	[0,4,1,2,5]	No new nodes added
22	Remove node from queue	3	[]	[0, 0, 0, 0, 0, 0]	[0,4,1,2,5]	Processing node 3
23	Add node to topological order	3	[]	[0, 0, 0, 0, 0, 0]	[0,4,1,2,5,3]	Topological order updated
24	Decrease in-degree of neighbors	3	[]	[0, 0, 0, 0, 0, 0]	[0,4,1,2,5,3]	No neighbors
25	Add neighbors with in-degree 0 to queue	3	[]	[0, 0, 0, 0, 0, 0]	[0,4,1,2,5,3]	No new nodes added
26	Queue empty, check completion	N/A	[]	[0, 0, 0, 0, 0, 0]	[0,4,1,2,5,3]	All nodes processed, topological order complete

💡 Queue is empty and all nodes are processed, topological order found

Variable Tracker

Variable	Start	After Step 0	After Step 5	After Step 9	After Step 17	After Step 26
inDegree	[0,0,0,0,0,0]	[0,1,1,2,0,1]	[0,0,0,2,0,1]	[0,0,0,2,0,0]	[0,0,0,0,0,0]	[0,0,0,0,0,0]
queue	[]	[]	[4,1,2]	[1,2,5]	[5,3]	[]
topologicalOrder	[]	[]	[0]	[0,4]	[0,4,1,2]	[0,4,1,2,5,3]

Key Moments - 3 Insights

Why do we add nodes with in-degree 0 to the queue at the start?

Nodes with in-degree 0 have no dependencies and can be processed first. This is shown in execution_table row 1 where nodes 0 and 4 are added to the queue.

Why do we decrease the in-degree of neighbors after processing a node?

Processing a node means its edges are removed, so neighbors lose one dependency. This is shown in rows 4 and 12 where neighbors' in-degree values decrease.

What happens if the queue becomes empty before processing all nodes?

It means a cycle exists and topological sort is impossible. In this example, the queue empties only after all nodes are processed (row 26), so no cycle.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what nodes are in the queue?

A [0,4]

B [1,2]

C [4,1,2]

D [5,3]

💡 Hint

Check the 'Queue State' column at step 5 in the execution_table.

At which step does node 3 get added to the queue?

A Step 13

B Step 17

C Step 9

D Step 22

💡 Hint

Look for when in-degree of node 3 becomes zero and it is added to the queue in the execution_table.

If node 4 had an incoming edge, how would the initial queue change?

A Node 4 would not be in the initial queue

B Node 4 would still be in the initial queue

C Queue would be empty initially

D All nodes would be in the initial queue

💡 Hint

Refer to the variable_tracker and execution_table rows 0 and 1 about in-degree and initial queue.

Concept Snapshot

Topological Sort (Kahn's Algorithm):
- Calculate in-degree for all nodes
- Add nodes with in-degree 0 to queue
- While queue not empty:
  - Remove node, add to order
  - Decrease neighbors' in-degree
  - Add neighbors with in-degree 0 to queue
- If all nodes processed, order is valid
- Detects cycles if not all nodes processed

Full Transcript

Topological Sort using Kahn's Algorithm works by first calculating the in-degree of each node, which counts how many edges come into it. Nodes with zero in-degree have no dependencies and are added to a queue. Then, the algorithm repeatedly removes nodes from the queue, adds them to the topological order, and decreases the in-degree of their neighbors. If any neighbor's in-degree drops to zero, it is added to the queue. This process continues until the queue is empty. If all nodes are processed, the topological order is complete. If not, a cycle exists and topological sorting is impossible. The execution table shows each step, queue state, in-degree array, and the growing topological order. The variable tracker highlights how in-degree, queue, and order change over key steps. Key moments clarify why nodes with zero in-degree start the queue, why neighbors' in-degree decreases, and what cycle detection means. The visual quiz tests understanding of queue contents, step when nodes are added, and effects of graph changes. This method is efficient and widely used for ordering tasks with dependencies.

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