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

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

#define MAX 6

int main() {
    int indegree[MAX] = {0};
    int graph[MAX][MAX] = {
        {0, 1, 1, 0, 0, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 1, 1, 0},
        {0, 0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0, 0}
    };

    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            if (graph[i][j]) indegree[j]++;
        }
    }

    int queue[MAX], front = 0, rear = 0;
    for (int i = 0; i < MAX; i++) {
        if (indegree[i] == 0) queue[rear++] = i;
    }

    int count = 0;
    int topo_order[MAX];

    while (front < rear) {
        int u = queue[front++];
        topo_order[count++] = u;
        for (int v = 0; v < MAX; v++) {
            if (graph[u][v]) {
                indegree[v]--;
                if (indegree[v] == 0) queue[rear++] = v;
            }
        }
    }

    if (count != MAX) {
        printf("Cycle detected\n");
        return 1;
    }

    for (int i = 0; i < MAX; i++) {
        printf("%d", topo_order[i]);
        if (i != MAX - 1) printf(" -> ");
    }
    printf(" -> null\n");
    return 0;
}

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

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

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

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

💡 Hint

Look at the indegree array and how nodes with zero indegree are processed in order.

Kahn's algorithm processes nodes with zero indegree first. Node 0 has zero indegree and is processed first. Then nodes 1 and 2 become zero indegree. Node 1 is enqueued before node 2 because of the order in the loop. So the order is 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null.

🧠 Conceptual

intermediate

Understanding Indegree in Kahn's Algorithm

In Kahn's Algorithm for topological sorting, what does the 'indegree' of a node represent?

A The number of edges coming into the node

B The number of edges going out from the node

C The total number of edges connected to the node

D The number of nodes reachable from this node

💡 Hint

Indegree counts incoming edges.

Indegree is the count of edges directed into a node. Kahn's algorithm uses indegree to find nodes with no incoming edges to start the sorting.

🔧 Debug

advanced

Identify the Bug in Kahn's Algorithm Implementation

What error does the following code produce when running Kahn's Algorithm on a graph with a cycle?

DSA C

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

#define MAX 3

int main() {
    int indegree[MAX] = {0};
    int graph[MAX][MAX] = {
        {0, 1, 0},
        {0, 0, 1},
        {1, 0, 0}
    };

    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            if (graph[i][j]) indegree[j]++;
        }
    }

    int queue[MAX], front = 0, rear = 0;
    for (int i = 0; i < MAX; i++) {
        if (indegree[i] == 0) queue[rear++] = i;
    }

    int count = 0;
    int topo_order[MAX];

    while (front < rear) {
        int u = queue[front++];
        topo_order[count++] = u;
        for (int v = 0; v < MAX; v++) {
            if (graph[u][v]) {
                indegree[v]--;
                if (indegree[v] == 0) queue[rear++] = v;
            }
        }
    }

    if (count != MAX) {
        printf("Cycle detected\n");
        return 1;
    }

    for (int i = 0; i < MAX; i++) {
        printf("%d", topo_order[i]);
        if (i != MAX - 1) printf(" -> ");
    }
    printf(" -> null\n");
    return 0;
}

A The program enters an infinite loop

B The program prints a partial topological order and then terminates normally

C The program crashes with segmentation fault

D The program prints 'Cycle detected' and exits with code 1

💡 Hint

Check the condition when count is not equal to number of nodes.

The graph has a cycle, so not all nodes can be processed. The count will be less than MAX, triggering the cycle detection message and exit.

🚀 Application

advanced

Order of Nodes in Kahn's Algorithm with Multiple Zero Indegree Nodes

Given the graph below, which topological order will Kahn's Algorithm produce if nodes with zero indegree are enqueued in ascending order?

DSA C

Graph edges:
0 -> 2
1 -> 2
2 -> 3
3 -> 4
4 -> 5

Nodes: 0, 1, 2, 3, 4, 5

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

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

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

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

💡 Hint

Nodes 0 and 1 have zero indegree initially. Which is enqueued first?

Both 0 and 1 have zero indegree initially. Since nodes are enqueued in ascending order, 0 is enqueued before 1. So the order starts with 0 -> 1 -> ...

🧠 Conceptual

expert

Why Kahn's Algorithm Uses a Queue

Why does Kahn's Algorithm use a queue data structure to store nodes with zero indegree during topological sorting?

A To process nodes in reverse order of their indegree values

B To implement a depth-first search traversal of the graph

C To process nodes in the order they become zero indegree, ensuring BFS traversal

D To store nodes temporarily before sorting them by their values

💡 Hint

Think about the order nodes are processed and how BFS works.

Kahn's Algorithm uses a queue to process nodes in the order they become zero indegree, which is a breadth-first search approach. This ensures correct topological order.

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