Topological Sort Using Kahn's Algorithm BFS in DSA C

Mental Model

We order tasks so that each task comes after all tasks it depends on. We do this by repeatedly picking tasks with no remaining dependencies.

Analogy: Imagine you have to bake a cake, but you must first prepare the batter and preheat the oven. You can only do a step when all its prerequisites are done. Kahn's algorithm finds the order to do all steps without breaking any rules.

Graph:
0 -> 1 -> 3
↓
2

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

Queue initially holds nodes with in-degree 0:
[0]

Dry Run Walkthrough

Input: Graph edges: 0->1, 0->2, 1->3, 2->3; nodes = 4

Goal: Find a linear order of nodes so that every edge u->v means u comes before v

Step 1: Calculate in-degree for each node

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

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

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

Queue: [0]

Why: Only nodes with no dependencies can be processed first

Step 3: Remove node 0 from queue and add to result

Result: 0
Queue: []

Why: Process node 0 as it has no dependencies

Step 4: Decrease in-degree of neighbors 1 and 2 by 1

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

Why: Removing 0 means its neighbors have one less dependency

Step 5: Add nodes 1 and 2 with in-degree 0 to queue

Queue: [1, 2]

Why: Now nodes 1 and 2 have no dependencies and can be processed

Step 6: Remove node 1 from queue and add to result

Result: 0 -> 1
Queue: [2]

Why: Process node 1 next

Step 7: Decrease in-degree of neighbor 3 by 1

In-degree array: [3]=1

Why: Removing 1 reduces dependencies of 3

Step 8: Remove node 2 from queue and add to result

Result: 0 -> 1 -> 2
Queue: []

Why: Process node 2 next

Step 9: Decrease in-degree of neighbor 3 by 1

In-degree array: [3]=0

Why: Removing 2 reduces dependencies of 3 to zero

Step 10: Add node 3 to queue

Queue: [3]

Why: Node 3 now has no dependencies

Step 11: Remove node 3 from queue and add to result

Result: 0 -> 1 -> 2 -> 3
Queue: []

Why: Process last node 3

Result:

Final topological order: 0 -> 1 -> 2 -> 3

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 100

// Queue structure for BFS
typedef struct {
    int items[MAX_NODES];
    int front, rear;
} Queue;

void initQueue(Queue* q) {
    q->front = 0;
    q->rear = -1;
}

int isEmpty(Queue* q) {
    return q->rear < q->front;
}

void enqueue(Queue* q, int val) {
    q->items[++q->rear] = val;
}

int dequeue(Queue* q) {
    return q->items[q->front++];
}

// Graph adjacency list
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* createNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

void addEdge(Node* adj[], int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = adj[src];
    adj[src] = newNode;
}

void kahnTopologicalSort(Node* adj[], int n) {
    int inDegree[MAX_NODES] = {0};
    int i;

    // Calculate in-degree of each node
    for (i = 0; i < n; i++) {
        Node* temp = adj[i];
        while (temp) {
            inDegree[temp->vertex]++;
            temp = temp->next;
        }
    }

    Queue q;
    initQueue(&q);

    // Enqueue nodes with in-degree 0
    for (i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            enqueue(&q, i);
        }
    }

    int count = 0;
    int topOrder[MAX_NODES];

    while (!isEmpty(&q)) {
        int u = dequeue(&q); // Remove node with no dependencies
        topOrder[count++] = u;

        // Decrease in-degree of neighbors
        Node* temp = adj[u];
        while (temp) {
            inDegree[temp->vertex]--;
            if (inDegree[temp->vertex] == 0) {
                enqueue(&q, temp->vertex);
            }
            temp = temp->next;
        }
    }

    // Check if there was a cycle
    if (count != n) {
        printf("Graph has a cycle, topological sort not possible\n");
        return;
    }

    // Print topological order
    for (i = 0; i < count; i++) {
        printf("%d", topOrder[i]);
        if (i != count - 1) printf(" -> ");
    }
    printf("\n");
}

int main() {
    int n = 4;
    Node* adj[MAX_NODES] = {NULL};

    addEdge(adj, 0, 1);
    addEdge(adj, 0, 2);
    addEdge(adj, 1, 3);
    addEdge(adj, 2, 3);

    kahnTopologicalSort(adj, n);

    return 0;
}

for (i = 0; i < n; i++) { Node* temp = adj[i]; while (temp) { inDegree[temp->vertex]++; temp = temp->next; } }

Calculate in-degree of each node by counting incoming edges

for (i = 0; i < n; i++) { if (inDegree[i] == 0) { enqueue(&q, i); } }

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

