Consider the tree arcs of a BFS traversal from a source node W in an…
2014
Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing
- A.
the shortest path between every pair of vertices.
- B.
the shortest path from W to every vertex in the graph.
- C.
the shortest paths from W to only those nodes that are leaves of T.
- D.
the longest path in the graph.
Attempted by 272 students.
Show answer & explanation
Correct answer: B
Answer: The BFS tree T rooted at W gives shortest paths (measured by number of edges) from W to every vertex in the graph.
Key idea: BFS explores vertices in layers by distance (number of edges) from the source W. Vertices discovered at distance d are discovered before any vertex at distance d+1.
Proof sketch: When BFS first discovers a vertex v it sets a parent pointer to the vertex that discovered v. If there were a strictly shorter path from W to v than the one given by following parent pointers, BFS would have discovered v earlier via that shorter path, contradicting the discovery order. Therefore the parent pointers define a shortest path from W to each vertex.
How to recover a shortest path: Follow parent pointers from any vertex back to W; this sequence of edges is a shortest path from W to that vertex.
Clarification: This statement depends on the graph being unweighted (or all edges having equal weight). For weighted graphs with non-equal positive weights, use Dijkstra's algorithm; for all-pairs shortest paths use repeated single-source algorithms or Floyd–Warshall.
A video solution is available for this question — log in and enroll to watch it.