Topological Sort Using Kahn's Algorithm BFS in DSA C - 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

↓

Pop node from queue

↓

Add node to topological order

↓

Decrease in-degree of neighbors

↓

If neighbor in-degree becomes 0, add to queue

↓

Repeat until queue empty

↓

Check if all nodes processed

↓

Output topological order or detect cycle

This flow shows how Kahn's algorithm uses in-degree counts and a queue to produce a topological order by repeatedly removing nodes with zero in-degree.

Execution Sample

DSA C

int indegree[V] = {0};
queue<int> q;
for (int u = 0; u < V; u++) {
  for (auto v : adj[u]) {
    indegree[v]++;
  }
}
for (int u = 0; u < V; u++) {
  if (indegree[u] == 0) q.push(u);
}

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

Execution Table

Step	Operation	Node Processed	Queue State	In-degree Array	Topological Order	Visual State
1	Calculate in-degree	-	[ ]	[A:0, B:1, C:1, D:2, E:1, F:0]	[]	Graph: A->B, A->C, B->D, C->D, D->E
2	Initialize queue with zero in-degree nodes	-	[A, F]	[A:0, B:1, C:1, D:2, E:1, F:0]	[]	Queue contains nodes with no incoming edges: A, F
3	Pop from queue	A	[F]	[A:0, B:1, C:1, D:2, E:1, F:0]	[A]	Remove A, process neighbors B and C
4	Decrease in-degree of B	-	[F]	[A:0, B:0, C:1, D:2, E:1, F:0]	[A]	B in-degree decreased from 1 to 0
5	Decrease in-degree of C	-	[F]	[A:0, B:0, C:0, D:2, E:1, F:0]	[A]	C in-degree decreased from 1 to 0
6	Add B and C to queue	-	[F, B, C]	[A:0, B:0, C:0, D:2, E:1, F:0]	[A]	B and C added to queue as their in-degree is zero
7	Pop from queue	F	[B, C]	[A:0, B:0, C:0, D:2, E:1, F:0]	[A, F]	Remove F, no neighbors to process
8	Pop from queue	B	[C]	[A:0, B:0, C:0, D:2, E:1, F:0]	[A, F, B]	Remove B, process neighbor D
9	Decrease in-degree of D	-	[C]	[A:0, B:0, C:0, D:1, E:1, F:0]	[A, F, B]	D in-degree decreased from 2 to 1
10	Pop from queue	C	[]	[A:0, B:0, C:0, D:1, E:1, F:0]	[A, F, B, C]	Remove C, process neighbor D
11	Decrease in-degree of D	-	[]	[A:0, B:0, C:0, D:0, E:1, F:0]	[A, F, B, C]	D in-degree decreased from 1 to 0
12	Add D to queue	-	[D]	[A:0, B:0, C:0, D:0, E:1, F:0]	[A, F, B, C]	D added to queue as in-degree is zero
13	Pop from queue	D	[]	[A:0, B:0, C:0, D:0, E:1, F:0]	[A, F, B, C, D]	Remove D, process neighbor E
14	Decrease in-degree of E	-	[]	[A:0, B:0, C:0, D:0, E:0, F:0]	[A, F, B, C, D]	E in-degree decreased from 1 to 0
15	Add E to queue	-	[E]	[A:0, B:0, C:0, D:0, E:0, F:0]	[A, F, B, C, D]	E added to queue as in-degree is zero
16	Pop from queue	E	[]	[A:0, B:0, C:0, D:0, E:0, F:0]	[A, F, B, C, D, E]	Remove E, no neighbors to process
17	Check if all nodes processed	-	[]	[A:0, B:0, C:0, D:0, E:0, F:0]	[A, F, B, C, D, E]	All nodes processed, topological order complete

💡 Queue empty and all nodes processed, topological order found

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 11	After Step 15	Final
Queue	[]	[A, F]	[F, B, C]	[]	[E]	[]
In-degree	[A:0, B:1, C:1, D:2, E:1, F:0]	[A:0, B:1, C:1, D:2, E:1, F:0]	[A:0, B:0, C:0, D:2, E:1, F:0]	[A:0, B:0, C:0, D:0, E:1, F:0]	[A:0, B:0, C:0, D:0, E:0, F:0]	[A:0, B:0, C:0, D:0, E:0, F:0]
Topological Order	[]	[]	[A]	[A, F, B, C]	[A, F, B, C, D]	[A, F, B, C, D, E]

Key Moments - 3 Insights

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

Nodes with zero in-degree have no dependencies and can be processed first. This is shown in execution_table row 2 where nodes A and F are added to the queue initially.

What happens when we decrease the in-degree of neighbors?

Decreasing in-degree simulates removing the processed node's edges. When a neighbor's in-degree becomes zero, it means all its dependencies are processed, so it is added to the queue (see rows 4-6 and 11-12).

How do we know if the graph has a cycle?

If after processing, some nodes still have non-zero in-degree and the queue is empty, it means a cycle exists. Here, all nodes reach zero in-degree and are processed (row 17), so no cycle.

Visual Quiz - 3 Questions

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

A [F, B, C]

B [A, F]

C [B, C]

D [C]

💡 Hint

Check the 'Queue State' column at step 6 in execution_table

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

A Step 11

B Step 12

C Step 13

D Step 14

💡 Hint

Look for the step where 'Add D to queue' operation happens in execution_table

If node E had an extra incoming edge, how would the in-degree array change after step 14?

A E's in-degree would be 1 instead of 0