while (!isEmpty(&q)) { int u = dequeue(&q); topOrder[count++] = u;

Remove node with no dependencies and add to topological order

Node* temp = adj[u]; while (temp) { inDegree[temp->vertex]--; if (inDegree[temp->vertex] == 0) { enqueue(&q, temp->vertex); } temp = temp->next; }

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

if (count != n) { printf("Graph has a cycle, topological sort not possible\n"); return; }

Detect cycle if not all nodes are processed

Output

0 -> 1 -> 2 -> 3

Complexity Analysis

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

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

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

Algorithm detects cycle because not all nodes get processed; prints error message

DSA C

if (count != n) {
    printf("Graph has a cycle, topological sort not possible\n");
    return;
}

Graph with single node and no edges

Node has in-degree 0, gets processed immediately, output is that single node

DSA C

for (i = 0; i < n; i++) {
    if (inDegree[i] == 0) {
        enqueue(&q, i);
    }
}

Graph with multiple disconnected components

All nodes with zero in-degree from all components get processed in order, producing a valid topological order

DSA C

for (i = 0; i < n; i++) {
    if (inDegree[i] == 0) {
        enqueue(&q, i);
    }
}

When to Use This Pattern

When you need to order tasks with dependencies and want to detect cycles, use Kahn's algorithm BFS for topological sorting because it processes nodes with zero dependencies first.

Common Mistakes

Mistake: Not updating in-degree of neighbors after removing a node
Fix: Decrease in-degree of all neighbors and enqueue those whose in-degree becomes zero

Mistake: Not checking for cycles by comparing processed node count to total nodes
Fix: Add a check after BFS to detect if a cycle exists by verifying if all nodes were processed

Summary

Finds an order of nodes so all dependencies come before dependent nodes using BFS and in-degree counts.

Use when you have a directed acyclic graph and want to find a valid linear ordering of nodes.

The key insight is to repeatedly process nodes with zero in-degree and update neighbors' in-degree 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 find a topological ordering of a Directed Acyclic Graph (DAG)

C. To detect cycles in an undirected graph

D. To find the shortest path between two nodes

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 like shortest path, cycle detection, and minimum spanning tree solve different problems unrelated to topological sorting.

3. Final Answer:

   To find a topological ordering of a Directed Acyclic Graph (DAG) -> Option B

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 shortest path
• Thinking it detects cycles in undirected graphs
• Mixing it up with minimum spanning tree algorithms

2. Which data structure is primarily used in Kahn's Algorithm to keep track of nodes with zero incoming edges?

easy

A. Priority Queue

B. Stack

C. Queue

D. Hash Map

Solution

1. Step 1: Identify the data structure for zero in-degree nodes

   Kahn's Algorithm uses a queue to process nodes with zero incoming edges in a first-in-first-out manner, ensuring correct topological order.

2. Step 2: Why not other data structures?

   A stack would reverse the order, a priority queue is not necessary for basic Kahn's Algorithm, and a hash map stores key-value pairs, not order.

3. Final Answer:

   Queue -> Option C

4. Quick Check:

   Zero in-degree nodes stored in queue [OK]

Hint: Use queue for BFS order in Kahn's Algorithm [OK]

Common Mistakes:

• Using stack instead of queue
• Confusing priority queue with normal queue
• Thinking hash map manages order

3. Consider the directed graph with edges: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1. What is the topological order produced by Kahn's Algorithm?

medium

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

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

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

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

Solution

1. Step 1: Calculate in-degree of each node

   Nodes: 0(in-degree 2),1(2),2(1),3(1),4(0),5(0). Start with nodes 4 and 5 in queue (pushed in ascending order: queue [4,5]).

2. Step 2: Process nodes in queue and update in-degree

   Pop 4: output [4], reduce 0->1, 1->1. Queue: [5]
   Pop 5: output [4,5], reduce 2->0 (push 2), 0->0 (push 0). Queue: [2,0]
   Pop 2: output [4,5,2], reduce 3->0 (push 3). Queue: [0,3]
   Pop 0: output [4,5,2,0], no neighbors. Queue: [3]
   Pop 3: output [4,5,2,0,3], reduce 1->0 (push 1). Queue: [1]
   Pop 1: output [4,5,2,0,3,1]. All nodes processed.

3. Final Answer:

   [4, 5, 2, 0, 3, 1] -> Option A

4. Quick Check:

   Topological order = [4, 5, 2, 0, 3, 1] [OK]

Hint: Start with zero in-degree nodes, update neighbors' in-degree [OK]

Common Mistakes:

• Not updating in-degree after removing nodes
• Wrong initial zero in-degree nodes
• Mixing order of nodes in queue

4. Given the following code snippet for Kahn's Algorithm, what is the error?

int indegree[V] = {0};
for (int i = 0; i < V; i++) {
  for (int j = 0; j < adj[i].size(); j++) {
    indegree[adj[i][j]]++;
  }
}
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();
  cout << u << " ";
  for (int v : adj[u]) {
    indegree[v]--;
    if (indegree[v] == 0) q.push(v);
  }
}

medium

A. No error, the code is correct

B. The adjacency list is not declared properly

C. The indegree array is not initialized correctly

D. The loop to push zero indegree nodes is missing

Solution

1. Step 1: Check indegree initialization

   Indegree array is initialized to zero for all vertices correctly using {0} syntax.

2. Step 2: Verify adjacency list and loops

   Loops correctly calculate indegree, push zero indegree nodes, and process queue with BFS logic.

3. Final Answer:

   No error, the code is correct -> Option A

4. Quick Check:

   Code matches Kahn's Algorithm steps [OK]

Hint: Check initialization and loops carefully for correctness [OK]

Common Mistakes:

• Forgetting to initialize indegree array
• Incorrect adjacency list declaration
• Missing zero indegree node insertion

5. You have a graph with edges: 1->2, 1->3, 3->4, 2->4, 4->5, and 5->3. What will Kahn's Algorithm detect when run on this graph?

hard

A. A valid topological order exists

B. The algorithm will run infinitely without stopping

C. The graph is disconnected but topological order exists

D. The graph contains a cycle, so no topological order

Solution

1. Step 1: Identify cycle in the graph

   The edges 3->4, 4->5, and 5->3 form a cycle (3->4->5->3), so the graph is not a DAG.

2. Step 2: Understand Kahn's Algorithm behavior on cycles

   Kahn's Algorithm fails to process all nodes if a cycle exists because some nodes never reach zero in-degree, indicating no valid topological order.

3. Final Answer:

   The graph contains a cycle, so no topological order -> Option D

4. Quick Check:

   Cycle detected = no topological order [OK]

Hint: Cycle means no topological order in Kahn's Algorithm [OK]

Common Mistakes:

• Assuming topological order exists despite cycle
• Thinking disconnected graph always causes failure
• Believing algorithm runs infinitely on cycle