← All Comparisons
BFS vs Topological Sort
Quick Answer
Use BFS when you need the shortest path in an unweighted graph, level-order traversal, or minimum steps to reach a target. Use Topological Sort when you need a valid ordering of nodes in a DAG (e.g., course prerequisites, task scheduling, build order). Kahn's algorithm uses a queue like BFS but processes nodes by in-degree to produce an ordering, not distances.
Side-by-Side Comparison
| Aspect | BFS | Topological Sort |
|---|---|---|
| Primary goal | Shortest path, level-order traversal | Valid linear ordering respecting dependencies |
| Graph requirement | Any graph (directed or undirected) | DAG only (no cycles) |
| Queue semantics | Process by distance from source | Process by in-degree (Kahn) or DFS post-order |
| What we track | Visited, distance/level from start | In-degree per node, or DFS state |
| Output | Distances, path, or level-by-level nodes | Ordered list where u before v if u → v |
| Typical problems | Word ladder, rotting oranges, shortest path in grid | Course schedule, task scheduling, build order |
| Cycle handling | Visited set prevents re-processing | Cycle detection: if result length < n, cycle exists |
Decision Framework
- Does the problem ask for "shortest path", "minimum steps", or "level order"? Use BFS.
- Does the problem ask for "valid order", "prerequisites", or "dependency order"? Use Topological Sort.
- Are there explicit dependencies (A before B)? Model as DAG, use topological sort.
- Is it a grid or graph where you need distance from start? Use BFS.
- Kahn's algorithm uses BFS-style queue — but for in-degree zero nodes, not distance. Don't confuse the two goals.
- Need both ordering and longest path in DAG? Topological sort first, then DP over the order.
Example Problems
BFS
- 1.Word Ladder — Shortest transformation sequence; BFS by edit distance.
- 2.Rotting Oranges — Multi-source BFS for minimum time to rot all.
- 3.01 Matrix — BFS from all zeros to find nearest 0 for each cell.
- 4.Binary Tree Level Order — Process nodes level by level.
Topological Sort
- 1.Course Schedule — Check if DAG (no cycle), output valid order.
- 2.Alien Dictionary — Build graph from order constraints, topological sort.
- 3.Sequence Reconstruction — Verify unique topological order matches sequences.
- 4.Longest Path in DAG — Topological sort, then DP along the order.