Pattern7 min read

Topological Sort

Order nodes such that every edge u→v has u before v — solves dependency, build, and course-prereq problems.

graphbfsdfs

Intro

Topological sort works on Directed Acyclic Graphs (DAGs). Two flavours: Kahn's algorithm (BFS using in-degree) and DFS-based (post-order). Kahn's is easier to reason about and gives natural cycle detection: if you can't process all nodes, there's a cycle.

Key insight

Repeatedly remove a node with no incoming edges and emit it. If you emit all n nodes, you have a topological order; otherwise, the remainder forms a cycle.

Approach

1Build adjacency list and in-degree array.
2Push all in-degree-0 nodes onto a queue.
3Pop u, emit it, decrement in-degree of each neighbour v; if it hits 0, push.
4If emitted count < n, the graph has a cycle.

Complexity

Time

O(V + E)

Space

O(V + E)

Code

LC 207 — course schedule (cycle detection)java

boolean canFinish(int n, int[][] prereq) {
    List<List<Integer>> g = new ArrayList<>();
    int[] indeg = new int[n];
    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
    for (int[] e : prereq) { g.get(e[1]).add(e[0]); indeg[e[0]]++; }
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
    int seen = 0;
    while (!q.isEmpty()) {
        int u = q.poll(); seen++;
        for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v);
    }
    return seen == n;
}

Pitfalls

Confusing direction of the edge (prereq vs. dependent).
Not handling disconnected components — they have multiple sources.
Returning the order without verifying you emitted all nodes (silent cycle).

Variants & follow-ups

Course Schedule II (LC 210)
Alien Dictionary (LC 269)
Parallel Courses (LC 1136)