DSA Tracker

Visualize

Course Schedule II

Kahn's algorithm — topological sort by indegree

time O(V + E)space O(V + E)

Course Schedule II is a topological sort wearing a word problem. Model each course as a vertex and each [course, before] pair as an edge before -> course, and the question becomes: list the vertices so every edge points forward. Kahn's algorithm does it by tracking each vertex's INDEGREE — the number of prerequisites it is still waiting on. Vertices at indegree 0 are takeable now, so they go in a queue; taking one removes its outgoing edges, which decrements its dependents and may free them in turn. The cycle check comes free: a vertex inside a cycle always has a prerequisite left inside that cycle, so its indegree never reaches 0, it never enters the queue, and the final order comes up short of numCourses — which is precisely the signal to return an empty list.

Details

Animated on: numCourses = 7, prerequisites = [[1,0],[2,0],[3,1],[3,2],[5,2],[4,3],[6,4],[6,5]] — return any order in which all 7 courses can be taken, or an empty list if no such order exists.

Problem:Course Schedule IIMedium

Pattern:Topological Sort

Kahn's algorithm — topological sort by indegree

step 1 / 11

7 courses and 8 prerequisite edges. An edge before -> course means before must be finished first, so a valid order is exactly a topological order of this graph — and only a graph with no cycle has one.

Pseudocode
1FUNCTION TOPO_ORDER(n, prereqs)
2  FOR EACH (course, before) IN prereqs
3    indeg[course] <- indeg[course] + 1
4  queue <- ALL v WITH indeg[v] = 0
5  WHILE queue NOT EMPTY
6    v <- REMOVE FRONT OF queue
7    APPEND v TO order
8    FOR EACH w IN adj[v]
9      indeg[w] <- indeg[w] - 1
10      IF indeg[w] = 0
11        APPEND w TO queue
12  IF LENGTH(order) < n
13    RETURN EMPTY
14  RETURN order

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. 7 courses and 8 prerequisite edges. An edge before -> course means before must be finished first, so a valid order is exactly a topological order of this graph — and only a graph with no cycle has one.
  2. Each badge is a course's INDEGREE — how many prerequisites it is still waiting on. Course 0 waits on nothing, 6 others do. Indegree is the whole trick: a course is takeable the instant its badge hits 0.
  3. Seed the queue with every indegree-0 course: course 0. These need no prerequisite, so they can be taken right now, in any order.
  4. Take course 0 — position 1 in the order. That satisfies a prerequisite for course 1 and course 2, so each badge drops by 1, and course 1, course 2 hit 0 and join the queue.
  5. Take course 1 — position 2 in the order. That satisfies a prerequisite for course 3, so each badge drops by 1 — none reaches 0 yet, so nothing new is takeable.
  6. Take course 2 — position 3 in the order. That satisfies a prerequisite for course 3 and course 5, so each badge drops by 1, and course 3, course 5 hit 0 and join the queue.
  7. Take course 3 — position 4 in the order. That satisfies a prerequisite for course 4, so each badge drops by 1, and course 4 hit 0 and join the queue.
  8. Take course 5 — position 5 in the order. That satisfies a prerequisite for course 6, so each badge drops by 1 — none reaches 0 yet, so nothing new is takeable.
  9. Take course 4 — position 6 in the order. That satisfies a prerequisite for course 6, so each badge drops by 1, and course 6 hit 0 and join the queue.
  10. Take course 6 — position 7 in the order. It unlocks nothing; it was the last course on its chain.
  11. The queue is empty and the order holds 7 of 7 courses: [0, 1, 2, 3, 5, 4, 6]. Every edge points from an earlier course to a later one, so the schedule is legal. Had a cycle existed, its courses could never have reached indegree 0, the loop would have stopped short, and the shortfall is exactly how the algorithm reports "impossible".

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Course Schedule II in the editorAll Graph problemsBack to roadmap