Practice: Course Schedule
Can you finish every course?.
A university says, to take course B, you must finish course A first. Given all the rules, can a student finish every course? Only if the rules don't go round in a circle. Pause. Which algorithm spots a cycle?

- B needs A first
- Can you finish them all?
- Only without a cycle
Cycle detection with DFS
We colour each course. White means not visited yet. Grey means we're in the middle of exploring it. Black means it's finished, and safe. If depth first search ever reaches a grey course, we've gone round in a circle. Run it. The first plan works. The second has a loop, so it's impossible.
def can_finish(rules):
state = {}
def visit(c):
if state.get(c) == "grey": return False
if state.get(c) == "black": return True
state[c] = "grey"
if not all(visit(n) for n in rules.get(c, [])): return False
state[c] = "black"
return True
return all(visit(c) for c in rules)
ok = {"maths": ["physics"], "physics": ["engineering"]}
bad = {"a": ["b"], "b": ["c"], "c": ["a"]}
print(can_finish(ok), can_finish(bad))True False
Three ways to find a cycle
You now know three ways to spot a cycle. Three colour depth first search, for directed graphs like this one. Kahn's algorithm, where the order comes out too short. And union find, for undirected graphs, where union returns false because two nodes were already connected.
| key | value |
|---|---|
| Directed | DFS with colours |
| Directed | Kahn's order too short |
| Undirected | union find returns False |
| Cost | O(V + E) |
Summary
A plan is possible only if its rules have no cycle. Three colour depth first search finds one, in O of V plus E. Next, a quiz on graphs.
Key takeaways- White, grey, black
- Reach grey = cycle
- No cycle = possible