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

Concept Flow - Topological Sort Using Kahn's Algorithm BFS

Calculate in-degree for all nodes

↓

Add nodes with in-degree 0 to queue

↓

While queue not empty

↓

Dequeue node

↓

Add node to topological order

↓

For each neighbor

↓

Decrease in-degree of neighbor

↓

If in-degree becomes 0, enqueue neighbor

↓

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 produce a topological order by repeatedly removing nodes with zero in-degree.

Execution Sample

DSA C#

graph = {0:[1,2],1:[3],2:[3],3:[]};
Calculate in-degree;
Queue = nodes with in-degree 0;
While queue not empty:
  node = dequeue;
  add node to order;
  for neighbor in graph[node]:
    decrease in-degree; enqueue if zero;

This code performs topological sort on a directed graph using Kahn's BFS algorithm.

Execution Table

Step	Operation	Node Processed	Queue State	In-degree State	Topological Order	Visual State
0	Calculate in-degree	N/A	[]	{0:0,1:1,2:1,3:2}	[]	Graph: 0->1,2; 1->3; 2->3; 3->
1	Initialize queue with in-degree 0 nodes	N/A	[0]	{0:0,1:1,2:1,3:2}	[]	Queue: [0]
2	Dequeue node	0	[]	{0:0,1:1,2:1,3:2}	[]	Processing node 0
3	Add node to order	0	[]	{0:0,1:1,2:1,3:2}	[0]	Order: [0]
4	Decrease in-degree of neighbors	0	[]	{0:0,1:0,2:0,3:2}	[0]	Neighbors 1 and 2 in-degree decreased
5	Enqueue neighbors with in-degree 0	0	[1,2]	{0:0,1:0,2:0,3:2}	[0]	Queue: [1,2]
6	Dequeue node	1	[2]	{0:0,1:0,2:0,3:2}	[0]	Processing node 1
7	Add node to order	1	[2]	{0:0,1:0,2:0,3:2}	[0,1]	Order: [0,1]
8	Decrease in-degree of neighbors	1	[2]	{0:0,1:0,2:0,3:1}	[0,1]	Neighbor 3 in-degree decreased
9	Enqueue neighbors with in-degree 0	1	[2]	{0:0,1:0,2:0,3:1}	[0,1]	No new nodes enqueued
10	Dequeue node	2	[]	{0:0,1:0,2:0,3:1}	[0,1]	Processing node 2
11	Add node to order	2	[]	{0:0,1:0,2:0,3:1}	[0,1,2]	Order: [0,1,2]
12	Decrease in-degree of neighbors	2	[]	{0:0,1:0,2:0,3:0}	[0,1,2]	Neighbor 3 in-degree decreased to 0
13	Enqueue neighbors with in-degree 0	2	[3]	{0:0,1:0,2:0,3:0}	[0,1,2]	Queue: [3]
14	Dequeue node	3	[]	{0:0,1:0,2:0,3:0}	[0,1,2]	Processing node 3
15	Add node to order	3	[]	{0:0,1:0,2:0,3:0}	[0,1,2,3]	Order: [0,1,2,3]
16	Queue empty, check completion	N/A	[]	{0:0,1:0,2:0,3:0}	[0,1,2,3]	All nodes processed, topological sort complete

💡 Queue is empty and all nodes are processed, so topological order is complete.

Variable Tracker

Variable	Start	After Step 4	After Step 9	After Step 13	Final
Queue	[]	[]	[1,2]	[3]	[]
In-degree	{0:0,1:1,2:1,3:2}	{0:0,1:0,2:0,3:2}	{0:0,1:0,2:0,3:1}	{0:0,1:0,2:0,3:0}	{0:0,1:0,2:0,3:0}
Topological Order	[]	[0]	[0,1]	[0,1,2]	[0,1,2,3]

Key Moments - 3 Insights

Why do we only enqueue nodes when their in-degree becomes zero?

Because a node can only be processed after all its incoming edges are removed, which means all its dependencies are processed. This is shown in execution_table rows 5, 9, and 13 where nodes are enqueued only when their in-degree hits zero.

What happens if the graph has a cycle?

If there is a cycle, some nodes will never reach in-degree zero, so they won't be enqueued or processed. The topological order will have fewer nodes than the graph size, which can be detected after the queue empties (see exit at step 16).

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

Because removing a node means removing its outgoing edges, so neighbors lose one incoming edge. This is shown in steps 4, 8, and 12 where in-degree values decrease.

Visual Quiz - 3 Questions

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

A [3]

B [1, 2]

C [0]

D []

💡 Hint

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

At which step does node 3 first get enqueued?

A Step 13

B Step 9

C Step 5

D Step 1

💡 Hint

Look at when in-degree of node 3 becomes zero and it enters the queue in execution_table.

If node 2 had no outgoing edges, how would the in-degree of node 3 change after processing node 2?

A It would decrease by 1

B It would increase by 1

C It would stay the same

D Node 3 would be removed

💡 Hint

Refer to the 'Decrease in-degree of neighbors' operation in execution_table and consider if node 2 has no neighbors.

Concept Snapshot

