Contents
- Kahn's Algorithm (BFS / Indegree)
- DFS Approach
- Complexity Analysis
Kahn's algorithm works by repeatedly removing nodes with indegree 0
(no incoming edges — no prerequisites). It also detects cycles: if the topological order
contains fewer than V vertices, the graph has a cycle.
Algorithm steps:
- Compute the indegree of every vertex.
- Enqueue all vertices with indegree 0.
- While the queue is non-empty: dequeue a vertex, add it to the result, and decrement the indegree of all its neighbours. Enqueue any neighbour whose indegree reaches 0.
- If result size < V, a cycle exists.
import java.util.*;
public List<Integer> topoSort(int V, List<List<Integer>> adj) {
int[] indegree = new int[V];
// Calculate indegrees
for (int u = 0; u < V; u++) {
for (int v : adj.get(u)) {
indegree[v]++;
}
}
// Enqueue all nodes with no incoming edges
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < V; i++) {
if (indegree[i] == 0) queue.offer(i);
}
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
int u = queue.poll();
order.add(u);
for (int v : adj.get(u)) {
indegree[v]--;
if (indegree[v] == 0) queue.offer(v);
}
}
// If order.size() != V, cycle detected
if (order.size() != V) throw new RuntimeException("Cycle detected — topological sort impossible");
return order;
}
Example:
// Graph: 5 → 0, 5 → 2, 4 → 0, 4 → 1, 2 → 3, 3 → 1
// Expected order (one valid): [4, 5, 2, 0, 3, 1]
int V = 6;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
adj.get(5).add(0); adj.get(5).add(2);
adj.get(4).add(0); adj.get(4).add(1);
adj.get(2).add(3);
adj.get(3).add(1);
System.out.println(topoSort(V, adj)); // [4, 5, 0, 2, 3, 1] (one valid order)
In the DFS approach, after fully exploring a node's descendants, push it onto a stack.
The reverse of the stack gives the topological order.
public List<Integer> topoSortDFS(int V, List<List<Integer>> adj) {
boolean[] visited = new boolean[V];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < V; i++) {
if (!visited[i]) {
dfs(i, adj, visited, stack);
}
}
List<Integer> order = new ArrayList<>();
while (!stack.isEmpty()) order.add(stack.pop());
return order;
}
private void dfs(int u, List<List<Integer>> adj, boolean[] visited, Deque<Integer> stack) {
visited[u] = true;
for (int v : adj.get(u)) {
if (!visited[v]) dfs(v, adj, visited, stack);
}
stack.push(u); // push after all descendants are processed
}
- Time: O(V + E) — every vertex and edge is processed once.
- Space: O(V) — indegree array / visited array / queue / stack.
Kahn's algorithm is preferred when you also need to detect cycles (check if result size == V).
The DFS approach is preferred when you need a post-order completion time or are already using DFS for other purposes.