Graphs
Topological Sort Dependency Ordering
Order vertices of a directed acyclic graph so that every edge points forward — prerequisites before dependents, courses before advanced courses, tasks before the tasks that need them. Two algorithms: Kahn's BFS and DFS post-order.
Foundations · Array · Linked List · Stack · Queue · HashMap · Binary Tree · Graph · BFS · DFS · Topo Sort · Shortest Path · Sorting
01
Section One · Foundation
What is Topological Sort?
A topological sort produces a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u→v, vertex u appears before vertex v in the ordering. It answers the question: "in what order should I process these tasks if some tasks depend on others?" The ordering is NOT unique — a DAG may have multiple valid topological orders. Topological sort only works on DAGs; if the graph has a cycle, no valid ordering exists (you can't put A before B and B before A simultaneously). There are two standard algorithms: Kahn's algorithm (BFS-based, using in-degrees) and DFS post-order (reverse the finish order). Both run in O(V + E). Topological sort appears in interviews as "Course Schedule" (LC 207/210), build dependency resolution, compilation order, and any problem where you need to process nodes in dependency order.
Analogy: Getting dressed in the morning. You must put on underwear before pants, socks before shoes, but shirt and pants are independent. A topological sort gives you one valid order: underwear → pants → shirt → socks → shoes. Another valid order: shirt → underwear → socks → pants → shoes. Both respect every "must come before" constraint. If you had a rule "pants before underwear AND underwear before pants," no valid ordering exists — that's a cycle.
02
Section Two · Mental Model
How It Thinks
A vertex with in-degree 0 has no prerequisites — it can be processed immediately
▶
Kahn's algorithm starts with ALL in-degree-0 vertices in a queue — these are the "ready" tasks. Process one, reduce neighbours' in-degrees, add newly-ready ones to the queue.
When you finish DFS on a vertex (all descendants explored), it has no remaining dependencies below it
▶
Add it to the result on DFS FINISH (post-order). Reverse the post-order → topological order. Alternatively, push onto a stack and pop at the end.
If the graph has a cycle, Kahn's queue empties before all vertices are processed
▶
If result.size() < V after Kahn's completes → cycle detected. This gives cycle detection as a bonus — "Course Schedule I" (LC 207) is just "does topo sort succeed?"
In DFS, a cycle exists if you visit a vertex that's currently on the recursion stack (grey state)
▶
Three-colour marking: WHITE = unvisited, GREY = in progress (on stack), BLACK = finished. Edge to GREY = back edge = cycle.
Topological sort ordering is NOT unique — parallel tasks can appear in any relative order
▶
Kahn's produces a specific order determined by queue processing (often lexicographic-smallest if using a PriorityQueue). DFS produces a different valid order. Both are correct.
Both algorithms visit each vertex once and each edge once
▶
Time: O(V + E). Space: O(V) for the in-degree array (Kahn's) or recursion stack (DFS). Both are optimal.
03
Section Three · Kahn's BFS
Kahn's Algorithm (BFS + In-Degree)
Kahn's algorithm works by repeatedly removing vertices with no incoming edges (in-degree 0). When you remove a vertex, decrement the in-degree of all its neighbours. If a neighbour's in-degree drops to 0, it's now "ready" — add it to the queue. Continue until the queue is empty. If all vertices were processed, the order is valid; otherwise, a cycle exists.
Pseudocode — Kahn's Algorithm
function kahnTopoSort(V, edges):
// 1. Build adjacency list + compute in-degrees
adj = adjacency list from edges
inDegree = int[V] // count of incoming edges for each edge (u → v):
inDegree[v]++
// 2. Enqueue all vertices with in-degree 0
queue = []
for v = 0 to V - 1:
if inDegree[v] == 0: queue.add(v)
// 3. Process the queue
order = []
while queue not empty:
u = queue.poll()
order.add(u)
for each neighbour v of u:
inDegree[v]--
if inDegree[v] == 0: queue.add(v)
// 4. Cycle check if order.size < V: return "cycle exists!" return order // O(V + E)
Kahn's step-by-step on a 6-vertex DAG
Kahn's is the interview favourite:
- It's iterative (no recursion stack overflow), gives the topological order directly, and detects cycles as a bonus (
order.size() < V). - For "Course Schedule II" (LC 210), it's the cleanest solution.
04
Section Four · DFS Post-Order
DFS-Based Topological Sort
Run DFS from every unvisited vertex. When a vertex finishes (all descendants explored), push it onto a stack (or prepend to a list). The final stack order (top to bottom) is a valid topological order. Intuitively: a vertex finishes AFTER all its dependents finish — so reversing the finish order puts prerequisites first.
Pseudocode — DFS Topo Sort
function dfsTopoSort(V, adj):
visited = boolean[V]
stack = [] // result in reverse for v = 0 to V - 1:
if !visited[v]: dfs(v)
return stack.reversed() // or pop from stack function dfs(u):
visited[u] = true for each neighbour v of u:
if !visited[v]: dfs(v)
stack.push(u) // add on FINISH (post-order)
Why post-order?:
- In DFS, a vertex finishes after ALL its descendants have finished. If u→v, then v finishes before u.
- So in the post-order list, v appears before u — reversing gives u before v, which is topological order.
05
Section Five · Cycle Detection
Detecting Cycles in DAGs
A topological sort only exists for DAGs. If the graph has a cycle, we need to detect it and return "impossible." Both algorithms detect cycles naturally:
Kahn's (BFS)
Count processed vertices
If order.size() < V after the queue empties, some vertices never reached in-degree 0 — they're part of a cycle. This is the cleanest cycle detection for directed graphs.
DFS (3-colour)
Detect back edges
Mark vertices: WHITE (unvisited), GREY (in progress), BLACK (done). If DFS reaches a GREY vertex → back edge → cycle. This is the standard directed cycle detection.
DFS 3-Colour Cycle Detection
// 0 = WHITE, 1 = GREY, 2 = BLACK int[] colour = new int[V];
boolean hasCycle(int u) {
colour[u] = 1; // GREY — in progress for (int v : adj[u]) {
if (colour[v] == 1) return true; // back edge → cycle! if (colour[v] == 0 && hasCycle(v)) return true;
}
colour[u] = 2; // BLACK — done return false;
}
Course Schedule I (LC 207) = cycle detection.:
- "Can you finish all courses?" = "Is the prerequisite graph a DAG?" Run Kahn's and check
order.size() == numCourses. - If yes → return true. If no → cycle → return false.
06
Section Six · Comparison
Kahn's vs DFS — Which to Use
| Aspect | Kahn's (BFS) | DFS Post-Order |
|---|---|---|
| Approach | Iterative (queue) | Recursive (stack) |
| Cycle detection | order.size() < V | GREY→GREY back edge |
| Output | Direct topological order | Reverse of post-order |
| Stack overflow risk | None (iterative) | Yes, on deep graphs |
| Lexicographic order | Easy: use PriorityQueue | Harder to guarantee |
| Interview preference | ✓ More common, cleaner | Option if DFS is already built |
| Time / Space | O(V+E) / O(V) | O(V+E) / O(V) |
Interview default: Kahn's.:
- It's iterative, gives the answer directly, and cycle detection is a one-line check.
- Use DFS only when the problem already requires DFS traversal (e.g., "Alien Dictionary" where you build the graph AND topo-sort it).
07
Section Seven · When to Use
When to Reach for Topological Sort
| Signal | Pattern | Example |
|---|---|---|
| "prerequisites" / "dependencies" / "ordering" | Topo sort (Kahn's) | Course Schedule I & II (LC 207, 210) |
| "can all tasks be completed?" | Cycle detection via topo sort | Course Schedule I (LC 207) |
| "return an ordering that satisfies all constraints" | Kahn's or DFS topo sort | Course Schedule II (LC 210) |
| "alien dictionary" / "infer order from comparisons" | Build DAG from pairs → topo sort | Alien Dictionary (LC 269) |
| "parallel task scheduling" / "minimum time" | Topo sort + level tracking (longest path in DAG) | Parallel Courses (LC 1136) |
| "compilation order" / "build order" | Topo sort on dependency graph | Build system dependencies |
08
Section Eight · Implementation
Build It Once
Build Kahn's once — it's the interview standard. The structure is always the same: build adjacency list, compute in-degrees, BFS from in-degree-0 vertices, check cycle.
Java — Course Schedule II (Kahn's)
// Course Schedule II — LC 210 — O(V + E) int[] findOrder(int numCourses, int[][] prereqs) {
List<List<Integer>> adj = new ArrayList<>();
int[] inDeg = new int[numCourses];
for (int i = 0; i < numCourses; i++)
adj.add(new ArrayList<>());
for (int[] p : prereqs) {
adj.get(p[1]).add(p[0]); // prereq → course
inDeg[p[0]]++;
}
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++)
if (inDeg[i] == 0) queue.offer(i);
int[] order = new int[numCourses];
int idx = 0;
while (!queue.isEmpty()) {
int u = queue.poll();
order[idx++] = u;
for (int v : adj.get(u))
if (--inDeg[v] == 0) queue.offer(v);
}
return idx == numCourses ? order : new int[0];
}
Topological Sort — Full Implementation
Java — Kahn's + DFS topo sort
import java.util.*;
public class TopologicalSort {
// ═══ 1. Kahn's (BFS) — Course Schedule II ═ O(V+E) static int[] findOrder(int n, int[][] prereqs) {
List<List<Integer>> adj = new ArrayList<>();
int[] inDeg = new int[n];
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] p : prereqs) {
adj.get(p[1]).add(p[0]);
inDeg[p[0]]++;
}
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++)
if (inDeg[i] == 0) q.offer(i);
int[] order = new int[n];
int idx = 0;
while (!q.isEmpty()) {
int u = q.poll();
order[idx++] = u;
for (int v : adj.get(u))
if (--inDeg[v] == 0) q.offer(v);
}
return idx == n ? order : new int[0]; // empty = cycle
}
// ═══ 2. Course Schedule I (cycle check only) ═ O(V+E) static boolean canFinish(int n, int[][] prereqs) {
return findOrder(n, prereqs).length > 0;
}
// ═══ 3. DFS-based topo sort ═════════════ O(V+E) static int[] topoSortDFS(int n, List<List<Integer>> adj) {
int[] colour = new int[n]; // 0=white, 1=grey, 2=black Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++)
if (colour[i] == 0 && dfsCycle(i, adj, colour, stack))
return new int[0]; // cycle int[] order = new int[n];
for (int i = 0; i < n; i++) order[i] = stack.pop();
return order;
}
static boolean dfsCycle(int u, List<List<Integer>> adj,
int[] colour, Deque<Integer> stack) {
colour[u] = 1; // grey for (int v : adj.get(u)) {
if (colour[v] == 1) return true; // cycle if (colour[v] == 0 && dfsCycle(v, adj, colour, stack))
return true;
}
colour[u] = 2; // black
stack.push(u); // post-order return false;
}
// ═══ 4. Alien Dictionary ════════════════ O(C) C = total chars static String alienOrder(String[] words) {
Map<Character, Set<Character>> adj = new HashMap<>();
Map<Character, Integer> inDeg = new HashMap<>();
for (String w : words)
for (char c : w.toCharArray()) {
adj.putIfAbsent(c, new HashSet<>());
inDeg.putIfAbsent(c, 0);
}
for (int i = 0; i < words.length - 1; i++) {
String w1 = words[i], w2 = words[i + 1];
int len = Math.min(w1.length(), w2.length());
if (w1.length() > w2.length() && w1.startsWith(w2))
return ""; // invalid: "abc" before "ab" for (int j = 0; j < len; j++) {
if (w1.charAt(j) != w2.charAt(j)) {
if (adj.get(w1.charAt(j)).add(w2.charAt(j)))
inDeg.merge(w2.charAt(j), 1, Integer::sum);
break;
}
}
}
// Kahn's on the character graph Deque<Character> q = new ArrayDeque<>();
for (char c : inDeg.keySet())
if (inDeg.get(c) == 0) q.offer(c);
StringBuilder sb = new StringBuilder();
while (!q.isEmpty()) {
char c = q.poll();
sb.append(c);
for (char next : adj.get(c))
if (inDeg.merge(next, -1, Integer::sum) == 0)
q.offer(next);
}
return sb.length() == inDeg.size() ? sb.toString() : "";
}
// ═══ Main ═══════════════════════════════════ public static void main(String[] args) {
System.out.println(Arrays.toString(
findOrder(4, new int[][]{{1,0},{2,0},{3,1},{3,2}})));
// [0, 1, 2, 3] or [0, 2, 1, 3] System.out.println(canFinish(2, new int[][]{{0,1},{1,0}}));
// false — cycle
}
}
Python — Topological sort
from collections import deque, defaultdict
# ═══ 1. Kahn's — Course Schedule II ══════ O(V+E) def find_order(n, prereqs):
adj = defaultdict(list)
in_deg = [0] * n
for course, pre in prereqs:
adj[pre].append(course)
in_deg[course] += 1
q = deque(i for i in range(n) if in_deg[i] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
in_deg[v] -= 1
if in_deg[v] == 0:
q.append(v)
return order if len(order) == n else []
# ═══ 2. Can finish? (cycle check) ════════ O(V+E) def can_finish(n, prereqs):
return len(find_order(n, prereqs)) == n
# ═══ 3. DFS-based topo sort ══════════════ O(V+E) def topo_sort_dfs(n, adj):
WHITE, GREY, BLACK = 0, 1, 2
colour = [WHITE] * n
stack = []
def dfs(u):
colour[u] = GREY
for v in adj[u]:
if colour[v] == GREY: return False if colour[v] == WHITE and not dfs(v): return False
colour[u] = BLACK
stack.append(u)
return True for i in range(n):
if colour[i] == WHITE and not dfs(i):
return []
return stack[::-1]
# ═══ 4. Alien Dictionary ═════════════════ O(C) def alien_order(words):
adj = defaultdict(set)
in_deg = {c: 0 for w in words for c in w}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i+1]
if len(w1) > len(w2) and w1.startswith(w2):
return "" for a, b in zip(w1, w2):
if a != b:
if b not in adj[a]:
adj[a].add(b)
in_deg[b] += 1
break
q = deque(c for c in in_deg if in_deg[c] == 0)
result = []
while q:
c = q.popleft()
result.append(c)
for nxt in adj[c]:
in_deg[nxt] -= 1
if in_deg[nxt] == 0:
q.append(nxt)
return "".join(result) if len(result) == len(in_deg) else "" # Demo
print(find_order(4, [[1,0],[2,0],[3,1],[3,2]])) # [0,1,2,3]
print(can_finish(2, [[0,1],[1,0]])) # False
09
Section Nine · Java Reference
Use It In Java
IN JAVA — Topological Sort Patterns
Adjacency list
List<List<Integer>> adj = new ArrayList<>(); — initialise n empty lists In-degree array
int[] inDeg = new int[n]; — increment for each incoming edge Queue
Deque<Integer> q = new ArrayDeque<>(); — Kahn's BFS queue | Kahn's Step | Java Code | Note |
|---|---|---|
| Build graph | adj.get(u).add(v); inDeg[v]++; | Read edge direction carefully (prereq→course) |
| Seed queue | if (inDeg[i] == 0) q.offer(i); | All vertices with no incoming edges |
| Process | int u = q.poll(); order[idx++] = u; | Take one ready vertex |
| Decrement | if (--inDeg[v] == 0) q.offer(v); | Pre-decrement + check in one line |
| Cycle check | return idx == n ? order : new int[0]; | Empty array = cycle detected |
⚠ Gotcha: Edge direction matters! In "Course Schedule," prerequisites are given as
[course, prereq] — the edge goes FROM prereq TO course (adj.get(prereq).add(course)). Reversing this produces a wrong answer. Always clarify: "X is a prerequisite of Y" means edge X→Y.
⚠ Gotcha: For lexicographically smallest topo order, replace
ArrayDeque with PriorityQueue in Kahn's. The min-heap always picks the smallest ready vertex first. This changes nothing about correctness but guarantees a unique canonical ordering.
10
Section Ten · Practice
Problems To Solve
Topological sort appears in interviews as "Course Schedule" or a disguised dependency-ordering problem. The key skill is recognising "prerequisites = directed edges → topo sort." Once recognised, Kahn's template is mechanical. The hard problems (Alien Dictionary, Parallel Courses) add a graph-construction step before the topo sort itself.
| Difficulty | Pattern | Problem | Key Insight |
|---|---|---|---|
| Medium | cycle | Course Schedule — LC 207 | "Can you finish all courses?" = "Is the graph a DAG?" Run Kahn's, check order.size() == numCourses. |
| Medium | topo | Course Schedule II — LC 210 | Return a valid ordering. Kahn's directly produces the answer. Return empty array if cycle. |
| Hard | topo+build | Alien Dictionary — LC 269 | Build a character DAG from adjacent word pairs (first differing character = edge). Then Kahn's on the character graph. Edge case: "abc" before "ab" is invalid. |
| Medium | topo+dp | Parallel Courses — LC 1136 | Topo sort with level tracking. Process layer by layer (like BFS levels). Number of layers = minimum semesters. If cycle → return -1. |
| Medium | topo | Minimum Height Trees — LC 310 | Not a classic topo sort but uses the in-degree peeling technique: repeatedly remove leaves (degree 1) until 1–2 nodes remain. Those are the roots of minimum-height trees. |
| Medium | topo | Longest Increasing Path in a Matrix — LC 329 | Each cell is a node, edge from smaller to larger neighbour. Topo sort on this implicit DAG. Longest path = max level in topo order. Also solvable with DFS + memoisation. |
Interview Pattern:
- When you see "prerequisites," "dependencies," "ordering constraints," or "can all tasks be completed" — think topological sort.
- Build the graph, run Kahn's, check for cycles.
- The template is always: in-degree array → seed queue → BFS process → check
count == V.