Pattern visualizer
Course Schedule II
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. 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..
Kahn's algorithm — topological sort by indegree
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.
1FUNCTION TOPO_ORDER(n, prereqs)2 FOR EACH (course, before) IN prereqs3 indeg[course] <- indeg[course] + 14 queue <- ALL v WITH indeg[v] = 05 WHILE queue NOT EMPTY6 v <- REMOVE FRONT OF queue7 APPEND v TO order8 FOR EACH w IN adj[v]9 indeg[w] <- indeg[w] - 110 IF indeg[w] = 011 APPEND w TO queue12 IF LENGTH(order) < n13 RETURN EMPTY14 RETURN order
← / → step · space play · Home restart