Why Most Interviews Get Graph Traversal Wrong
You've probably been told "use BFS for shortest path" a hundred times. And it's true — for unweighted graphs. But here's what nobody mentions: BFS can scan 10x more nodes than necessary if you're searching for a specific target in a large graph. Bidirectional search cuts that search space dramatically, yet I've seen maybe 3 interview candidates ever mention it.
Let me show you the actual runtime difference with working code.
The Mental Model: How Each Algorithm Explores
BFS grows like a circular wave from the source, visiting every node at distance $d$ before touching any node at distance $d+1$. For shortest path in unweighted graphs, it's optimal — first time you hit the target, you've found the shortest path. Time complexity $O(V + E)$ where $V$ is vertices and $E$ is edges.
DFS dives deep along one path until it hits a dead end, then backtracks. It's great for cycle detection and topological sorting, but for shortest path? Terrible. It might explore a path of length 1000 before checking a path of length 3. You'd need to explore every possible path and track the minimum, making it $O(V + E)$ for traversal but requiring full graph exploration to guarantee the shortest path.
Continue reading the full article on TildAlice
Top comments (0)