Shortest path (fewest edges) in an unweighted graph?
Options
- DFS
- BFS (Correct option)
- Dijkstra with a max-heap
- Topological sort
Answer
BFS
Why
BFS (breadth-first search) explores in rings: first all neighbors 1 step away, then all at 2 steps, and so on, using a queue.
So the first time BFS reaches a node, it got there with the fewest possible edges.
DFS goes deep along one path first, so the first path it finds may be long. Cost of BFS: O(V + E).
Remember
Fewest steps in an unweighted graph → BFS.