GATE CS 2025 Set 2 | Question 59

NAT · 2 marks

Consider the following algorithm someAlgo that takes an undirected graph \(G\) as input.

someAlgo(\(G\))

  1. Let \(v\) be any vertex in \(G\). Run BFS on \(G\) starting at \(v\). Let \(u\) be a vertex in \(G\) at maximum distance from \(v\) as given by the BFS.
  2. Run BFS on \(G\) again with \(u\) as the starting vertex. Let \(z\) be the vertex at maximum distance from \(u\) as given by the BFS.
  3. Output the distance between \(u\) and \(z\) in \(G\).

The output of someAlgo(\(T\)) for the tree shown in the given figure is ___________. (Answer in integer)

A tree with 14 vertices drawn as dots joined by edges. One vertex is joined to a leaf, to a vertex with two further leaves, to a vertex with one further leaf, and to a second branching vertex; that second vertex has two leaves and one more neighbour, which has a leaf and a two-edge path hanging from it.

Answer

6

Explanation

On a tree, a vertex farthest from any start vertex is always an end of a longest path, so the second BFS measures the tree's diameter: the largest distance, in edges, between two vertices.

In the figure, a longest path starts at the lowest leaf on the far left, goes up to its neighbour and the left branching vertex, crosses to the central branching vertex, and follows the right branch through two more vertices to the rightmost leaf: 6 edges. The topmost leaf also reaches the rightmost leaf in 6 edges, and no two vertices are farther apart.

So the output is 6 whichever start vertex \(v\) is chosen.

Answer: 6