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

↓

Initialize queue with nodes having in-degree 0

↓

While queue not empty

Yes↓

Pop node from queue

↓

Add node to topological order

↓

For each neighbor of node

↓

Decrease neighbor's in-degree by 1

↓

If neighbor's in-degree is 0, add to queue

↩Back to While queue not empty

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

Execution Sample

DSA C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Graph represented as adj list: A->B,C; F->E; B->D; C->D
    map<char, vector<char>> adj = {
        {'A', {'B', 'C'}},
        {'B', {'D'}},
        {'C', {'D'}},
        {'D', {}},
        {'E', {}},
        {'F', {'E'}}
    };
    vector<char> nodes = {'A','B','C','D','E','F'};
    map<char, int> indeg;
    for (char node : nodes) indeg[node] = 0;
    for (auto& p : adj) {
        for (char nei : p.second) {
            indeg[nei]++;
        }
    }
    // indeg: A:0 B:1 C:1 D:2 E:1 F:0
    queue<char> q;
    for (char node : nodes) {
        if (indeg[node] == 0) q.push(node);
    }
    vector<char> order;
    while (!q.empty()) {
        char node = q.front(); q.pop();
        order.push_back(node);
        for (char nei : adj[node]) {
            indeg[nei]--;
            if (indeg[nei] == 0) {
                q.push(nei);
            }
        }
    }
    // order: A F B C E D
    for (char n : order) cout << n << " ";
    cout << endl;
    return 0;
}

This C++ code performs topological sorting on the given directed acyclic graph (DAG) using Kahn's BFS algorithm with in-degree tracking. It outputs the topological order: A F B C E D

Execution Table

Step	Operation	Queue State	In-degree Map	Topological Order	Visual State
0	Calculate in-degree	[]	{A:0, B:1, C:1, D:2, E:1, F:0}	[]	Graph: A(0), B(1), C(1), D(2), E(1), F(0)
1	Initialize queue with in-degree 0 nodes	[A, F]	{A:0, B:1, C:1, D:2, E:1, F:0}	[]	Queue: A, F
2	Dequeue A	[F]	{A:0, B:1, C:1, D:2, E:1, F:0}	[A]	Removed A from queue
3	Decrease in-degree of neighbors B and C	[F]	{A:0, B:0, C:0, D:2, E:1, F:0}	[A]	B and C in-degree decreased
4	Enqueue B and C (in-degree 0)	[F, B, C]	{A:0, B:0, C:0, D:2, E:1, F:0}	[A]	Queue: F, B, C
5	Dequeue F	[B, C]	{A:0, B:0, C:0, D:2, E:1, F:0}	[A, F]	Removed F from queue
6	Decrease in-degree of neighbor E	[B, C]	{A:0, B:0, C:0, D:2, E:0, F:0}	[A, F]	E in-degree decreased
7	Enqueue E (in-degree 0)	[B, C, E]	{A:0, B:0, C:0, D:2, E:0, F:0}	[A, F]	Queue: B, C, E
8	Dequeue B	[C, E]	{A:0, B:0, C:0, D:2, E:0, F:0}	[A, F, B]	Removed B from queue
9	Decrease in-degree of neighbor D	[C, E]	{A:0, B:0, C:0, D:1, E:0, F:0}	[A, F, B]	D in-degree decreased
10	Dequeue C	[E]	{A:0, B:0, C:0, D:1, E:0, F:0}	[A, F, B, C]	Removed C from queue
11	Decrease in-degree of neighbor D	[E]	{A:0, B:0, C:0, D:0, E:0, F:0}	[A, F, B, C]	D in-degree decreased to 0
12	Enqueue D (in-degree 0)	[E, D]	{A:0, B:0, C:0, D:0, E:0, F:0}	[A, F, B, C]	Queue: E, D
13	Dequeue E	[D]	{A:0, B:0, C:0, D:0, E:0, F:0}	[A, F, B, C, E]	Removed E from queue
14	E has no neighbors	[D]	{A:0, B:0, C:0, D:0, E:0, F:0}	[A, F, B, C, E]	No in-degree changes
15	Dequeue D	[]	{A:0, B:0, C:0, D:0, E:0, F:0}	[A, F, B, C, E, D]	Removed D from queue
16	D has no neighbors	[]	{A:0, B:0, C:0, D:0, E:0, F:0}	[A, F, B, C, E, D]	No in-degree changes
17	Queue empty, end	[]	{A:0, B:0, C:0, D:0, E:0, F:0}	[A, F, B, C, E, D]	Topological order complete

💡 Queue is empty, all nodes processed, topological order found

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	After 11	After 12	After 13	After 14	After 15	Final
Queue	[]	[A, F]	[F]	[F]	[F, B, C]	[B, C]	[B, C]	[B, C, E]	[C, E]	[C, E]	[E]	[E]	[E, D]	[D]	[D]	[]	[]
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: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:2,E:1,F:0}	{A:0,B:0,C:0,D:2,E:1,F:0}	{A:0,B:0,C:0,D:2,E:0,F:0}	{A:0,B:0,C:0,D:2,E:0,F:0}	{A:0,B:0,C:0,D:2,E:0,F:0}	{A:0,B:0,C:0,D:1,E:0,F:0}	{A:0,B:0,C:0,D:1,E:0,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}	{A:0,B:0,C:0,D:0,E:0,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}	{A:0,B:0,C:0,D:0,E:0,F:0}
Topological Order	[]	[]	[A]	[A]	[A]	[A, F]	[A, F]	[A, F]	[A, F, B]	[A, F, B]	[A, F, B, C]	[A, F, B, C]	[A, F, B, C]	[A, F, B, C, E]	[A, F, B, C, E]	[A, F, B, C, E, D]	[A, F, B, C, E, D]

Key Moments - 3 Insights

Why do we start with nodes that have in-degree 0?

Nodes with in-degree 0 have no dependencies and can be placed first in the order. This is shown in execution_table row 1 where queue is initialized with these nodes.

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

Decreasing in-degree means one dependency is resolved. When in-degree reaches 0, the neighbor is ready to be processed, as seen in rows 3-4 and 6-7 where neighbors B, C, and E are enqueued.

Why does the algorithm stop when the queue is empty?

An empty queue means no nodes are left with zero in-degree to process. At this point, all nodes have been ordered, as shown in row 17 where the topological order is complete.

Visual Quiz - 3 Questions

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

A B, C

B A, F

C F, B, C

D F

💡 Hint

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

At which step does node D get enqueued?

A Step 11

B Step 12

C Step 10

D Step 13

💡 Hint

Look for when D appears in the 'Queue State' column in the execution_table

If node F had an in-degree of 1 initially, what would happen to the initial queue?

A Queue would start with A only

B Queue would start empty

C Queue would start with A and F

D Queue would start with F only

💡 Hint

Refer to the 'In-degree Map' and 'Queue State' at step 1 in the execution_table

Concept Snapshot

Topological Sort using Kahn's Algorithm (BFS):
- Calculate in-degree for 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
- Result is a valid topological order

Full Transcript

Kahn's algorithm for topological sort works by first calculating the in-degree (number of incoming edges) for each node in the graph. 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 any neighbor's in-degree becomes zero, it is added to the queue. This process continues until the queue is empty, meaning all nodes have been processed and a valid topological order is found. The execution table shows each step, the queue contents, in-degree map, and the growing topological order. Key moments include understanding why nodes with zero in-degree start the process, how in-degree decreases represent resolving dependencies, and why the algorithm stops when no nodes remain in the queue.

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