1Understand
The idea
In a dependency graph, a node can be done once all its prerequisites are done. Count each node's incoming edges, start with the nodes at zero, and every time you finish a node, decrease the count of its successors (Kahn's algorithm). If some nodes never reach zero, there is a cycle.
Intuition
In a dependency graph, a node can be done once all its prerequisites are done. Kahn's algorithm counts incoming edges, starts with nodes at zero, and every time you finish a node, decrease the count of its successors.
If some nodes never reach zero indegree, there is a cycle, the order is impossible. DFS-based topo sort pushes nodes after their descendants and reverses the finish order.
Both produce a valid linear order when the graph is a DAG.
What you will be able to do
- Implement Kahn's algorithm
- Detect a cycle from the output length
When to use it
- Prerequisites / dependencies / build order
- Can all tasks be completed?
- Order letters from a sorted alien dictionary
2See it
Walkthrough
Kahn’s algorithm
Edges A→B, A→C, B→D, peel indegree-0 nodes.
1 / 5
Indegrees: A0 B1 C1 D1. Queue = [A], only nodes with no incoming edges.
Live template
Line 1 active
Complexity: time O(V + E), space O(V + E)
O(V + E) time and space. Prefer Kahn when you also need cycle detection via leftover nodes. DFS topo is fine too; both beat repeated linear scans looking for free nodes.
Read the walkthrough as text
Course schedule order. Courses 0..3, edges (prereq → course): 0→1, 0→2, 1→3, 2→3.
- Indegrees:
[0,1,1,2]. Queue starts with0. - Take
0; reduce1and2to 0; enqueue them. - Take
1and2(order among them may vary); each reduces3. - Take
3. Order length 4 → valid, e.g.[0,1,2,3].
If an edge 3→0 existed, someone would remain with indegree > 0.
3Recognise it
Kinds of problems (7)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Kahn's algorithm (BFS)
Example. Topological order of course prerequisites.
How. Zero in-degree queue; peel nodes, decrement neighbours; order length n means no cycle.
DFS post-order
Example. Topo sort by finishing times.
How. DFS post-order stack, reverse for order; cycle if back edge in directed DFS.
Cycle detection in dependencies
Example. Can you finish all courses?
How. Kahn: fewer than n processed ⇒ cycle; or three-colour DFS on prerequisite graph.
Alien dictionary
Example. Derive character order from sorted alien words.
How. Compare adjacent words for first mismatch edge; topo sort letters; empty if invalid prefix.
Longest path in a DAG
Example. Critical path length in a DAG with weights.
How. Topo order relax edges: dist[v] = max(dist[v], dist[u] + w).
Reachability between all pairs (transitive closure)
Example. After topo on DAG, which nodes reach which?
How. Process backward in topo: propagate reach bits or DP from each source.
Nodes with no incoming edges
Example. Sources to start a dependency traversal.
How. Nodes with in-degree 0 after building the graph, Kahn’s initial queue.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Edge direction reversed
Why it happens. “A depends on B” reads as A → B in your head.
How it fails. Edge course → prerequisite makes both appear last, order satisfies dependencies backward.
Fix. Edge prerequisite → dependent (must finish prereq before course).
Cycle not detected
Why it happens. Partial order from processed nodes still prints something.
How it fails. Cycle A→B→A: Kahn processes 2 nodes, returns order length < n but code returns it anyway.
Fix. Success iff len(order) == n (or all nodes coloured in DFS).
Nodes without edges
Why it happens. Only nodes in edges get in-degree entries.
How it fails. Isolated node never in-degree zero set, dropped from order despite no incoming edges.
Fix. Initialize all nodes in indeg map before applying edges.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.