Topological Sort Using Kahn's Algorithm BFS in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kahn's Algorithm on a Simple DAG

What is the output of the following C# code implementing Kahn's Algorithm for topological sorting on the given graph?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int V = 4;
        List<int>[] graph = new List<int>[V];
        for (int i = 0; i < V; i++) graph[i] = new List<int>();
        graph[0].Add(1);
        graph[0].Add(2);
        graph[1].Add(2);
        graph[2].Add(3);

        int[] indegree = new int[V];
        for (int i = 0; i < V; i++) {
            foreach (var node in graph[i]) {
                indegree[node]++;
            }
        }

        Queue<int> q = new Queue<int>();
        for (int i = 0; i < V; i++) {
            if (indegree[i] == 0) q.Enqueue(i);
        }

        List<int> topoOrder = new List<int>();
        while (q.Count > 0) {
            int u = q.Dequeue();
            topoOrder.Add(u);
            foreach (var v in graph[u]) {
                indegree[v]--;
                if (indegree[v] == 0) q.Enqueue(v);
            }
        }

        Console.WriteLine(string.Join(" -> ", topoOrder) + " -> null");
    }
}

A 3 -> 2 -> 1 -> 0 -> null

B 0 -> 2 -> 1 -> 3 -> null

C 1 -> 0 -> 2 -> 3 -> null

D 0 -> 1 -> 2 -> 3 -> null

💡 Hint

Start with nodes having zero incoming edges and remove edges step by step.

The algorithm starts with nodes having zero indegree, which is node 0. Then it removes edges from 0 to 1 and 2, updating indegrees. Node 1 becomes zero indegree next, then node 2, and finally node 3. The order is 0 -> 1 -> 2 -> 3 -> null.

❓ Predict Output

intermediate

Detecting Cycle with Kahn's Algorithm

What will be the output of the following code snippet that attempts topological sorting on a graph with a cycle?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int V = 3;
        List<int>[] graph = new List<int>[V];
        for (int i = 0; i < V; i++) graph[i] = new List<int>();
        graph[0].Add(1);
        graph[1].Add(2);
        graph[2].Add(0); // cycle here

        int[] indegree = new int[V];
        for (int i = 0; i < V; i++) {
            foreach (var node in graph[i]) {
                indegree[node]++;
            }
        }

        Queue<int> q = new Queue<int>();
        for (int i = 0; i < V; i++) {
            if (indegree[i] == 0) q.Enqueue(i);
        }

        List<int> topoOrder = new List<int>();
        while (q.Count > 0) {
            int u = q.Dequeue();
            topoOrder.Add(u);
            foreach (var v in graph[u]) {
                indegree[v]--;
                if (indegree[v] == 0) q.Enqueue(v);
            }
        }

        if (topoOrder.Count != V) {
            Console.WriteLine("Cycle detected, topological sort not possible");
        } else {
            Console.WriteLine(string.Join(" -> ", topoOrder) + " -> null");
        }
    }
}

A 2 -> 1 -> 0 -> null

B 0 -> 1 -> 2 -> null

C Cycle detected, topological sort not possible

D 0 -> 2 -> 1 -> null

💡 Hint

If the number of nodes in the topological order is less than total nodes, a cycle exists.

The graph contains a cycle (0 -> 1 -> 2 -> 0). Kahn's algorithm cannot process all nodes, so the output indicates cycle detection.

🧠 Conceptual

advanced

Understanding Indegree Initialization in Kahn's Algorithm

In Kahn's Algorithm for topological sorting, why do we initialize the indegree array by counting incoming edges for each node before starting the BFS?

A To identify nodes with no incoming edges which can be starting points for the topological order

B To count the total number of edges in the graph

C To find nodes with the highest number of outgoing edges

D To sort the nodes in descending order of their values

💡 Hint

Think about which nodes can be safely placed first in the order.

Nodes with zero incoming edges have no dependencies and can be placed first in the topological order. Initializing indegree helps identify these nodes.

❓ Predict Output

advanced

Output of Kahn's Algorithm on a Graph with Multiple Valid Orders

Given the following graph, what is the output of the Kahn's Algorithm implementation below?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int V = 5;
        List<int>[] graph = new List<int>[V];
        for (int i = 0; i < V; i++) graph[i] = new List<int>();
        graph[0].Add(2);
        graph[1].Add(2);
        graph[1].Add(3);
        graph[3].Add(4);

        int[] indegree = new int[V];
        for (int i = 0; i < V; i++) {
            foreach (var node in graph[i]) {
                indegree[node]++;
            }
        }

        Queue<int> q = new Queue<int>();
        for (int i = 0; i < V; i++) {
            if (indegree[i] == 0) q.Enqueue(i);
        }

        List<int> topoOrder = new List<int>();
        while (q.Count > 0) {
            int u = q.Dequeue();
            topoOrder.Add(u);
            foreach (var v in graph[u]) {
                indegree[v]--;
                if (indegree[v] == 0) q.Enqueue(v);
            }
        }

        Console.WriteLine(string.Join(" -> ", topoOrder) + " -> null");
    }
}

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

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

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

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

💡 Hint

Nodes 0 and 1 have zero indegree initially; the queue order affects the output.

Initially, nodes 0 and 1 have zero indegree. The queue enqueues 0 first then 1 (due to loop order). Processing 0 then 1 leads to order 0 -> 1 -> 2 -> 3 -> 4 -> null.

🚀 Application

expert

Number of Valid Topological Orders in a DAG

Consider a DAG with 3 nodes and edges: 0->1 and 0->2. How many valid topological orders exist for this graph?

A 1

B 2

C 3

D 6

💡 Hint

Node 0 must come before 1 and 2, but 1 and 2 can be in any order.

Node 0 must come first. Nodes 1 and 2 can be in any order after 0. So valid orders are: 0->1->2 and 0->2->1, total 2.

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