Graph Algorithms

Topological Sort

A linear ordering of a DAG's vertices such that every edge points forward — the algorithm behind build systems, task schedulers, and "which courses can I take first."

Only defined for directed acyclic graphs (DAGs) — a cycle means no valid ordering exists
Kahn's algorithm: repeatedly remove vertices with in-degree 0, which is BFS in spirit
DFS-based alternative: run DFS, then reverse the postorder finish times
A topological order is rarely unique — many valid orderings can satisfy the same DAG
Kahn's algorithm detects a cycle for free: if fewer than V vertices get removed, a cycle exists

Kahn's algorithm

static List<Integer> topoSort(List<List<Integer>> adj, int n) {
    int[] indegree = new int[n];
    for (List<Integer> neighbors : adj) for (int v : neighbors) indegree[v]++;

    Deque<Integer> ready = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indegree[i] == 0) ready.add(i);

    List<Integer> order = new ArrayList<>();
    while (!ready.isEmpty()) {
        int u = ready.poll();
        order.add(u);
        for (int v : adj.get(u)) {
            if (--indegree[v] == 0) ready.add(v);
        }
    }
    if (order.size() != n) throw new IllegalStateException("cycle detected");
    return order;
}

Kahn's vs DFS-based topological sort
	Kahn's (BFS-style)	DFS-postorder
Cycle detection	free — leftover in-degree ≠ 0 vertices	needs an explicit "on stack" marker
Order produced	one valid order among many	a different valid order among many
Natural fit	iterative, easy to reason about degrees	when you're already doing a DFS pass for something else