Process nodes with in-degree 0 first — linear ordering of a DAG
DAGIn-degreeBFS QueueCycle Detection
Time: O(V + E)Space: O(V)
When to Use
Order tasks where some depend on others
Detect cycle in directed graph — if output < V, cycle exists
Course scheduling with prerequisites
Build systems, package dependency resolution
Find ordering of items with constraints
Complexity
Build in-degree[]
O(V + E)
BFS processing
O(V + E)
Total
O(V + E)
Space
O(V) for queue + in-degree array
Live Animation · Topological Sort (Kahn's BFS) · LC #210
Problem
Given numCourses = 6 and a list of prerequisites, return a valid order to finish all courses. Use Kahn's BFS: compute in-degrees, enqueue all zero-in-degree courses first, then BFS — taking a course decrements its dependents' in-degrees, unlocking new courses.
Input: numCourses = 6, prerequisites = [[1,0],[2,0],[3,1],[3,2],[4,2],[5,3]] · Answer: [0, 1, 2, 3, 4, 5]
In-Degree [ ]
🗳 Queue
✅ Output Order
Step 0 / 8
InitSeed QueueProcess NodeDone
Build in-degree array: count incoming edges for every node.
for edge (u,v): inDeg[v]++
Java Pattern Templateskeleton only
// Topological Sort — Kahn's BFS (pattern skeleton)int[] inDeg = new int[n];
List<List<Integer>> adj = /* build adjacency list */;
// 1. Count in-degreesfor (int[] e : edges) inDeg[e[1]]++;
// 2. Seed queue with all zero-in-degree nodes
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++) if (inDeg[i] == 0) q.offer(i);
// 3. BFS — process each zero-in-degree node
List<Integer> order = new ArrayList<>();
while (!q.isEmpty()) {
int u = q.poll();
order.add(u);
for (int v : adj.get(u)) {
if (--inDeg[v] == 0) q.offer(v); // unblock neighbor
}
}
// 4. Cycle check: if not all nodes processed → cycle existsif (order.size() < n) { /* cycle detected */ }