GATE CS 2014 Set 2 Q14 — Graph Traversals (BFS, DFS)

Breadth-First Search (BFS) on an unweighted, connected, undirected graph explores vertices level by level, starting from a source vertex $W$.

During BFS, when we traverse an edge to discover an unvisited vertex, that edge becomes a tree arc. The collection of these tree arcs forms a BFS tree $T$ rooted at $W$.

• Shortest Path Property: For any vertex $v$ in the graph, the unique path from the root $W$ to $v$ in the BFS tree $T$ has the minimum possible number of edges. Thus, it represents the shortest path from $W$ to $v$ in the unweighted graph.
• Since the graph is connected, BFS visits every vertex. Therefore, the tree $T$ contains the shortest path from $W$ to every vertex in the graph.

Analyzing the Options:

• Option A: Incorrect. BFS from a single source $W$ only computes shortest paths originating from $W$, not between every arbitrary pair of vertices.
• Option B: Correct. The BFS tree $T$ provides the shortest path from the source $W$ to all vertices in the graph.
• Option C: Incorrect. The shortest paths are computed for all vertices in the tree, not just the leaf nodes.
• Option D: Incorrect. BFS is not used for finding longest paths.