Topological Sort
Overview
Topological Sort applies exclusively to Directed Acyclic Graphs (DAGs). It orders the vertices linearly such that for every directed edge pointing from U to V, vertex U appears before vertex V in the final ordering.
This is the definitive algorithm behind Dependency Resolution. Imagine you need to compile a massive Java project. Class B imports Class A, so Class B depends on Class A. You absolutely must compile Class A first. Topological Sort maps out the exact sequence to process hundreds of tasks without violating a single prerequisite.
Kahn's Algorithm is the standard, intuitive way to implement this using a BFS-like queue approach. It calculates the 'In-Degree' (number of incoming prerequisites) for every node. Nodes with an In-Degree of 0 have no prerequisites and are ready to execute! They are added to a Queue. As they are processed, they 'remove' their outbound edges, dropping the In-Degrees of their neighbors until the neighbors hit 0 and enter the queue.
Syntax
import java.util.*;
public class TopologicalSort {
// prerequisites format: [Course, RequiredPrereq]
public List<Integer> sort(int numCourses, int[][] prerequisites) {
Map<Integer, List<Integer>> graph = new HashMap<>();
int[] inDegree = new int[numCourses]; // Tracks prerequisites count
// 1. Build Graph and calculate In-Degrees
for (int[] pre : prerequisites) {
int course = pre[0];
int required = pre[1]; // Required -> Course
graph.putIfAbsent(required, new ArrayList<>());
graph.get(required).add(course);
inDegree[course]++; // This course has an incoming requirement
}
// 2. Add all courses with NO prerequisites (In-Degree == 0) to Queue
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) queue.offer(i);
}
List<Integer> order = new ArrayList<>();
// 3. Process Queue
while (!queue.isEmpty()) {
int curr = queue.poll();
order.add(curr);
// We finished 'curr'. Decrease In-Degree of all courses depending on it.
for (int neighbor : graph.getOrDefault(curr, new ArrayList<>())) {
inDegree[neighbor]--;
// If a neighbor now has 0 prerequisites left, it's ready!
if (inDegree[neighbor] == 0) {
queue.offer(neighbor);
}
}
}
// If the order size != numCourses, there was a cycle! (Impossible to resolve)
return order.size() == numCourses ? order : new ArrayList<>();
}
}Common Pitfalls
- Not checking for cycles at the end. If the graph contains a cycle (A depends on B, B depends on A), those nodes will never reach an In-Degree of 0. They will never enter the queue. You must check
if (order.size() == numNodes)at the end to guarantee a valid sort. - Parsing the directed edges backwards. If the input array is
[Task, Prerequisite], the edge MUST point from Prerequisite -> Task. Getting this backwards breaks the entire logic. - Using it on undirected graphs. Topological sort relies entirely on one-way dependencies. It makes no mathematical sense on an undirected graph.
Interview Questions
It means the node has absolutely no uncompleted prerequisites. It is totally independent and is ready to be processed immediately.
Yes, absolutely. If multiple nodes have an In-Degree of 0 at the same time, the order you pull them from the queue dictates the sort. Both orderings are perfectly valid dependency resolutions.
Real-World Example
Build Tools and Package Managers. When you run npm install or mvn clean install, the tool reads the package.json or pom.xml. It builds a massive dependency graph. It runs a Topological Sort to figure out exactly which libraries must be downloaded and compiled first so that later libraries have everything they need to function.
public class BuildSystem {
public void compileProject(List<Module> modules) {
List<Module> compilationOrder = runTopologicalSort(modules);
if (compilationOrder.size() < modules.size()) {
throw new CircularDependencyException("Cannot compile: Cycle detected!");
}
for (Module m : compilationOrder) {
System.out.println("Compiling: " + m.getName());
m.compile();
}
}
}Check Your Knowledge
Test your understanding of Topological Sort with these quick questions.