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.