templates · Graph traversal
Topological sort (Kahn & DFS)
- "Prerequisites", "dependencies" or "X must happen before Y"
- "Is it possible to finish everything?" (that is: is there a cycle?)
- You need a valid order of tasks, like a build tool or Git history (a DAG)
the one rule
The invariant
A node joins the order only when everything that must come before it is already in the order.
write it from memory
The template
Kahn's algorithm (BFS on indegrees)
/** An order of 0..n-1 where every edge {u, v} has u before v; empty if there is a cycle. */static int[] kahn(int n, int[][] edges) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); int[] indegree = new int[n]; for (int[] e : edges) { adj.get(e[0]).add(e[1]); // u must come before v indegree[e[1]]++; } Deque<Integer> queue = new ArrayDeque<>(); for (int i = 0; i < n; i++) if (indegree[i] == 0) queue.offer(i); // nothing has to come first int[] order = new int[n]; int done = 0; while (!queue.isEmpty()) { int u = queue.poll(); order[done++] = u; // take a ready node for (int v : adj.get(u)) { if (--indegree[v] == 0) queue.offer(v); // last blocker gone: v is ready } } return done == n ? order : new int[0]; // someone never got ready = cycle}Start with nodes nobody waits on. Taking a node removes its edges; a neighbour whose count hits 0 becomes ready.
fill in the blanks — only these lines change per problem
- line 7The edge direction. In Course Schedule,
[a, b]means b comes first, so the edge isb → a. - line 16What you do with a ready node: add it to the order, or count it if you only need yes / no.
- line 21What a cycle means for the answer:
false, an empty array, or an empty string (Alien Dictionary).
DFS with three colours
/** Same answer by DFS: finish order, reversed. Grey = on the current path, so meeting grey = cycle. */static int[] dfsOrder(int n, int[][] edges) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); for (int[] e : edges) adj.get(e[0]).add(e[1]); int[] colour = new int[n]; // 0 white (new), 1 grey (on path), 2 black (done) Deque<Integer> finished = new ArrayDeque<>(); for (int u = 0; u < n; u++) { if (colour[u] == 0 && !visit(u, adj, colour, finished)) return new int[0]; } int[] order = new int[n]; for (int i = 0; i < n; i++) order[i] = finished.pop(); // last finished comes first return order;} /** False if a cycle is reachable from u. */static boolean visit(int u, List<List<Integer>> adj, int[] colour, Deque<Integer> finished) { colour[u] = 1; // grey: we are inside u for (int v : adj.get(u)) { if (colour[v] == 1) return false; // back to the current path = cycle if (colour[v] == 0 && !visit(v, adj, colour, finished)) return false; } colour[u] = 2; // black: u and everything after it is done finished.push(u); return true;}A node finishes only after everything after it has finished, so reversing the finish order gives a valid order.
fill in the blanks — only these lines change per problem
- line 20How a cycle shows up: you reach a grey node. For Find Eventual Safe States, grey nodes are the unsafe ones.
complexity
What it costs
- time
O(V + E) - Every node is taken once and every edge lowers one indegree once (Kahn), or is followed once (DFS).
- space
O(V + E) - The adjacency list, plus indegree or colour arrays and a queue or call stack of at most V nodes.
watch out
Common bugs
- Reversing the edge direction, which gives the order backwards.
- In DFS, using only two colours (seen / not seen). Then a node reached by two paths looks like a cycle.
- Forgetting the final check
done == n. Without it, a graph with a cycle returns a short order instead of failing.
use it
Practise it on
learn it properly