Question Bank
Topological Sort Essentials
Difficulty: Medium
Kahn's algorithm, DFS-based ordering, and using topo sort to detect cycles in directed graphs. Code stems are mostly Python.
Topological Sort Essentials
Kahn's algorithm, DFS-based ordering, and using topo sort to detect cycles in directed graphs. Code stems are mostly Python.
406 views
12
Implement Kahn's algorithm to return one valid topological order of the DAG given as an adjacency list. Return None if the graph has a cycle.
Examples
Example 1:
Input: n = 4, adj = [[1, 2], [3], [3], []]
Output: [0, 1, 2, 3]
Explanation: Compute in-degrees, seed a queue with zero-indegree vertices, then repeatedly pop and decrement neighbors. Each time a neighbor reaches indegree 0, push it. O(V + E).Example 2:
Input: n = 2, adj = [[1], [0]]
Output: None
Explanation: The two vertices form a cycle. Neither ever reaches indegree 0, so the order has fewer than n vertices and Kahn returns None.List all valid topological orderings of this graph. Edges: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3.
Explain how Kahn's algorithm detects a cycle. What is the invariant that fails when a cycle exists?
Fix this DFS-based topological sort. It is supposed to return a valid order but currently returns the reverse of one.
Examples
Example 1:
Input: adj = [[1, 2], [3], [3], []]
Output (buggy version): [3, 1, 2, 0] (post-order, wrong)
Output (fixed version): [0, 2, 1, 3]
Explanation: The function appends u after recursing into descendants, which is post-order. Post-order on a DAG is the reverse of a topological sort because descendants finish first. The fix is to reverse the result before returning.You have numCourses courses and a list of prerequisites [a, b] meaning take b before a. What does the directed edge point from to in your adjacency list, and why does that choice matter?