Kahn’s Algorithm in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
#define N 6
int main() {
    int g[N][N] = {{0,1,1,0,0,0},{0,0,0,1,1,0},{0,0,0,0,1,0},
                   {0,0,0,0,0,1},{0,0,0,0,0,1},{0,0,0,0,0,0}};
    int in[N] = {0}, q[N], front = 0, rear = 0;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) in[j] += g[i][j];
    for (int i = 0; i < N; i++) if (in[i] == 0) q[rear++] = i;
    while (front < rear) {
        int u = q[front++]; printf("%d ", u);
        for (int v = 0; v < N; v++) if (g[u][v] && --in[v] == 0) q[rear++] = v;
    }
}

C Output

Input:
Graph edges: 0→1, 0→2, 1→3, 1→4, 2→4, 3→5, 4→5
Output:
Input: Adjacency matrix, Source nodes with in-degree 0
Output: 0 1 2 3 4 5

C++ Program

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
    int n = 6;
    vector<vector<int>> g = {{1,2},{3,4},{4},{5},{5},{}};
    vector<int> in(n);
    for (auto u : g) for (int v : u) in[v]++;
    queue<int> q;
    for (int i = 0; i < n; i++) if (!in[i]) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";
        for (int v : g[u]) if (--in[v] == 0) q.push(v);
    }
}

C++ Output

Input:
Graph edges: 0→1, 0→2, 1→3, 1→4, 2→4, 3→5, 4→5
Output:
Input: Adjacency list, Source = 0
Output: 0 1 2 3 4 5

JAVA Program

import java.util.*;
class Main {
    public static void main(String[] args) {
        int n = 5;
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        g.get(0).add(2); g.get(0).add(3); g.get(1).add(3); g.get(2).add(4);
        int[] in = new int[n];
        for (List<Integer> u : g) for (int v : u) in[v]++;
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) if (in[i] == 0) q.add(i);
        while (!q.isEmpty()) {
            int u = q.poll();
            System.out.print(u + " ");
            for (int v : g.get(u)) if (--in[v] == 0) q.add(v);
        }
    }
}

JAVA Output

Input:
Graph edges: 0→2, 0→3, 1→3, 2→4
Output:
Input: List of dependencies
Output: 0 1 2 3 4

Python Program

from collections import deque
g = {0: [1, 2], 1: [3], 2: [3], 3: []}
in_deg = {u: 0 for u in g}
for u in g: 
    for v in g[u]: in_deg[v] += 1
q = deque([u for u in g if in_deg[u] == 0])
res = []
while q:
    u = q.popleft(); res.append(u)
    for v in g[u]:
        in_deg[v] -= 1
        if in_deg[v] == 0: q.append(v)
print(*res)

Python Output

Input:
Graph edges: 0→1, 0→2, 1→3, 2→3
Output:
Input: In-degree initialized graph
Output: 0 1 2 3

In-Depth Explanation

Example

Let's consider the C++ example:

0 → 1, 2  

1 → 3, 4  

2 → 4  

3 → 5  

4 → 5

Nodes 0 and 1 should appear before 3, and 3 and 4 should appear before 5.

Kahn's Algorithm detects all 0 in-degree nodes, begins from there, and slowly "eliminates" edges by reducing the in-degree of their neighbors. When the in-degree of any node reduces to 0, it's enqueued for processing.

Real-Life Analogy

Consider a planner for college courses. Certain courses have prerequisites. You can only enroll in "Data Structures" after "Programming Basics," and in "Algorithms" after "Data Structures." Kahn's Algorithm orders the courses in such a way that it meets all these chains of dependencies.

Why It Matters

Topological sorting comes into play when:

You're working with tasks that are dependent on each other

You want to schedule items which need to obey certain rules

You're constructing compiler dependency graphs or workflow pipelines

Kahn's Algorithm employs BFS and in-degrees, thus making it efficient and intuitive compared to DFS-based topological sorting.

Learning Insights

You learn:

Graph traversal using queues and in-degree arrays

Real-world application of dependency resolution

Difference between Kahn's (BFS) and DFS-based topological sort

This also emphasizes the fact that elimination of constraints (in-degree reduces to 0) allows progress.

Interview & Real-World Application

Kahn's Algorithm is a popular interview question, particularly in:

DAG-related problems

Course scheduling

Task execution order

Build systems and dependency managers

Used in

Makefile/build tools (determining compilation order)

Package managers (such as npm, pip)

Database systems (resolving joins or foreign keys)

Task scheduling engines

Kahn's Algorithm provides an efficient and useful method of determining the order of execution of tasks that have dependencies on other tasks. It's commonly applied in compilers, build processes, and course prerequisite verifiers. Unlike DFS-based sorts, Kahn's is based on the easy-to-understand queue data structure. The clean implementations in C, C++, Java, and Python assist you in developing a bulletproof understanding of how in-degree manipulation and dependency resolution are done in real-world scenarios. This algorithm is an interview code must-know for solving problems related to job scheduling, DAGs, and system design.