Shortest path by breadth-first search — Aptitude Question
Shortest path by breadth-first search: An undirected graph has these adjacency lists: | Vertex | Adjacent vertices… Answer and worked solution on CodeKairo.
- Topic: Data Structures & Algorithms
- Section: Programming MCQs
- Difficulty: Medium
- Time target: 105 seconds
Question
An undirected graph has these adjacency lists:
| Vertex | Adjacent vertices |
|---|---|
| A | B, C |
| B | A, D |
| C | A, E |
| D | B, E |
| E | C, D, F |
| F | E |
A breadth-first search from A is used to find the shortest path to F. How many edges does that path contain?
Options
- 2
- 3
- 4
- 5
Show the answer and the worked solution
Correct answer: B. 3
Worked solution
- BFS from A places B and C at distance 1.
- Expanding those puts D (reached from B) and E (reached from C) at distance 2.
- F is adjacent only to E, so F is discovered at distance 3, along A → C → E → F.
- That path uses 3 edges; the alternative A → B → D → E → F needs 4.
Answer: 3.
The idea
In an unweighted graph, BFS finds shortest paths because it settles all vertices at distance d before any at distance d + 1. Dijkstra's algorithm is the weighted generalisation.
Shortcut. F's only neighbour is E, and E is two hops from A through C, so the distance to F is 2 + 1 = 3.
Common trap. 4 follows the depth-first route A → B → D → E → F instead of the shorter path through C.
All Data Structures & Algorithms questions · placement mock tests