GATE CS 2014 Set 2 Q.24 (CS Q.14): Graph Traversals, Topological Sort and Connectivity

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

the shortest path between every pair of vertices.

the shortest path from $W$ to every vertex in the graph.

the shortest paths from $W$ to only those nodes that are leaves of $T$ .

the longest path in the graph.

Official answer and solution

Official answer: B
From: Official GATE 2014 answer key

Solution

Recall the structural property of Breadth-First Search (BFS) trees in unweighted graphs.

In an unweighted, connected, undirected graph $G$ , Breadth-First Search (BFS) explores vertices in increasing order of their hop distance from the start vertex $W$ .
A vertex at distance $d$ from $W$ is discovered only after all reachable vertices at distance $< d$ have been discovered.
The tree edges of the BFS tree $T$ connect each vertex $v$ to the predecessor vertex from which $v$ was first visited.
Consequently, the unique simple path from $W$ to any vertex $v$ along the tree edges in $T$ has minimum possible length (minimum number of edges) in $G$ .
Therefore, the BFS tree $T$ serves as a data structure representing the shortest path from $W$ to every vertex in the graph (option B).

Final answer

Common trap

Thinking BFS from a single source computes all-pairs shortest paths (which would require BFS from all vertices, O(V(V+E))).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 2
Question: 24 of 65, printed as CS Q.14
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source