Topological Sorting using BFS - Kahn's Algorithm

Last Updated : 31 Oct, 2025

Given a Directed Acyclic Graph having V vertices and E edges, find any Topological Sorted ordering of the graph.

Topological Sorted order: It is a linear ordering of vertices such that for every directed edge u -> v, vertex u comes before v in the ordering.

Example:

Input: adj[][] = [[1], [2], [], [2, 4], []]

Output: [0, 3, 1, 4, 2]
Explanation: For every pair of vertex(u -> v) in the ordering, u comes before v.
Input: adj[][]= [[1], [2], [3], [], [5], [1, 2]]

Output: [0, 4, 5, 1, 2, 3]
Explanation: For every pair of vertex(u -> v) in the ordering, u comes before v.

[Approach]

The idea is to use Kahn’s Algorithm, which applies BFS to generate a valid topological ordering.
We first compute the in-degree of every vertex — representing how many incoming edges each vertex has. Then, all vertices with an in-degree of 0 are added to a queue, as they can appear first in the ordering.
We repeatedly remove a vertex from the queue, add it to our result list, and reduce the in-degree of all its adjacent vertices. If any of those vertices now have an in-degree of 0, they are added to the queue.
This process continues until the queue is empty, and the resulting order represents one valid topological sort of the graph.

Illustration of the algorithm:

Below is the implementation of the above algorithm.

C++

//Driver Code Starts
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

//Driver Code Ends

vector<int> topoSort(vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> indegree(n, 0);
    queue<int> q;
    vector<int> list;

    // Compute indegrees
    for (int i = 0; i < n; i++) {
        for (int next : adj[i])
            indegree[next]++;
    }

    // Add all nodes with indegree 0 
    // into the queue
    for (int i = 0; i < n; i++)
        if (indegree[i] == 0)
            q.push(i);

    // Kahn’s Algorithm (BFS)
    while (!q.empty()) {
        int top = q.front();
        q.pop();
        list.push_back(top);
        for (int next : adj[top]) {
            indegree[next]--;
            if (indegree[next] == 0)
                q.push(next);
        }
    }

    return list;
}

//Driver Code Starts

void addEdge(vector<vector<int>>& adj, int u, int v) {
    adj[u].push_back(v);
}

int main() {
    int n =6;
    vector<vector<int>> adj(n);
    
    addEdge(adj, 0, 1);
    addEdge(adj, 1, 2);
    addEdge(adj, 2, 3);
    addEdge(adj, 4, 5);
    addEdge(adj, 5, 1);
    addEdge(adj, 5, 2);

    vector<int> res = topoSort(adj);
    for (int vertex : res)
        cout << vertex << " ";
    cout << endl;
}

//Driver Code Ends

Java

//Driver Code Starts
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

class GFG {
//Driver Code Ends

    static ArrayList<Integer> topoSort(ArrayList<ArrayList<Integer>> adj) {
        int n = adj.size();
        int[] indegree = new int[n];
        Queue<Integer> q = new LinkedList<>();
        ArrayList<Integer> result = new ArrayList<>();

        // Compute indegrees
        for (int i = 0; i < n; i++) {
            for (int next : adj.get(i)) {
                indegree[next]++;
            }
        }

        // Add all nodes with indegree 0 
        // into the queue
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                q.add(i);
            }
        }

        // Kahn’s Algorithm (BFS)
        while (!q.isEmpty()) {
            int top = q.poll();
            result.add(top);
            for (int next : adj.get(top)) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.add(next);
                }
            }
        }

        return result;
    }

//Driver Code Starts

    static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) {
        adj.get(u).add(v);
    }

    public static void main(String[] args) {
        int n = 6;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        addEdge(adj, 0, 1);
        addEdge(adj, 1, 2);
        addEdge(adj, 2, 3);
        addEdge(adj, 4, 5);
        addEdge(adj, 5, 1);
        addEdge(adj, 5, 2);

        ArrayList<Integer> res = topoSort(adj);
        for (int vertex : res) {
            System.out.print(vertex + " ");
        }
        System.out.println();
    }
}

//Driver Code Ends

Python

#Driver Code Starts
from collections import deque