B E's in-degree would be 0 as before

C D's in-degree would increase

D F's in-degree would increase

💡 Hint

Check the 'In-degree Array' column at step 14 and consider how extra edges affect in-degree

Concept Snapshot

Topological Sort (Kahn's Algorithm):
- Calculate in-degree for all nodes
- Add nodes with zero in-degree to a queue
- While queue not empty:
  - Remove node, add to order
  - Decrease in-degree of neighbors
  - Add neighbors with zero in-degree to queue
- If all nodes processed, order is valid
- Detect cycle if nodes remain unprocessed

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 a neighbor's in-degree becomes 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 some nodes remain with non-zero in-degree, it means the graph has a cycle and no valid topological order exists. The execution table shows each step, including queue contents, in-degree array, and the growing topological order. Key moments include understanding why zero in-degree nodes start the process, how in-degree decreases simulate edge removal, and how cycle detection works by checking unprocessed nodes. The visual quiz tests understanding of queue states, step when nodes are added, and effects of extra edges on in-degree.

Practice

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

easy

A. To calculate the minimum spanning tree

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

C. To detect cycles in an undirected graph

D. To find the shortest path between two nodes

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 like shortest path, cycle detection, and minimum spanning tree solve different problems unrelated to topological sorting.

3. Final Answer:

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

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 it up with minimum spanning tree algorithms

2. Which data structure is primarily used in Kahn's Algorithm to keep track of nodes with zero incoming edges?

easy

A. Priority Queue

B. Stack

C. Queue

D. Hash Map

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 a first-in-first-out manner, ensuring correct topological order.

2. Step 2: Why not other data structures?

   A stack would reverse the order, a priority queue is not necessary for basic Kahn's Algorithm, and a hash map stores key-value pairs, not order.

3. Final Answer:

   Queue -> Option C

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
• Confusing priority queue with normal queue
• Thinking hash map manages order

3. Consider the directed graph with edges: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1. What is the topological order produced by Kahn's Algorithm?

medium

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

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

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

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

Solution

1. Step 1: Calculate in-degree of each node

   Nodes: 0(in-degree 2),1(2),2(1),3(1),4(0),5(0). Start with nodes 4 and 5 in queue (pushed in ascending order: queue [4,5]).

2. Step 2: Process nodes in queue and update in-degree

   Pop 4: output [4], reduce 0->1, 1->1. Queue: [5]
   Pop 5: output [4,5], reduce 2->0 (push 2), 0->0 (push 0). Queue: [2,0]
   Pop 2: output [4,5,2], reduce 3->0 (push 3). Queue: [0,3]
   Pop 0: output [4,5,2,0], no neighbors. Queue: [3]
   Pop 3: output [4,5,2,0,3], reduce 1->0 (push 1). Queue: [1]
   Pop 1: output [4,5,2,0,3,1]. All nodes processed.

3. Final Answer:

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

4. Quick Check:

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

Hint: Start with zero in-degree nodes, update neighbors' in-degree [OK]

Common Mistakes:

• Not updating in-degree after removing nodes
• Wrong initial zero in-degree nodes
• Mixing order of nodes in queue

4. Given the following code snippet for Kahn's Algorithm, what is the error?

int indegree[V] = {0};
for (int i = 0; i < V; i++) {
  for (int j = 0; j < adj[i].size(); j++) {
    indegree[adj[i][j]]++;
  }
}
queue<int> q;
for (int i = 0; i < V; i++) {
  if (indegree[i] == 0) q.push(i);
}
while (!q.empty()) {
  int u = q.front(); q.pop();
  cout << u << " ";
  for (int v : adj[u]) {
    indegree[v]--;
    if (indegree[v] == 0) q.push(v);
  }
}

medium

A. No error, the code is correct

B. The adjacency list is not declared properly

C. The indegree array is not initialized correctly

D. The loop to push zero indegree nodes is missing

Solution

1. Step 1: Check indegree initialization

   Indegree array is initialized to zero for all vertices correctly using {0} syntax.

2. Step 2: Verify adjacency list and loops

   Loops correctly calculate indegree, push zero indegree nodes, and process queue with BFS logic.

3. Final Answer:

   No error, the code is correct -> Option A

4. Quick Check:

   Code matches Kahn's Algorithm steps [OK]

Hint: Check initialization and loops carefully for correctness [OK]

Common Mistakes:

• Forgetting to initialize indegree array
• Incorrect adjacency list declaration
• Missing zero indegree node insertion

5. You have a graph with edges: 1->2, 1->3, 3->4, 2->4, 4->5, and 5->3. What will Kahn's Algorithm detect when run on this graph?

hard

A. A valid topological order exists

B. The algorithm will run infinitely without stopping

C. The graph is disconnected but topological order exists

D. The graph contains a cycle, so no topological order

Solution

1. Step 1: Identify cycle in the graph

   The edges 3->4, 4->5, and 5->3 form a cycle (3->4->5->3), so the graph is not a DAG.

2. Step 2: Understand Kahn's Algorithm behavior on cycles

   Kahn's Algorithm fails to process all nodes if a cycle exists because some nodes never reach zero in-degree, indicating no valid topological order.

3. Final Answer:

   The graph contains a cycle, so no topological order -> Option D

4. Quick Check:

   Cycle detected = no topological order [OK]

Hint: Cycle means no topological order in Kahn's Algorithm [OK]

Common Mistakes:

• Assuming topological order exists despite cycle
• Thinking disconnected graph always causes failure
• Believing algorithm runs infinitely on cycle