Topological sort is an ordering of nodes in a directed graph where for every edge A → B, node A comes before node B. In simple language, it’s like figuring out the right order to do things when some tasks depend on others.
Think of college courses. We can’t take “Advanced Algorithms” before “Intro to Programming.” Topological sort gives us a valid order to take all courses.
Important: Topological sort only works on DAGs (Directed Acyclic Graphs). If there’s a cycle, no valid ordering exists — we can’t resolve circular dependencies.
Visual Example
Course Dependencies
Math
——→
Physics
——→
Engineering
Intro CS
——→
Algorithms
—↗
Valid order: Math → Intro CS → Physics → Algorithms → Engineering
Also valid: Intro CS → Math → Algorithms → Physics → Engineering
Multiple valid orderings can exist!
Approach 1: Kahn’s Algorithm (BFS with In-degree)
This is the most intuitive approach. The idea:
- Count in-degree (number of incoming edges) for each node
- Start with all nodes that have in-degree 0 (no dependencies)
- Process them, reduce in-degree of their neighbors
- When a neighbor’s in-degree hits 0, add it to the queue
- If we process all nodes, we have a valid ordering. If not, there’s a cycle.
// Kahn's Algorithm — BFS topological sort
function topoSort(numNodes, edges) {
const graph = Array.from({ length: numNodes }, () => []);
const inDegree = Array(numNodes).fill(0);
for (const [u, v] of edges) {
graph[u].push(v);
inDegree[v]++;
}
const queue = [];
for (let i = 0; i < numNodes; i++)
if (inDegree[i] === 0) queue.push(i); // start with no-dependency nodes
const order = [];
while (queue.length > 0) {
const node = queue.shift();
order.push(node);
for (const neighbor of graph[node]) {
inDegree[neighbor]--;
if (inDegree[neighbor] === 0) queue.push(neighbor);
}
}
return order.length === numNodes ? order : []; // empty = cycle exists
}# Kahn's Algorithm — BFS topological sort
from collections import deque
def topo_sort(num_nodes, edges):
graph = [[] for _ in range(num_nodes)]
in_degree = [0] * num_nodes
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(i for i in range(num_nodes) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == num_nodes else [] # empty = cycle// Kahn's Algorithm — BFS topological sort
int[] topoSort(int numNodes, int[][] edges) {
List<List<Integer>> graph = new ArrayList<>();
int[] inDegree = new int[numNodes];
for (int i = 0; i < numNodes; i++) graph.add(new ArrayList<>());
for (int[] e : edges) { graph.get(e[0]).add(e[1]); inDegree[e[1]]++; }
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numNodes; i++)
if (inDegree[i] == 0) queue.add(i);
int[] order = new int[numNodes];
int idx = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
order[idx++] = node;
for (int neighbor : graph.get(node))
if (--inDegree[neighbor] == 0) queue.add(neighbor);
}
return idx == numNodes ? order : new int[0]; // empty = cycle
}Approach 2: DFS-based Topological Sort
The DFS approach uses post-order traversal. We do DFS, and after we’ve fully explored all descendants of a node, we add it to a stack. The stack gives us the reverse topological order.
// DFS-based topological sort
function topoSortDFS(numNodes, edges) {
const graph = Array.from({ length: numNodes }, () => []);
for (const [u, v] of edges) graph[u].push(v);
const visited = new Set();
const stack = []; // result in reverse order
function dfs(node) {
visited.add(node);
for (const neighbor of graph[node])
if (!visited.has(neighbor)) dfs(neighbor);
stack.push(node); // add AFTER processing all children
}
for (let i = 0; i < numNodes; i++)
if (!visited.has(i)) dfs(i);
return stack.reverse(); // reverse gives topological order
}# DFS-based topological sort
def topo_sort_dfs(num_nodes, edges):
graph = [[] for _ in range(num_nodes)]
for u, v in edges:
graph[u].append(v)
visited = set()
stack = [] # result in reverse order
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
stack.append(node) # add AFTER processing all children
for i in range(num_nodes):
if i not in visited:
dfs(i)
return stack[::-1] # reverse gives topological order// DFS-based topological sort
int[] topoSortDFS(int numNodes, int[][] edges) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numNodes; i++) graph.add(new ArrayList<>());
for (int[] e : edges) graph.get(e[0]).add(e[1]);
boolean[] visited = new boolean[numNodes];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < numNodes; i++)
if (!visited[i]) dfs(graph, i, visited, stack);
int[] order = new int[numNodes];
for (int i = 0; i < numNodes; i++) order[i] = stack.pop();
return order;
}
void dfs(List<List<Integer>> graph, int node, boolean[] visited, Deque<Integer> stack) {
visited[node] = true;
for (int neighbor : graph.get(node))
if (!visited[neighbor]) dfs(graph, neighbor, visited, stack);
stack.push(node); // post-order
}Classic Problem: Course Schedule
LeetCode 207 — Given numCourses and prerequisite pairs, determine if we can finish all courses. This is just cycle detection in a directed graph. If we can topologically sort all nodes, there’s no cycle.
// Can we finish all courses? (cycle detection via Kahn's)
function canFinish(numCourses, prerequisites) {
const graph = Array.from({ length: numCourses }, () => []);
const inDegree = Array(numCourses).fill(0);
for (const [course, prereq] of prerequisites) {
graph[prereq].push(course);
inDegree[course]++;
}
const queue = [];
for (let i = 0; i < numCourses; i++)
if (inDegree[i] === 0) queue.push(i);
let count = 0;
while (queue.length > 0) {
const node = queue.shift();
count++;
for (const next of graph[node])
if (--inDegree[next] === 0) queue.push(next);
}
return count === numCourses; // processed all = no cycle
}# Can we finish all courses? (cycle detection via Kahn's)
from collections import deque
def can_finish(num_courses, prerequisites):
graph = [[] for _ in range(num_courses)]
in_degree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque(i for i in range(num_courses) if in_degree[i] == 0)
count = 0
while queue:
node = queue.popleft()
count += 1
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return count == num_courses # processed all = no cycle// Can we finish all courses? (cycle detection via Kahn's)
boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
int[] inDegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
for (int[] p : prerequisites) {
graph.get(p[1]).add(p[0]);
inDegree[p[0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++)
if (inDegree[i] == 0) queue.add(i);
int count = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
count++;
for (int next : graph.get(node))
if (--inDegree[next] == 0) queue.add(next);
}
return count == numCourses;
}Kahn’s vs DFS: Which to Use?
| Kahn’s (BFS) | DFS-based | |
|---|---|---|
| Intuition | Easy to understand — remove nodes with no deps | Less intuitive (post-order) |
| Cycle detection | Built-in (if count != numNodes) | Need extra state (3-color marking) |
| Interview preference | More common, easier to explain | Shorter code |
Interview tip: Kahn’s algorithm is usually the safer choice. It’s easier to explain, cycle detection comes for free, and interviewers see it more often.
Complexity
- Time: O(V + E) — we visit every node and edge once
- Space: O(V + E) — graph storage plus the queue/stack
Topological sort shows up in build systems, package managers, course scheduling, and task dependency resolution. Whenever we see “ordering with dependencies” in an interview, this is our tool.