The GATE Grind

GATE 2014 CS (CS2) – Question 24

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 1 mark · Multiple choice

A BFS from W in an unweighted connected undirected graph gives tree T. T is a data structure for computing ______.

  1. shortest paths between every vertex pair
  2. shortest paths from W to every vertex
  3. shortest paths from W only to leaves of T
  4. the longest path in the graph

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) shortest paths from W to every vertex

Explanation

BFS discovers vertices in nondecreasing distance from its source in an unweighted graph. Each tree path from W therefore has the minimum number of edges to that vertex. Thus **B**, shortest paths from W to every vertex. It does not simultaneously preserve all-pairs shortest paths.