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 order of nodes after running Kahn's Algorithm BFS on the given graph?

DSA C++

/* Graph edges:
0 -> 1
0 -> 2
1 -> 3
2 -> 3
*/

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    int V = 4;
    vector<vector<int>> adj(V);
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(3);

    vector<int> indegree(V, 0);
    for (int i = 0; i < V; i++) {
        for (int node : adj[i]) {
            indegree[node]++;
        }
    }

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

    vector<int> topo_order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo_order.push_back(u);
        for (int v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0) q.push(v);
        }
    }

    for (int node : topo_order) {
        cout << node << " ";
    }
    cout << endl;
    return 0;
}

A 0 1 2 3

B 0 2 1 3

C 1 0 2 3

D 3 1 2 0

💡 Hint

Start with nodes having zero incoming edges and process neighbors by reducing their indegree.

Kahn's algorithm starts with nodes having zero indegree. Here, node 0 has zero indegree. After processing 0, nodes 1 and 2 become zero indegree and are added to the queue. The order depends on queue insertion order, so 1 is processed before 2, resulting in 0 1 2 3.

❓ Predict Output

intermediate

Detecting Cycle with Kahn's Algorithm

What will be the output of the following code that uses Kahn's Algorithm BFS on a graph with a cycle?

DSA C++

/* Graph edges:
0 -> 1
1 -> 2
2 -> 0 (cycle)
*/

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    int V = 3;
    vector<vector<int>> adj(V);
    adj[0].push_back(1);
    adj[1].push_back(2);
    adj[2].push_back(0);

    vector<int> indegree(V, 0);
    for (int i = 0; i < V; i++) {
        for (int node : adj[i]) {
            indegree[node]++;
        }
    }

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

    vector<int> topo_order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo_order.push_back(u);
        for (int v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0) q.push(v);
        }
    }

    if ((int)topo_order.size() != V) {
        cout << "Cycle detected" << endl;
    } else {
        for (int node : topo_order) {
            cout << node << " ";
        }
        cout << endl;
    }
    return 0;
}

A Cycle detected

B 0 1 2

C 1 2 0

D 2 0 1

💡 Hint

If the number of nodes processed is less than total nodes, a cycle exists.

Kahn's algorithm cannot process nodes in a cycle because their indegree never becomes zero. Here, no node has zero indegree initially, so the queue is empty and no nodes are processed. The algorithm detects a cycle and prints Cycle detected.

🔧 Debug

advanced

Identify the Bug in Kahn's Algorithm Implementation

The following code attempts to perform topological sort using Kahn's Algorithm BFS but produces incorrect output. What is the bug?

DSA C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    int V = 3;
    vector<vector<int>> adj(V);
    adj[0].push_back(1);
    adj[1].push_back(2);

    vector<int> indegree(V, 0);
    for (int i = 0; i < V; i++) {
        for (int node : adj[i]) {
            indegree[i]++;
        }
    }

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

    vector<int> topo_order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo_order.push_back(u);
        for (int v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0) q.push(v);
        }
    }

    for (int node : topo_order) {
        cout << node << " ";
    }
    cout << endl;
    return 0;
}

A The queue is not initialized with nodes having zero indegree

B The indegree calculation increments indegree[i] instead of indegree[node]

C The adjacency list is empty, so no edges exist

D The topo_order vector is not printed correctly

💡 Hint

Check how indegree is updated inside the nested loop.

The bug is in the indegree calculation loop. It increments indegree[i] for each neighbor, but it should increment indegree[node] because node is the destination of the edge. This causes wrong indegree counts and incorrect processing order.

❓ Predict Output

advanced

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

Given the graph below, what is the output of Kahn's Algorithm BFS? Note that multiple valid topological orders exist, but the algorithm uses a queue and processes nodes in ascending order of their indices when indegree is zero.

DSA C++

/* Graph edges:
0 -> 2
1 -> 2
2 -> 3
*/

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    int V = 4;
    vector<vector<int>> adj(V);
    adj[0].push_back(2);
    adj[1].push_back(2);
    adj[2].push_back(3);

    vector<int> indegree(V, 0);
    for (int i = 0; i < V; i++) {
        for (int node : adj[i]) {
            indegree[node]++;
        }
    }

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

    vector<int> topo_order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo_order.push_back(u);
        for (int v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0) q.push(v);
        }
    }

    for (int node : topo_order) {
        cout << node << " ";
    }
    cout << endl;
    return 0;
}

A 2 0 1 3

B 1 0 2 3

C 0 2 1 3

D 0 1 2 3

💡 Hint

Nodes 0 and 1 have zero indegree initially; the queue processes 0 first because it has smaller index.

Initially, nodes 0 and 1 have zero indegree and are added to the queue in order 0 then 1. The algorithm processes 0 first, then 1, then 2, then 3. So the output is 0 1 2 3.

🧠 Conceptual

expert

Why Kahn's Algorithm Detects Cycles in Directed Graphs

Which statement best explains why Kahn's Algorithm BFS can detect cycles in a directed graph?

A Because the algorithm sorts nodes by their values and detects duplicates as cycles.

B Because the algorithm uses a depth-first search to find back edges indicating cycles.

C Because nodes in a cycle never have their indegree reduced to zero, so they are never processed, resulting in fewer nodes in the topological order than total nodes.

