Think about the subjects in a B.Tech CS course.
You cannot study Data Structures before you know Programming in C. You cannot study Algorithms before Data Structures and Discrete Mathematics.
Programming in C → Data Structures
Data Structures → Algorithms
Discrete Maths → AlgorithmsSo in what order should you take the subjects?
One valid answer is:
Programming in C → Discrete Maths → Data Structures → AlgorithmsAnother valid answer is:
Discrete Maths → Programming in C → Data Structures → AlgorithmsBoth respect every rule. Finding such an order is called Topological Sorting.
A topological sort of a directed graph is a linear ordering of its vertices such that for every directed edge u → v, vertex u comes before vertex v.
In simple words: every task comes after all the tasks it depends on.
Dependencies as a Graph
We model the problem as a directed graph:
Vertex → a task (or course, file, package)
Edge → u → v means "u must be done before v"Here is the graph we will use throughout this chapter:
5 ──→ 2 ──→ 3
│ │
↓ ↓
0 ←── 4 ──→ 1
Edges:
5 → 2, 5 → 0
4 → 0, 4 → 1
2 → 3, 3 → 1A valid topological order must place:
5before2and04before0and12before33before1
Some valid orders:
4 5 2 0 3 1
5 4 2 3 1 0
4 5 0 2 3 1An invalid order:
5 2 1 3 4 0
✗
1 comes before 3 and 4, but 3 → 1 and 4 → 1Notice that more than one topological order can exist. Any order that respects every edge is correct.
Topological Sort Works Only on a DAG
A DAG is a Directed Acyclic Graph: a directed graph with no cycles.
Topological sorting is possible if and only if the graph is a DAG.
Why? Look at a cycle:
A → B → C → AThe rules say:
A before B
B before C
C before AThat would need A before A, which is impossible. In the previous chapter, this was exactly the "everyone is waiting for everyone" situation.
What about undirected graphs? An undirected edge A ─ B has no direction, so it doesn't say which one comes first. Topological sort is not defined for undirected graphs.
Every DAG has at least one topological order, and a graph with a cycle has none.
There are two classic ways to find a topological order:
Topological Sort
├── Kahn's Algorithm (BFS + indegree)
└── DFS-based method (DFS + stack)Indegree: The Key Idea Behind Kahn's Algorithm
The indegree of a vertex is the number of edges coming into it. You met this term in the Graphs chapter.
For our graph:
Vertex | Incoming edges | Indegree |
|---|---|---|
0 | 5 → 0, 4 → 0 | 2 |
1 | 4 → 1, 3 → 1 | 2 |
2 | 5 → 2 | 1 |
3 | 2 → 3 | 1 |
4 | none | 0 |
5 | none | 0 |
A vertex with indegree 0 has no pending prerequisites. It can be done right now.
So the idea is:
1. Do any task that has no pending prerequisites.
2. Once it is done, it no longer blocks the tasks after it.
3. Some of those tasks may now have no pending prerequisites.
4. Repeat.This is exactly how you would plan your semesters in real life.
Kahn's Algorithm
Kahn's algorithm (published by Arthur Kahn in 1962) uses a queue, so it feels just like BFS.
1. Compute the indegree of every vertex.
2. Add every vertex with indegree 0 to a queue.
3. While the queue is not empty:
remove a vertex u from the queue
add u to the answer
for every edge u → v:
indegree[v]--
if indegree[v] == 0:
add v to the queue
4. If the answer contains all V vertices → it is a valid order.
Otherwise → the graph has a cycle.Kahn's Algorithm Step by Step
Starting indegrees:
vertex : 0 1 2 3 4 5
indegree : 2 2 1 1 0 0Vertices with indegree 0 are 4 and 5:
Queue = [4, 5]
Order = []Step 1: Remove 4
Edges 4 → 0 and 4 → 1. Decrease their indegrees.
indegree[0]: 2 → 1
indegree[1]: 2 → 1
Queue = [5]
Order = [4]Step 2: Remove 5
Edges 5 → 2 and 5 → 0.
indegree[2]: 1 → 0 → add 2
indegree[0]: 1 → 0 → add 0
Queue = [2, 0]
Order = [4, 5]Step 3: Remove 2
Edge 2 → 3.
indegree[3]: 1 → 0 → add 3
Queue = [0, 3]
Order = [4, 5, 2]Step 4: Remove 0
0 has no outgoing edges.
Queue = [3]
Order = [4, 5, 2, 0]Step 5: Remove 3
Edge 3 → 1.
indegree[1]: 1 → 0 → add 1
Queue = [1]
Order = [4, 5, 2, 0, 3]Step 6: Remove 1
Queue = []
Order = [4, 5, 2, 0, 3, 1]All 6 vertices are in the answer, so this is a valid topological order.
Kahn's Algorithm in Java
This program also shows what happens when we add the edge 1 → 5, which creates the cycle 5 → 2 → 3 → 1 → 5.
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
class Main {
static ArrayList<Integer> topoSort(ArrayList<ArrayList<Integer>> graph) {
int vertices = graph.size();
// Step 1: count incoming edges of every vertex
int[] indegree = new int[vertices];
for (int u = 0; u < vertices; u++) {
for (int v : graph.get(u)) {
indegree[v]++;
}
}
// Step 2: start with every vertex that has no prerequisite
Queue<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < vertices; i++) {
if (indegree[i] == 0) {
queue.add(i);
}
}
ArrayList<Integer> order = new ArrayList<>();
// Step 3: remove vertices one by one
while (!queue.isEmpty()) {
int node = queue.poll();
order.add(node);
for (int neighbor : graph.get(node)) {
indegree[neighbor]--;
if (indegree[neighbor] == 0) {
queue.add(neighbor);
}
}
}
// Step 4: if some vertex was never added, there is a cycle
if (order.size() != vertices) {
return new ArrayList<>();
}
return order;
}
public static void main(String[] args) {
int vertices = 6;
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
graph.add(new ArrayList<>());
}
graph.get(5).add(2);
graph.get(5).add(0);
graph.get(4).add(0);
graph.get(4).add(1);
graph.get(2).add(3);
graph.get(3).add(1);
System.out.println("Topological order: " + topoSort(graph));
// add 1 -> 5 to create the cycle 5 -> 2 -> 3 -> 1 -> 5
graph.get(1).add(5);
System.out.println("After adding 1 -> 5: " + topoSort(graph));
}
}Output:
Topological order: [4, 5, 2, 0, 3, 1]
After adding 1 -> 5: []How Kahn's Algorithm Detects Cycles
After adding 1 → 5, vertex 5 has an incoming edge. Only 4 starts with indegree 0.
Remove 4 → indegree[0] = 1, indegree[1] = 1
Queue is empty. Order = [4]Vertices 5, 2, 3, 1 are all waiting for each other, so none of them ever reaches indegree 0. Vertex 0 is also stuck, because it is still waiting for 5.
Since order.size() is 1 and not 6, we know there is a cycle.
If Kahn's algorithm processes fewer than V vertices, the graph contains a cycle.
This is the BFS-style cycle detection for directed graphs that was promised in the previous chapter.
The DFS-Based Method
The second approach uses the DFS you already know, with one small twist.
Think about when DFS finishes a vertex, that is, when the recursive call returns.
By that time, DFS has already explored everything reachable from that vertex, which means every task that depends on it.
So if we push each vertex onto a stack after visiting all its neighbors:
dfs(node):
mark node visited
for each neighbor:
if not visited:
dfs(neighbor)
push node onto stack ← after all neighborsthen every vertex is pushed after all the vertices that must come after it. Popping the stack gives them in the correct order.
This order of finishing is called postorder. So:
Topological order = reverse of DFS postorder.
DFS Method Step by Step
Adjacency list (in the order edges were added):
0 : []
1 : []
2 : [3]
3 : [1]
4 : [0, 1]
5 : [2, 0]We start DFS from every unvisited vertex in order 0, 1, 2, 3, 4, 5:
dfs(0) → no neighbors → push 0 stack: [0]
dfs(1) → no neighbors → push 1 stack: [1, 0]
dfs(2) → dfs(3) → 1 is visited → push 3 stack: [3, 1, 0]
→ back in 2 → push 2 stack: [2, 3, 1, 0]
3 already visited
dfs(4) → 0, 1 visited → push 4 stack: [4, 2, 3, 1, 0]
dfs(5) → 2, 0 visited → push 5 stack: [5, 4, 2, 3, 1, 0](The top of the stack is written first.)
Popping everything gives:
5 4 2 3 1 0Check: 5 before 2, 0; 4 before 0, 1; 2 before 3; 3 before 1. Valid.
It is a different order from Kahn's algorithm, and that is completely fine.
DFS Topological Sort in Java
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
class Main {
static void dfs(
int node,
ArrayList<ArrayList<Integer>> graph,
boolean[] visited,
Deque<Integer> stack
) {
visited[node] = true;
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
dfs(neighbor, graph, visited, stack);
}
}
// every vertex that depends on 'node' is already on the stack
stack.push(node);
}
static ArrayList<Integer> topoSort(ArrayList<ArrayList<Integer>> graph) {
int vertices = graph.size();
boolean[] visited = new boolean[vertices];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < vertices; i++) {
if (!visited[i]) {
dfs(i, graph, visited, stack);
}
}
ArrayList<Integer> order = new ArrayList<>();
while (!stack.isEmpty()) {
order.add(stack.pop());
}
return order;
}
public static void main(String[] args) {
int vertices = 6;
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
graph.add(new ArrayList<>());
}
graph.get(5).add(2);
graph.get(5).add(0);
graph.get(4).add(0);
graph.get(4).add(1);
graph.get(2).add(3);
graph.get(3).add(1);
System.out.println("Topological order: " + topoSort(graph));
}
}Output:
Topological order: [5, 4, 2, 3, 1, 0]We used ArrayDeque as the stack, because it is faster than the old Stack class. push() and pop() work at the front of the deque, exactly like a stack.
A Warning About Cycles
This simple DFS version does not check for cycles. If the graph has a cycle, it will still print some order, but that order is meaningless.
If the input might contain a cycle, combine it with the three-state method from the Cycle Detection chapter:
state VISITING found → cycle, no topological order
otherwise → push node when it becomes DONEKahn's algorithm gives you cycle detection for free, which is one reason many people prefer it in interviews.
Kahn's Algorithm vs DFS Method
Kahn's Algorithm | DFS Method | |
|---|---|---|
Based on | BFS + indegree | DFS + postorder |
Data structure | Queue | Stack / recursion |
Cycle detection | Built in (count < V) | Needs the three-state check |
Recursion depth risk | None (iterative) | Deep graphs can overflow the stack |
Easy to get smallest order | Yes, use a priority queue | Not easily |
Time | O(V + E) | O(V + E) |
Space | O(V) | O(V) |
Both are correct. Learn both, because interviewers sometimes ask for a specific one.
Time and Space Complexity
For an adjacency list:
Time → O(V + E)
Space → O(V)In Kahn's algorithm:
Computing indegrees looks at every edge once:
O(E).Every vertex enters and leaves the queue once:
O(V).Every edge is used once to decrease an indegree:
O(E).
In the DFS method, it is a normal DFS: every vertex and every edge is processed once.
The extra space is the indegree array (or visited array), the queue (or stack), and the answer list, all O(V), not counting the graph itself.
Classic Problem: Course Schedule
This is one of the most asked graph problems in placements (LeetCode 207 and 210).
Problem: There are numCourses courses labelled 0 to numCourses - 1. You are given pairs [a, b], meaning you must take course b before course a. Return a valid order to take all courses, or an empty array if it is impossible.
The trick is building the edge in the right direction:
[a, b] means b must come before a → edge b → aAfter that, it is plain Kahn's algorithm.
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;
class Main {
static int[] findOrder(int numCourses, int[][] prerequisites) {
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
int[] indegree = new int[numCourses];
// [course, prereq] means prereq -> course
for (int[] p : prerequisites) {
int course = p[0];
int prereq = p[1];
graph.get(prereq).add(course);
indegree[course]++;
}
Queue<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
queue.add(i);
}
}
int[] order = new int[numCourses];
int index = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
order[index++] = node;
for (int next : graph.get(node)) {
if (--indegree[next] == 0) {
queue.add(next);
}
}
}
// cycle: not every course could be taken
if (index != numCourses) {
return new int[0];
}
return order;
}
public static void main(String[] args) {
int[][] prereq1 = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
int[][] prereq2 = {{1, 0}, {0, 1}};
System.out.println(Arrays.toString(findOrder(4, prereq1)));
System.out.println(Arrays.toString(findOrder(2, prereq2)));
}
}Output:
[0, 1, 2, 3]
[]In the first example, 0 unlocks 1 and 2, and both of them unlock 3. In the second example, 0 needs 1 and 1 needs 0, a cycle, so no order exists.
For Course Schedule I (just return true or false), return index == numCourses instead of the array.
Variation: The Smallest Topological Order
Sometimes the question asks for the lexicographically smallest topological order: whenever there is a choice, pick the smallest vertex.
Just replace the queue in Kahn's algorithm with a min priority queue (you learned this in the Priority Queue chapter):
import java.util.ArrayList;
import java.util.PriorityQueue;
class Main {
static ArrayList<Integer> smallestTopoSort(ArrayList<ArrayList<Integer>> graph) {
int vertices = graph.size();
int[] indegree = new int[vertices];
for (int u = 0; u < vertices; u++) {
for (int v : graph.get(u)) {
indegree[v]++;
}
}
// min-heap: always pick the smallest available vertex
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < vertices; i++) {
if (indegree[i] == 0) {
pq.add(i);
}
}
ArrayList<Integer> order = new ArrayList<>();
while (!pq.isEmpty()) {
int node = pq.poll();
order.add(node);
for (int neighbor : graph.get(node)) {
if (--indegree[neighbor] == 0) {
pq.add(neighbor);
}
}
}
return order;
}
public static void main(String[] args) {
int vertices = 6;
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
graph.add(new ArrayList<>());
}
graph.get(5).add(2);
graph.get(5).add(0);
graph.get(4).add(0);
graph.get(4).add(1);
graph.get(2).add(3);
graph.get(3).add(1);
System.out.println("Smallest order: " + smallestTopoSort(graph));
}
}Output:
Smallest order: [4, 5, 0, 2, 3, 1]At the start both 4 and 5 are available, so we take 4. Then only 5 is available. After 5, both 0 and 2 become available, and we pick the smaller one, 0.
Because each priority queue operation costs O(log V), the time becomes O(V log V + E).
Variation: Minimum Number of Semesters
If you can take any number of courses in one semester (as long as prerequisites are done), what is the minimum number of semesters?
Run Kahn's algorithm level by level, just like level-order BFS. All vertices in the queue at the same time form one semester.
For our graph:
Semester 1: 4, 5
Semester 2: 2, 0
Semester 3: 3
Semester 4: 1So the answer is 4. This is the idea behind problems like Parallel Courses (LeetCode 1136).
Is the Topological Order Unique?
Usually not. But it is unique exactly when, at every step of Kahn's algorithm, there is only one vertex in the queue.
For example:
A → B → C → Dhas only one valid order, A B C D.
But:
A → C
B → Chas two: A B C and B A C.
If a problem expects one specific answer, it will usually say something like "return the lexicographically smallest order" or "any valid order is accepted".
Real-Life Applications
Build tools like Maven, Gradle and Make compile modules only after the modules they depend on.
Package managers like npm and pip install dependencies before the package that needs them.
Spreadsheets recalculate a cell only after the cells its formula uses.
Task scheduling: project plans where some tasks must finish before others start.
Course planning: ordering subjects by prerequisites.
Compilers use it to order declarations and to schedule instructions.
Common Mistakes
1. Reversing the edge direction
For input [a, b] = "b before a", the edge is b → a. Building a → b gives the order completely backwards. Always read the problem statement carefully.
2. Forgetting to reverse the DFS postorder
If you add vertices to a list when DFS finishes them and print the list directly, you get the order backwards. Use a stack, or reverse the list at the end.
3. Adding the vertex before its neighbors in DFS
Pushing the vertex at the start of dfs() (preorder) does not give a topological order. It must be pushed after the loop.
4. Not checking for a cycle
In Kahn's algorithm, always compare the result size with V. In the DFS method, use the three states if the input can contain a cycle.
5. Starting only from vertex 0
Both methods must consider every vertex. Kahn's algorithm does this by adding all indegree-0 vertices to the queue, and the DFS method by looping over all vertices.
6. Using it on an undirected graph
Topological sort only makes sense for directed acyclic graphs.
Practice Problems
Topological Sort (GeeksforGeeks), the basic problem
Course Schedule (LeetCode 207), is a valid order possible?
Course Schedule II (LeetCode 210), return the order
Find Eventual Safe States (LeetCode 802), Kahn's algorithm on the reversed graph
Parallel Courses (LeetCode 1136), level-by-level Kahn's algorithm
Alien Dictionary (LeetCode 269 / GeeksforGeeks), build the graph from word order, then topologically sort the letters
Interview Tips
Keywords like prerequisite, dependency, must happen before, order of tasks or build order are strong hints for topological sort.
Say upfront that a valid order exists only if the graph is a DAG, and explain how you will detect a cycle.
Kahn's algorithm is usually the safest choice: iterative, easy to explain, and it detects cycles automatically.
Mention that multiple valid answers can exist, unless the problem asks for a specific one.
The Main Idea
Topological sort orders the vertices of a directed acyclic graph so that every edge u → v has u before v.
Possible only for a DAG
More than one valid order can existTwo ways to do it:
Kahn's Algorithm
repeatedly take a vertex with indegree 0
fewer than V vertices taken → cycle
DFS Method
push a vertex after all its neighbors are done
pop the stack (reverse postorder)Both run in:
Time → O(V + E)
Space → O(V)Whenever a problem says "do X before Y", draw an edge X → Y and think topological sort.