Skip to main content

Command Palette

Search for a command to run...

toposort bfs

Published
1 min readView as Markdown
public static ArrayList<Integer> topoSort(int V, int[][] edges){
    int indegree[] = new int[V]; // Step 1: In-degree array
    ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
    for(int i = 0; i < V; i++) adj.add(new ArrayList<>());

    // Step 2: Build adjacency list and in-degree
    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        adj.get(u).add(v);
        indegree[v]++;
    }
    // Step 3: Enqueue nodes with in-degree 0
    Queue<Integer> q = new LinkedList<>();
    for(int i = 0; i < V; i++) {
        if(indegree[i] == 0) q.offer(i);
    }
    // Step 4: Process queue
    ArrayList<Integer> res = new ArrayList<>();
    while(!q.isEmpty()) {
        int node = q.poll();
        res.add(node);
        for(int n: adj.get(node)) {
            indegree[n]--;
            if(indegree[n] == 0) q.offer(n);
        }
    }
    return res;
}

More from this blog

Amit singh's blog

235 posts