#Driver Code Ends

def topoSort(adj):
    n = len(adj)
    indegree = [0] * n
    res = []
    queue = deque()

    # Compute indegrees
    for i in range(n):
        for next_node in adj[i]:
            indegree[next_node] += 1
            
    # Add all nodes with indegree 0 
    # into the queue
    for i in range(n):
        if indegree[i] == 0:
            queue.append(i)

    # Kahn’s Algorithm
    while queue:
        top = queue.popleft()
        res.append(top)
        for next_node in adj[top]:
            indegree[next_node] -= 1
            if indegree[next_node] == 0:
                queue.append(next_node)

    return res

def addEdge(adj, u, v):
    adj[u].append(v)

#Driver Code Starts

# Example
n = 6
adj = [[] for _ in range(n)]

addEdge(adj, 0, 1)
addEdge(adj, 1, 2)
addEdge(adj, 2, 3)
addEdge(adj, 4, 5)
addEdge(adj, 5, 1)
addEdge(adj, 5, 2)

res = topoSort(adj)
print(*res)
#Driver Code Ends

//Driver Code Starts
using System;
using System.Collections.Generic;

class GFG {
//Driver Code Ends

    public static List<int> topoSort(List<List<int>> adj) {
        int n = adj.Count;
        int[] indegree = new int[n];
        List<int> list = new List<int>();
        Queue<int> queue = new Queue<int>();

        // Compute indegrees
        for (int i = 0; i < n; i++) {
            foreach (int next in adj[i])
                indegree[next]++;
        }

        // Add all nodes with indegree 0 
        // into the queue
        for (int i = 0; i < n; i++)
            if (indegree[i] == 0)
                queue.Enqueue(i);

        // Kahn’s Algorithm (BFS)
        while (queue.Count > 0) {
            int top = queue.Dequeue();
            list.Add(top);
            foreach (int next in adj[top]) {
                indegree[next]--;
                if (indegree[next] == 0)
                    queue.Enqueue(next);
            }
        }

        return list;
    }

//Driver Code Starts

    public static void addEdge(List<List<int>> adj, int u, int v) {
        adj[u].Add(v);
    }

    public static void Main() {
        int n = 6;
        List<List<int>> adj = new List<List<int>>();
        for (int i = 0; i < n; i++)
            adj.Add(new List<int>());

        addEdge(adj, 0, 1);
        addEdge(adj, 1, 2);
        addEdge(adj, 2, 3);
        addEdge(adj, 4, 5);
        addEdge(adj, 5, 1);
        addEdge(adj, 5, 2);

        List<int> res = topoSort(adj);
        Console.WriteLine(string.Join(" ", res));
    }
}
//Driver Code Ends

JavaScript

function topoSort(adj) {
    n = adj.length
    let indegree = new Array(n).fill(0);
    let queue = [];
    let res = [];

    // Compute indegrees
    for (let i = 0; i < n; i++) {
        for (let next of adj[i]) indegree[next]++;
    }

    // Add all nodes with indegree 0 
    // into the queue
    for (let i = 0; i < n; i++) {
        if (indegree[i] === 0) queue.push(i);
    }

    // Kahn’s Algorithm
    while (queue.length > 0) {
        let top = queue.shift();
        res.push(top);
        for (let next of adj[top]) {
            indegree[next]--;
            if (indegree[next] === 0) queue.push(next);
        }
    }

    return res;
}


//Driver Code Starts
function addEdge(adj, u, v) {
    adj[u].push(v);
}

// Example
let n = 6;
let adj = Array.from({ length: n }, () => []);

addEdge(adj, 0, 1);
addEdge(adj, 1, 2);
addEdge(adj, 2, 3);
addEdge(adj, 4, 5);
addEdge(adj, 5, 1);
addEdge(adj, 5, 2);

let res = topoSort(adj);
console.log(...res);
//Driver Code Ends

Output

0 4 5 1 2 3

Time Complexity: O(V+E). For Performing BFS
Auxiliary Space: O(V).

kartik

Improve

Article Tags :

Topological Sorting using BFS - Kahn's Algorithm

[Approach]

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem

Thank You!

What kind of Experience do you want to share?