Graphs · Stage 3 of 3
Topological Sort
Repeatedly take a node with no incoming edges; leftovers mean a cycle
Foundations
So far, every edge worked both ways. Now, what if each edge has a direction, from one node to another that must come after it, and you need an order that respects every arrow?
In a directed graph, a node's in-degree counts the arrows pointing into it. A node with in-degree 0 waits on nothing, so it can go first. Kahn's algorithm queues every such node, then repeatedly takes one, appends it to the order, and lowers the in-degree of each node it points to, queuing any that reach 0. If the order ends up shorter than the graph, the leftovers sit on, or behind, a cycle.
Take the directed graph adj = [[1, 2], [3], [3], [4], []]: arrows 0 → 1, 0 → 2, 1 → 3, 2 → 3, and 3 → 4. Only node 0 has in-degree 0. Taking 0 frees 1 and 2; taking 1 lowers 3 to in-degree 1, and taking 2 frees it; taking 3 frees 4. The order 0, 1, 2, 3, 4 makes every arrow point forward.
3 waiting on one more arrow, from 2. Node 2 has in-degree 0, so it goes next; then 3, then 4.Case Scenario
The problem
Course Schedule
numCourses courses labeled 0..n-1. prerequisites[i] = [a, b] means b before a. Return true if you can finish all courses (the graph is a DAG).
- Input
- numCourses = 5, prerequisites = [[1, 0], [2, 1], [3, 2], [1, 3], [4, 0]]
- Output
- False
Course Schedule asks whether all numCourses courses can be finished, where each pair [course, pre] means pre must come first. Draw an arrow from pre to course; every course can be taken exactly when the graph has no cycle, which Kahn's algorithm detects. For 5 courses and [[1, 0], [2, 1], [3, 2], [1, 3], [4, 0]], courses 1, 2, and 3 wait on each other, so the answer is False.
The direct approach tries orders: pick a course whose prerequisites are done, recurse, and back up at a dead end. With n courses there can be up to n! orders to explore, and a cycle hides at the end of many of them. The real question is narrower: whether any set of courses waits on itself.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.