MediumHigh Frequency35 min
Topological Sort
Order tasks respecting dependencies using Kahn's algorithm (BFS) or DFS.
Topological sort orders nodes in a DAG so every edge goes from earlier to later. Use Kahn's (BFS + in-degree) or DFS post-order. Key for scheduling/dependency problems.
Topological Sort
Kahn's Algorithm
Course Schedule II
O(V+E)If result.size() < n → cycle → return []. Kahn's naturally detects cycles.Step-by-step1 / 5
Graphnodes + edges
0: in=0123
in-degrees: [0,1,1,2]
Course 0: no prereqs. Courses 1,2: each needs 0. Course 3: needs both 1 and 2.