Topological sort using BFS
Topological sort using BFS is a medium graphs problem solved with the topological sort pattern.
The best approach, kahn's algorithm (bfs on in-degrees), runs in O(V + E) time and O(V) space.
Below are 2 approaches in Java, from dfs finish order up.
Problem
Return a topological order of a directed acyclic graph: an ordering of all vertices where, for every edge u → v, u comes before v. Use the BFS method (Kahn’s algorithm).
Examples
Example 1
- Input
V = 6, edges = [[5,2],[5,0],[4,0],[4,1],[2,3],[3,1]]- Output
[4, 5, 2, 0, 3, 1] (any valid order)- Why
- Every edge u → v has u before v.
Example 2
- Input
V = 3, edges = []- Output
[0, 1, 2]
Constraints
- The graph is a DAG (directed and acyclic).
1 <= V <= 10^4.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.
| Approach | Time | Space |
|---|---|---|
| DFS finish order | O(V + E) | O(V) |
| Kahn's algorithm (BFS on in-degrees) | O(V + E) | O(V) |
1DFS finish order
O(V + E)O(V)Run DFS; after a node's descendants are finished, push it on a stack. Popping the stack gives a topological order.
- dfs(u): mark; visit unvisited children; push u.
- Reverse the finish order.
class Solution {
public List<Integer> topoSort(int V, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
for (int[] e : edges) adj.get(e[0]).add(e[1]);
boolean[] seen = new boolean[V];
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < V; i++) if (!seen[i]) dfs(i, adj, seen, st);
return new ArrayList<>(st);
}
private void dfs(int u, List<List<Integer>> adj, boolean[] seen, Deque<Integer> st) {
seen[u] = true;
for (int v : adj.get(u)) if (!seen[v]) dfs(v, adj, seen, st);
st.push(u);
}
}2Kahn's algorithm (BFS on in-degrees)
O(V + E)O(V)Queue every node with in-degree 0. Pop one, append it to the order, and decrease the in-degree of its children; any child that reaches 0 joins the queue. If the order ends up shorter than V, the graph had a cycle.
- indeg[v] for all edges; queue nodes with indeg 0.
- Pop u; add to order; for v in adj[u]: if --indeg[v] == 0, enqueue v.
class Solution {
public List<Integer> topoSort(int V, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
int[] indeg = new int[V];
for (int[] e : edges) { adj.get(e[0]).add(e[1]); indeg[e[1]]++; }
Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < V; i++) if (indeg[i] == 0) q.add(i);
List<Integer> order = new ArrayList<>();
while (!q.isEmpty()) {
int u = q.poll();
order.add(u);
for (int v : adj.get(u)) if (--indeg[v] == 0) q.add(v);
}
return order;
}
}Edge cases to test
- Several nodes with in-degree 0 at the start
- Isolated nodes
Hints
Hint 1
A node can go first once nothing points to it any more (in-degree 0).
FAQ
What is the best time complexity for Topological sort using BFS?
Kahn's algorithm (BFS on in-degrees) runs in O(V + E) time and O(V) extra space.
Which pattern does Topological sort using BFS use?
It is a graphs problem that uses the topological sort pattern. Other problems with the same pattern: Course Schedule, Course Schedule II, Alien Dictionary.
Is there a brute force solution for Topological sort using BFS?
Yes. DFS finish order takes O(V + E) time and O(V) space. Run DFS; after a node's descendants are finished, push it on a stack.
Which edge cases should I test for Topological sort using BFS?
Several nodes with in-degree 0 at the start; Isolated nodes.