Intermediate · Module 17 · Lesson 6
Topological sort
Order DAG nodes using indegrees or DFS finish times.
Lesson 100 of 123
1d streakInteractive Visualization
Trace the algorithm state by state
Change the inputs, run an operation, and connect each visible state change to the explanation below.
Interactive algorithm lab
Kahn’s Topological Sort
Remove prerequisites using indegrees
Current
—
Ready queue
A B
Output
—
Completed
0/6
Why this step happens
A and B have no remaining prerequisites, so they enter the queue.
Only nodes whose prerequisites are already output may enter the queue.
Topological Sort: Kahn’s BFS Algorithm & Cycle Detection
A topological sort of a Directed Acyclic Graph (DAG) linearly orders vertices such that for every directed edge u -> v, u appears before v. Kahn’s algorithm maintains in-degrees for all nodes: nodes with in-degree 0 are processed via a queue, decrementing neighbor in-degrees.
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] inDegree = new int[numCourses];
Map<Integer, List<Integer>> adj = new HashMap<>();
for (int[] edge : prerequisites) {
adj.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);
inDegree[edge[0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) queue.offer(i);
}
int processed = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
processed++;
for (int next : adj.getOrDefault(course, List.of())) {
if (--inDegree[next] == 0) queue.offer(next);
}
}
return processed == numCourses; // If processed < numCourses, a cycle exists!
}Active Recall Checkpoint
How does Kahn’s algorithm detect cycles in a directed graph?
Show answer & explanation
Nodes involved in a directed cycle never reach an in-degree of 0, so they never enter the queue. If total processed nodes < V, the graph contains a cycle.
Use it when
Use topological sort for task scheduling, build dependencies (Make/Maven), course prerequisites, and package manager dependency resolution.
Reconsider when
Reconsider when the graph contains undirected edges or when cycles are known to be valid components.
Cost Model
Complexity & Trade-offs
When to use it
- Networks, dependencies, connectivity, shortest paths, and grid movement.
- Ordering prerequisite-constrained work.
- Grouping reachable or mutually reachable states.
Common mistakes
- Marking visited too late and enqueuing the same vertex repeatedly.
- Ignoring disconnected components.
- Using an algorithm whose weight assumptions do not match the graph.
Practice prompts
- Reproduce the worked Topological sort example without looking at the trace.
- Change one input condition and explain whether the Topological sort invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check