Pattern visualizer

Course Schedule

You never have to produce the order to answer this. Repeatedly take any course whose prerequisites are all done, and count how many you get through: anything reachable drains eventually, so the count falls short only when some courses depend on each other in a loop. One number per course is enough state — how many prerequisites are still outstanding — because finishing a course lowers exactly the counts of the courses it unlocks. The picture below draws one directed arrow per prerequisite and shows that outstanding count as a badge. Animated on: 7 courses with prerequisites 0->1, 0->2, 1->3, 2->3, 3->4, 4->5, 5->6, 6->4 (a->b means take a before b) — can every course be finished?.

Kahn's topological sort: drain the courses that have no prerequisites

time O(V + E)space O(V + E)step 1 / 12

Courses and prerequisites

line 1

7 courses, and an arrow a to b means a must be taken before b. The question is not which order to use but whether ANY order exists — and the only thing that can rule one out is a group of courses that require each other in a loop.

Pseudocode

1FUNCTION canFinish(n, prereqs):
2  FOR c FROM 0 TO n - 1
3    indeg[c] <- 0
4  FOR EACH (a, b) IN prereqs
5    APPEND b TO next[a]
6    indeg[b] <- indeg[b] + 1
7  queue <- EVERY c WHERE indeg[c] = 0
8  taken <- 0
9  WHILE queue NOT EMPTY
10    c <- REMOVE FIRST FROM queue
11    taken <- taken + 1
12    FOR EACH d IN next[c]
13      indeg[d] <- indeg[d] - 1
14      IF indeg[d] = 0
15        APPEND d TO queue
16  RETURN taken = n

← / → step · space play · Home restart

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap