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

Mental Model

We find an order to do tasks so that all dependencies come before the task itself. We start with tasks that have no prerequisites and remove them step-by-step.

Analogy: Imagine you have a list of chores where some chores depend on others being done first. You start with chores that don't need anything done before them, finish those, then move on to chores that become free after finishing the first ones.

Graph nodes with arrows showing dependencies:

  A -> B -> D
  ↓         ↑
  C ---------

Start with nodes having no incoming arrows (A), then remove them and update.

Dry Run Walkthrough

Input: Graph edges: A->B, A->C, B->D, C->D

Goal: Find an order to complete tasks so that all dependencies come before the task

Step 1: Calculate in-degree (number of incoming edges) for each node: A=0, B=1, C=1, D=2

In-degree: A[0], B[1], C[1], D[2]
Queue: []

Why: We need to know which nodes have no prerequisites to start with

Step 2: Add nodes with in-degree 0 to queue: A

Queue: [A]

Why: Start processing nodes that can be done immediately

Step 3: Remove A from queue and add to result order

Order: [A]
Queue: []

Why: We complete A first

Step 4: Decrease in-degree of neighbors B and C by 1: B=0, C=0

In-degree: B[0], C[0], D[2]
Queue: []

Why: Removing A frees B and C to be done

Step 5: Add B and C to queue since their in-degree is now 0

Queue: [B, C]

Why: B and C can now be processed

Step 6: Remove B from queue and add to order

Order: [A, B]
Queue: [C]

Why: Process B next

Step 7: Decrease in-degree of neighbor D by 1: D=1

In-degree: D[1]
Queue: [C]

Why: B's completion reduces D's prerequisites

Step 8: Remove C from queue and add to order

Order: [A, B, C]
Queue: []

Why: Process C next

Step 9: Decrease in-degree of neighbor D by 1: D=0

In-degree: D[0]
Queue: []

Why: C's completion frees D

Step 10: Add D to queue

Queue: [D]

Why: D can now be processed

Step 11: Remove D from queue and add to order

Order: [A, B, C, D]
Queue: []

Why: Process last node D

Result:

Final order: A -> B -> C -> D -> null

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <string>

using namespace std;

class Graph {
public:
    unordered_map<string, vector<string>> adj;
    unordered_map<string, int> in_degree;

    void addEdge(const string& u, const string& v) {
        adj[u].push_back(v);
        if (in_degree.find(u) == in_degree.end()) in_degree[u] = 0;
        if (in_degree.find(v) == in_degree.end()) in_degree[v] = 0;
        in_degree[v]++;
    }

    vector<string> kahnTopologicalSort() {
        queue<string> q;
        vector<string> order;

        // Add all nodes with in-degree 0 to queue
        for (auto& pair : in_degree) {
            if (pair.second == 0) {
                q.push(pair.first);
            }
        }

        while (!q.empty()) {
            string u = q.front();
            q.pop();
            order.push_back(u);

            // Decrease in-degree of neighbors
            for (auto& v : adj[u]) {
                in_degree[v]--;
                if (in_degree[v] == 0) {
                    q.push(v);
                }
            }
        }

        // If order size != number of nodes, graph has a cycle
        if (order.size() != in_degree.size()) {
            return {};
        }

        return order;
    }
};

int main() {
    Graph g;
    g.addEdge("A", "B");
    g.addEdge("A", "C");
    g.addEdge("B", "D");
    g.addEdge("C", "D");

    vector<string> order = g.kahnTopologicalSort();

    if (order.empty()) {
        cout << "Graph has a cycle, no topological order." << endl;
    } else {
        for (auto& node : order) {
            cout << node << " -> ";
        }
        cout << "null" << endl;
    }

    return 0;
}

for (auto& pair : in_degree) { if (pair.second == 0) { q.push(pair.first); } }

Add all nodes with no prerequisites to the queue to start processing

while (!q.empty()) { string u = q.front(); q.pop(); order.push_back(u);

Process nodes in queue and add them to the topological order

for (auto& v : adj[u]) { in_degree[v]--; if (in_degree[v] == 0) { q.push(v); } }

Decrease in-degree of neighbors and add them to queue if they become free

if (order.size() != in_degree.size()) { return {}; }

Detect cycle if not all nodes are processed

Output

A -> B -> C -> D -> null

Complexity Analysis

Time: O(V + E) because we visit each node and edge once during the BFS traversal

Space: O(V + E) to store the graph and the in-degree map

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

Empty graph (no nodes)

Returns empty order immediately

DSA C++

if (order.size() != in_degree.size()) {
    return {};
}

Graph with cycle

Returns empty vector indicating no valid topological order

DSA C++

if (order.size() != in_degree.size()) {
    return {};
}

Graph with single node and no edges

Returns order with that single node

DSA C++

for (auto& pair : in_degree) {
    if (pair.second == 0) {
        q.push(pair.first);
    }
}

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 prerequisites first and updates dependencies stepwise.

Common Mistakes

Mistake: Not initializing in-degree for all nodes, causing missing nodes in the result
Fix: Initialize in-degree for all nodes, including those with zero incoming edges, before starting the algorithm

Mistake: Not checking for cycles by comparing processed nodes count with total nodes
Fix: Add a check after processing to detect cycles by comparing order size with total nodes

Summary

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

Use when you have a directed acyclic graph and want to order nodes so all prerequisites come first.

Start with nodes having zero incoming edges and remove them step-by-step, updating neighbors' in-degree.

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