Overview
A topological order of a directed graph lists every vertex so that each edge u → v has u before v. Build systems compile libraries before the programs that use them, package managers install dependencies first, and universities sequence prerequisite courses — all are topological sorts. Such an order exists exactly when the graph has no directed cycle (it is a DAG).
Kahn's algorithm is the most practical way to compute one: repeatedly take a vertex with no remaining incoming edges, output it, and remove its outgoing edges. If you run out of such vertices before outputting everything, the remaining vertices form a cycle — which is how "can all courses be finished?" is answered.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| Kahn's algorithm | O(V + E) |
| DFS-based sort | O(V + E) |
Patterns to recognise
Can it be done? / In what order?
Use it for: Course schedule I and II, build order.
Run Kahn's; success means the output contains every vertex.
Three-colour DFS
Use it for: Find eventual safe states, cycle detection.
White = unvisited, grey = on the stack, black = finished.
Longest path in a DAG
Use it for: Parallel courses III, longest increasing path in a matrix.
Relax edges in topological order, tracking the best value per vertex.
Code template
from collections import deque
def find_order(num_courses, prerequisites):
graph = [[] for _ in range(num_courses)]
indegree = [0] * num_courses
for course, pre in prerequisites:
graph[pre].append(course) # pre must come before course
indegree[course] += 1
queue = deque(i for i in range(num_courses) if indegree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return order if len(order) == num_courses else [] # [] means a cycle
vector<int> findOrder(int numCourses, const vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses);
vector<int> indegree(numCourses, 0);
for (auto& p : prerequisites) {
graph[p[1]].push_back(p[0]); // p[1] must come before p[0]
++indegree[p[0]];
}
queue<int> q;
for (int i = 0; i < numCourses; ++i) if (indegree[i] == 0) q.push(i);
vector<int> order;
while (!q.empty()) {
int node = q.front(); q.pop();
order.push_back(node);
for (int nxt : graph[node])
if (--indegree[nxt] == 0) q.push(nxt);
}
if ((int)order.size() != numCourses) return {}; // cycle
return order;
}
Common mistakes
- Getting the edge direction backwards — write down "u must come before v" and draw u → v.
- Topological sort only applies to directed graphs.
- Vertices with no edges at all still belong in the order; seed the queue from every vertex.
Quick check
Three questions on Topo Sort. Get all three right to earn +15 XP.
-
A topological order exists only when the graph is:
A cycle means some task would have to come before itself.
-
Kahn's algorithm begins with which vertices?
A vertex with no incoming edges has no unfinished prerequisites.
-
How does Kahn's algorithm reveal a cycle?
Vertices on a cycle never drop to in-degree zero, so they are never output.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Find the Town JudgeLeetCode Easy +20
- Course ScheduleLeetCode Medium +40
- Course Schedule IILeetCode Medium +40
- Find Eventual Safe StatesLeetCode Medium +40
- Minimum Height TreesLeetCode Medium +40
- Parallel Courses IIILeetCode Hard +70
- Longest Increasing Path in a MatrixLeetCode Hard +70
Stuck on Topo Sort?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor