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

Mental Model

We find an order to do tasks so that all requirements come before the tasks that need them. We do this by always picking tasks that have no unmet requirements first.

Analogy: Imagine you have a list of homework assignments where some depend on others being done first. You start with assignments that have no prerequisites, finish them, then move on to assignments that become free of prerequisites as you go.

Graph:
0 -> 1 -> 3
↓    ↓
2    4

In-degree array:
[0]=0, [1]=1, [2]=1, [3]=1, [4]=1

Queue initially: 0 (tasks with zero prerequisites)

Dry Run Walkthrough

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

Goal: Find a valid order to complete tasks so all dependencies come before dependent tasks

Step 1: Calculate in-degree for each node

In-degree: [0]=0, [1]=1, [2]=1, [3]=1, [4]=1
Queue: empty

Why: We need to know how many prerequisites each task has

Step 2: Add nodes with zero in-degree to queue

In-degree: [0]=0, [1]=1, [2]=1, [3]=1, [4]=1
Queue: 0

Why: Start with tasks that have no prerequisites

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

In-degree: [0]=0, [1]=0, [2]=0, [3]=1, [4]=1
Queue: 1, 2
Result: 0

Why: Completing 0 frees up its dependent tasks

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

In-degree: [0]=0, [1]=0, [2]=0, [3]=0, [4]=0
Queue: 2, 3, 4
Result: 0 -> 1

Why: Completing 1 frees up its dependent tasks

Step 5: Remove 2 from queue and add to result; no neighbors to update

In-degree unchanged
Queue: 3, 4
Result: 0 -> 1 -> 2

Why: 2 has no dependent tasks

Step 6: Remove 3 from queue and add to result; no neighbors to update

Queue: 4
Result: 0 -> 1 -> 2 -> 3

Why: 3 has no dependent tasks

Step 7: Remove 4 from queue and add to result; no neighbors to update

Queue: empty
Result: 0 -> 1 -> 2 -> 3 -> 4

Why: 4 has no dependent tasks

Result:

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

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    private readonly int V;
    private readonly List<int>[] adj;

    public Graph(int vertices) {
        V = vertices;
        adj = new List<int>[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int u, int v) {
        adj[u].Add(v);
    }

    public List<int> KahnTopologicalSort() {
        int[] inDegree = new int[V];

        // Calculate in-degree of each vertex
        for (int i = 0; i < V; i++) {
            foreach (int node in adj[i]) {
                inDegree[node]++;
            }
        }

        Queue<int> queue = new Queue<int>();

        // Enqueue vertices with zero in-degree
        for (int i = 0; i < V; i++) {
            if (inDegree[i] == 0) {
                queue.Enqueue(i);
            }
        }

        List<int> topoOrder = new List<int>();

        while (queue.Count > 0) {
            int u = queue.Dequeue();
            topoOrder.Add(u);

            // Decrease in-degree of neighbors
            foreach (int neighbor in adj[u]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.Enqueue(neighbor);
                }
            }
        }

        // If topoOrder size != V, graph has a cycle
        if (topoOrder.Count != V) {
            throw new InvalidOperationException("Graph has at least one cycle, topological sort not possible.");
        }

        return topoOrder;
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(5);
        g.AddEdge(0, 1);
        g.AddEdge(0, 2);
        g.AddEdge(1, 3);
        g.AddEdge(1, 4);

        List<int> result = g.KahnTopologicalSort();
        Console.WriteLine(string.Join(" -> ", result));
    }
}

for (int i = 0; i < V; i++) { foreach (int node in adj[i]) { inDegree[node]++; } }

Calculate in-degree for each node by counting incoming edges

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

Add all nodes with zero in-degree to the queue to start processing

while (queue.Count > 0) { int u = queue.Dequeue(); topoOrder.Add(u);

Remove node from queue and add it to the topological order

foreach (int neighbor in adj[u]) { inDegree[neighbor]--; if (inDegree[neighbor] == 0) { queue.Enqueue(neighbor); } }

Reduce in-degree of neighbors and enqueue if they become zero

if (topoOrder.Count != V) { throw new InvalidOperationException("Graph has at least one cycle, topological sort not possible."); }

Check for cycles by verifying if all nodes were processed

Output

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

Complexity Analysis

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

Space: O(V + E) for adjacency list and in-degree array plus queue and output list

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 early

Edge Cases

Graph with cycle

Throws exception indicating topological sort is not possible

DSA C#

if (topoOrder.Count != V) { throw new InvalidOperationException("Graph has at least one cycle, topological sort not possible."); }

Graph with no edges (all nodes independent)

All nodes have zero in-degree and appear in any order in the output

DSA C#

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

Single node graph

Returns list with the single node

DSA C#

while (queue.Count > 0) { int u = queue.Dequeue(); topoOrder.Add(u);

When to Use This Pattern

When you need to order tasks with dependencies and want to detect cycles, use Kahn's algorithm because it processes nodes with no unmet prerequisites first using BFS.

Common Mistakes

Mistake: Not updating in-degree of neighbors after removing a node
Fix: Always decrease in-degree of neighbors and enqueue them if their in-degree becomes zero

Mistake: Not checking if all nodes were processed, missing cycle detection
Fix: Compare the size of the result list with the number of nodes to detect cycles

Summary

Finds a valid order to complete tasks with dependencies using BFS and in-degree counts.

Use when you have a directed acyclic graph and want to order nodes respecting dependencies.

The key insight is to always process nodes with zero unmet prerequisites and update neighbors accordingly.

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