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.