Topological Sort Using Kahn's Algorithm BFS in DSA C - Build from Scratch

Topological Sort Using Kahn's Algorithm BFS

📖 Scenario: Imagine you are managing tasks in a project where some tasks must be done before others. You want to find an order to do all tasks without breaking any rules.

🎯 Goal: Build a program in C that uses Kahn's Algorithm with BFS to find a valid order of tasks (topological sort) from given dependencies.

📋 What You'll Learn

Create an adjacency list to represent the directed graph of tasks

Create an array to store the in-degree (number of incoming edges) for each task

Use a queue to process tasks with zero in-degree

Implement Kahn's Algorithm to find the topological order

Print the topological order of tasks

💡 Why This Matters

🌍 Real World

Topological sorting is used in project scheduling, build systems, and resolving dependencies in software packages.

💼 Career

Understanding topological sort helps in roles like software development, project management, and systems engineering where task ordering and dependency resolution are critical.

1

Create the graph representation

Create an adjacency list called graph as an array of integer arrays with size 6, and an integer array called in_degree of size 6 initialized to 0.

DSA C

# Create the adjacency list array 'graph' and the in-degree array 'in_degree' of size 6
# Your code here

Hint

Use a 2D array for graph and a 1D array for in_degree, both of size 6.

2

Add edges and compute in-degree

Add edges to graph to represent these dependencies: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1. Update the in_degree array accordingly for each edge.

DSA C

#include 
#include 

#define N 6

int graph[N][N] = {0};
int in_degree[N] = {0};

int main() {
    // Add edges and update in-degree
    // Your code here
    return 0;
}

Hint

For each edge u->v, set graph[u][v] = 1 and increment in_degree[v].

3

Implement Kahn's Algorithm BFS

Create an integer array queue of size 6 and two integers front and rear initialized to 0. Enqueue all nodes with in_degree 0. Then, use a while loop to dequeue nodes, add them to topo_order array, and reduce in-degree of their neighbors, enqueueing neighbors when their in-degree becomes 0.

DSA C

#include 
#include 

#define N 6

int graph[N][N] = {0};
int in_degree[N] = {0};

int main() {
    graph[5][2] = 1; in_degree[2]++;
    graph[5][0] = 1; in_degree[0]++;
    graph[4][0] = 1; in_degree[0]++;
    graph[4][1] = 1; in_degree[1]++;
    graph[2][3] = 1; in_degree[3]++;
    graph[3][1] = 1; in_degree[1]++;

    int queue[N];
    int front = 0, rear = 0;
    int topo_order[N];
    int index = 0;

    // Your code here

    return 0;
}

Hint

Use a queue to process nodes with zero in-degree and update neighbors' in-degree inside the while loop.

4

Print the topological order

Print the elements of the topo_order array separated by spaces in a single line.

DSA C

#include 
#include 

#define N 6

int graph[N][N] = {0};
int in_degree[N] = {0};

int main() {
    graph[5][2] = 1; in_degree[2]++;
    graph[5][0] = 1; in_degree[0]++;
    graph[4][0] = 1; in_degree[0]++;
    graph[4][1] = 1; in_degree[1]++;
    graph[2][3] = 1; in_degree[3]++;
    graph[3][1] = 1; in_degree[1]++;

    int queue[N];
    int front = 0, rear = 0;
    int topo_order[N];
    int index = 0;

    for (int i = 0; i < N; i++) {
        if (in_degree[i] == 0) {
            queue[rear++] = i;
        }
    }

    while (front < rear) {
        int u = queue[front++];
        topo_order[index++] = u;

        for (int v = 0; v < N; v++) {
            if (graph[u][v]) {
                in_degree[v]--;
                if (in_degree[v] == 0) {
                    queue[rear++] = v;
                }
            }
        }
    }

    // Print the topological order
    // Your code here

    return 0;
}

Hint

Use a for loop to print each element of topo_order separated by spaces.

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