Topological Sort

Topological Sort produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u → v, vertex u comes before v in the ordering. If the graph has a cycle, topological sort is impossible. It is commonly used for scheduling tasks with prerequisites.

Share

Contents

Kahn's Algorithm (BFS / Indegree)

Kahn's algorithm works by repeatedly removing nodes with indegree 0 (no incoming edges: no prerequisites). It also detects cycles: if the topological order contains fewer than V vertices, the graph has a cycle.

Algorithm steps:
  1. Compute the indegree of every vertex.
  2. Enqueue all vertices with indegree 0.
  3. While the queue is non-empty: dequeue a vertex, add it to the result, and decrement the indegree of all its neighbours. Enqueue any neighbour whose indegree reaches 0.
  4. If result size < V, a cycle exists.
Java
import java.util.*;

public List<Integer> topoSort(int V, List<List<Integer>> adj) {
    int[] indegree = new int[V];

    // Calculate indegrees
    for (int u = 0; u < V; u++) {
        for (int v : adj.get(u)) {
            indegree[v]++;
        }
    }

    // Enqueue all nodes with no incoming edges
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < V; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }

    List<Integer> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        int u = queue.poll();
        order.add(u);

        for (int v : adj.get(u)) {
            indegree[v]--;
            if (indegree[v] == 0) queue.offer(v);
        }
    }

    // If order.size() != V, cycle detected
    if (order.size() != V) throw new RuntimeException("Cycle detected — topological sort impossible");

    return order;
}
Example:
Java
// Graph: 5 → 0, 5 → 2, 4 → 0, 4 → 1, 2 → 3, 3 → 1
// Expected order (one valid): [4, 5, 2, 0, 3, 1]
int V = 6;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
adj.get(5).add(0); adj.get(5).add(2);
adj.get(4).add(0); adj.get(4).add(1);
adj.get(2).add(3);
adj.get(3).add(1);
System.out.println(topoSort(V, adj)); // [4, 5, 0, 2, 3, 1] (one valid order)

DFS Approach

In the DFS approach, after fully exploring a node's descendants, push it onto a stack. The reverse of the stack gives the topological order.

Java
public List<Integer> topoSortDFS(int V, List<List<Integer>> adj) {
    boolean[] visited = new boolean[V];
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            dfs(i, adj, visited, stack);
        }
    }

    List<Integer> order = new ArrayList<>();
    while (!stack.isEmpty()) order.add(stack.pop());
    return order;
}

private void dfs(int u, List<List<Integer>> adj, boolean[] visited, Deque<Integer> stack) {
    visited[u] = true;
    for (int v : adj.get(u)) {
        if (!visited[v]) dfs(v, adj, visited, stack);
    }
    stack.push(u); // push after all descendants are processed
}

Complexity Analysis
  • Time: O(V + E). Every vertex and edge is processed once.
  • Space: O(V). Indegree array / visited array / queue / stack.
Kahn's algorithm is preferred when you also need to detect cycles (check if result size == V). The DFS approach is preferred when you need a post-order completion time or are already using DFS for other purposes.