D Because the algorithm removes edges randomly and checks if any nodes remain isolated.

💡 Hint

Think about what happens to nodes in a cycle regarding their indegree.

Kahn's Algorithm works by repeatedly removing nodes with zero indegree. In a cycle, nodes always have at least one incoming edge, so their indegree never becomes zero. Hence, they are never processed, and the final topological order has fewer nodes than the graph, indicating a cycle.

Practice

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

easy

A. To find the shortest path between two nodes

B. To calculate the minimum spanning tree

C. To detect cycles in an undirected graph

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 algorithms: shortest path (Dijkstra's or BFS), cycle detection in undirected graphs (DFS), and minimum spanning tree (Kruskal's or Prim's) are unrelated to 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 topological order in DAGs [OK]

Common Mistakes:

• Confusing topological sort with shortest path
• Thinking it works on undirected graphs
• Assuming it detects cycles directly

2. Which of the following C++ STL containers is best suited to implement the queue used in Kahn's Algorithm?

easy

A. std::queue

B. std::set

C. std::vector

D. std::stack

Solution

1. Step 1: Identify the data structure needed

   Kahn's Algorithm uses a queue to process nodes with zero incoming edges in FIFO order.

2. Step 2: Match with C++ STL containers

   std::queue provides FIFO behavior, suitable for this purpose. std::stack is LIFO, std::vector is dynamic array without FIFO, std::set is ordered but not FIFO.

3. Final Answer:

   std::queue -> Option A

4. Quick Check:

   Queue = std::queue [OK]

Hint: Use std::queue for FIFO processing in Kahn's Algorithm [OK]

Common Mistakes:

• Using std::stack instead of std::queue
• Using std::vector without queue operations
• Using std::set which is ordered but not FIFO

3. What is the output of the following code snippet implementing Kahn's Algorithm on the graph with edges: 5->0, 5->2, 4->0, 4->1, 2->3, 3->1?

std::vector graph = {{}, {}, {}, {}, {}, {}};
// Edges added as graph[5].push_back(0), etc.
// After running Kahn's Algorithm, which topological order is printed?
// Options are sequences of node numbers.

medium

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

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

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

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

Solution

1. Step 1: Build indegree and initialize queue

   Nodes 4 and 5 have zero indegree, so queue starts with [4,5].

2. Step 2: Process nodes in queue order

   Process 4: remove edges 4->0, 4->1; indegree of 0 and 1 decrease. Process 5: remove edges 5->0, 5->2; indegree of 0 and 2 decrease. When indegree of 0 and 2 become zero, add to queue. Continue processing 0, 2, 3, 1 in order.

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 nodes having zero indegree in queue [OK]

Common Mistakes:

• Starting queue with wrong nodes
• Not updating indegree correctly
• Mixing order of nodes with zero indegree

4. What is missing from this Kahn's Algorithm implementation:

std::vector<int> indegree(V, 0);
for (int u = 0; u < V; u++) {
  for (int v : graph[u]) {
    indegree[v]++;
  }
}
std::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();
  for (int v : graph[u]) {
    indegree[v]--;
    if (indegree[v] == 0) q.push(v);
  }
  // Missing code here
}

medium

A. Not decrementing indegree[v] inside the loop

B. Not printing or storing the topological order nodes

C. Not checking if the graph has cycles before running

D. Not pushing nodes with zero indegree into the queue initially

Solution

1. Step 1: Analyze the loop behavior

   The code correctly calculates indegree and pushes zero indegree nodes into the queue. It decrements indegree and pushes new zero indegree nodes inside the loop.

2. Step 2: Identify missing action

   The missing code is to store the popped node u into a topological order vector, e.g., topo.push_back(u); after q.pop();. Without it, the algorithm processes correctly but does not output the order.

3. Final Answer:

   Not printing or storing the topological order nodes -> Option B

4. Quick Check:

   Missing topo.push_back(u) [OK]

Hint: Always record nodes when popping from queue [OK]

Common Mistakes:

• Forgetting to store or print topological order
• Incorrect indegree decrement logic
• Not initializing queue with zero indegree nodes

5. Given a Directed Acyclic Graph (DAG) with 6 nodes and edges: 0->1, 0->2, 1->3, 2->3, 3->4, 4->5, how can Kahn's Algorithm be modified to detect if the graph contains a cycle?

hard

A. Count processed nodes; if count < total nodes, a cycle exists

B. Check if queue becomes empty

C. Use a visited array to mark nodes and detect back edges

D. Run DFS instead of BFS to find cycles

Solution

1. Step 1: Understand Kahn's Algorithm processing

   Kahn's Algorithm processes nodes with zero indegree and removes edges. If a cycle exists, some nodes never reach zero indegree and remain unprocessed.

2. Step 2: Detect cycle by counting processed nodes

   If the number of processed nodes is less than total nodes, it means some nodes are stuck due to cycles. This is a standard cycle detection method using Kahn's Algorithm.

3. Final Answer:

   Count processed nodes; if count < total nodes, a cycle exists -> Option A

4. Quick Check:

   Processed nodes count < total nodes = cycle [OK]

Hint: Compare processed nodes count with total nodes [OK]

Common Mistakes:

• Assuming Kahn's Algorithm alone detects cycles without counting
• Confusing BFS with DFS cycle detection methods
• Not tracking processed nodes count