Topological Sort (Kahn's Algorithm):
- Calculate in-degree of all nodes.
- Enqueue nodes with in-degree 0.
- While queue not empty:
  - Dequeue node, add to order.
  - Decrease in-degree of neighbors.
  - Enqueue neighbors with in-degree 0.
- If all nodes processed, order is valid; else cycle exists.

Full Transcript

Topological Sort using Kahn's Algorithm works by first calculating the in-degree (number of incoming edges) for each node in the graph. Nodes with zero in-degree are added to a queue because they have no dependencies. 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 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 not, the graph contains a cycle. The execution table traces each step, showing queue contents, in-degree changes, and the growing topological order. Key moments clarify why nodes are enqueued only when in-degree is zero, what happens with cycles, and why in-degree decreases after processing nodes. The visual quiz tests understanding of queue states, enqueue timing, and effects of 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 detect cycles in an undirected graph

C. To find the shortest path between two nodes

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

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 graph problems: cycle detection, shortest path, and minimum spanning tree, which are not the purpose of Kahn's Algorithm.

3. Final Answer:

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

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 cycle detection
• Thinking it finds shortest paths
• Mixing with minimum spanning tree algorithms

2. Which C# data structure is best suited to store nodes with zero incoming edges during Kahn's Algorithm?

easy

A. Queue

B. Stack

C. Dictionary

D. HashSet

Solution

1. Step 1: Identify the role of zero in-degree nodes

   Kahn's Algorithm processes nodes with zero incoming edges in the order they are discovered, which requires a First-In-First-Out (FIFO) structure.

2. Step 2: Match data structure to FIFO behavior

   A Queue provides FIFO behavior, making it ideal to store and process zero in-degree nodes in the correct order.

3. Final Answer:

   Queue -> Option A

4. Quick Check:

   Zero in-degree nodes use FIFO queue [OK]

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

Common Mistakes:

• Using stack which is LIFO, not suitable here
• Choosing dictionary which stores key-value pairs
• Using hashset which has no order

3. What is the output of the following C# code snippet implementing Kahn's Algorithm on this graph?

var graph = new Dictionary<int, List<int>> {
  {1, new List<int> {2, 3}},
  {2, new List<int> {4}},
  {3, new List<int> {4}},
  {4, new List<int> ()}
};
var result = TopologicalSort(graph);
Console.WriteLine(string.Join(", ", result));

List<int> TopologicalSort(Dictionary<int, List<int>> graph) {
  var inDegree = new Dictionary<int, int>();
  foreach (var node in graph.Keys) inDegree[node] = 0;
  foreach (var edges in graph.Values)
    foreach (var v in edges) inDegree[v]++;
  var queue = new Queue<int>(inDegree.Where(kv => kv.Value == 0).Select(kv => kv.Key));
  var topoOrder = new List<int>();
  while (queue.Count > 0) {
    var u = queue.Dequeue();
    topoOrder.Add(u);
    foreach (var v in graph[u]) {
      inDegree[v]--;
      if (inDegree[v] == 0) queue.Enqueue(v);
    }
  }
  return topoOrder;
}

medium

A. [4, 2, 3, 1]

B. [1, 2, 3, 4]

C. [1, 3, 2, 4]

D. [2, 3, 1, 4]

Solution

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

   Node 1: 0, Node 2: 1 (from 1), Node 3: 1 (from 1), Node 4: 2 (from 2 and 3).

2. Step 2: Process nodes in queue order

   Start with node 1 (in-degree 0). Remove it, reduce in-degree of 2 and 3 to 0, enqueue both. Then dequeue 2, reduce in-degree of 4 to 1. Dequeue 3, reduce in-degree of 4 to 0, enqueue 4. Finally dequeue 4.

3. Final Answer:

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

4. Quick Check:

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

Hint: Track in-degree and queue order carefully [OK]

Common Mistakes:

• Ignoring in-degree updates after dequeue
• Mixing order of nodes with same in-degree
• Starting with wrong initial nodes

4. Identify the bug in this Kahn's Algorithm C# code snippet:

var inDegree = new Dictionary<int, int>();
foreach (var node in graph.Keys) inDegree[node] = 0;
foreach (var edges in graph.Values)
  foreach (var v in edges) inDegree[v] = 0; // Bug here
var queue = new Queue<int>(inDegree.Where(kv => kv.Value == 0).Select(kv => kv.Key));

medium

A. Queue should be a stack for correct order

B. The first loop should initialize inDegree with -1

C. The second loop resets in-degree to zero instead of incrementing

D. The graph.Keys should be iterated twice

Solution

1. Step 1: Analyze in-degree calculation

   The second loop incorrectly sets inDegree[v] = 0 for each adjacent node, overwriting the count instead of incrementing it.

2. Step 2: Correct in-degree update

   It should increment inDegree[v] by 1 for each incoming edge to count properly, i.e., inDegree[v]++.

3. Final Answer:

   The second loop resets in-degree to zero instead of incrementing -> Option C

4. Quick Check:

   In-degree must be incremented, not reset [OK]

Hint: Increment in-degree counts, don't reset them [OK]

Common Mistakes:

• Setting in-degree to zero inside the counting loop
• Using stack instead of queue
• Misinitializing in-degree dictionary

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

hard

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

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

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

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

Solution

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

   Nodes: 0(in-degree 2 from 4,5), 1(in-degree 2 from 3,4), 2(in-degree 1 from 5), 3(in-degree 1 from 2), 4(in-degree 0), 5(in-degree 0).

2. Step 2: Process nodes with zero in-degree first

   Start with 5 and 4. Removing 5 reduces in-degree of 2 to 0 and 0 to 1; removing 4 reduces in-degree of 0 to 0 and 1 to 1. Then process 2 and 0 (in some order), followed by 3, then 1.

3. Final Answer:

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

4. Quick Check:

   Valid topological order respects edges [OK]

Hint: Start with zero in-degree nodes, remove edges stepwise [OK]

Common Mistakes:

• Placing nodes before their dependencies
• Ignoring multiple valid orders
• Starting with nodes that have incoming edges