How do you find the shortest path in an unweighted graph?

Difficulty: 3/10

Breadth-First Search, Graph Traversal, Shortest Path

Shortest Path in Unweighted Graph

Use BFS starting from the source. BFS explores vertices in increasing order of the number of edges from the source, so the first time a vertex is discovered its distance is the shortest number of edges from the source. A parent array can reconstruct the actual path.

javascript

1
Algorithm: BFS.
2
Shortest distance means minimum number of edges.
3
Time: O(V+E) with adjacency lists.
4
Space: O(V).
5
Parent pointers allow path reconstruction.

Scenario Questions

0-2 years experience

2-5 years experience

1Our feature needs to compute the fewest hops between two users in a social network graph stored in memory. How would you implement it, and what edge cases would you watch out for?

Follow-up Questions