Question

Consider the following algorithm tt{someAlgo that takes an undirected graph \( G \) as input.} tt{someAlgo(G)} 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. 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. Output the distance between \( u \) and \( z \) in \( G \). The output of tt{someAlgo(T)} for the tree shown in the given figure is ___________ . (Answer in integer) \begin{center} \includegraphics{q59_fig.png} \end{center}

Hint:

To find the diameter of a tree, use two BFS traversals: first to find the farthest node from any starting node, and second to determine the farthest node from the previously found node.

Answer 1

Correct Answer: 6

Starting from an arbitrary vertex, the first traversal identifies a vertex that lies farthest from it. This vertex must lie at one extreme of the tree.

Beginning again from this extreme vertex and exploring the tree outward, the farthest vertex reached represents the opposite extreme.

The distance between these two extreme vertices corresponds to the longest possible simple path that exists in the tree.

Hence, the value produced by the algorithm is equal to the length of the longest path between any two vertices in the given tree.

Using the distances shown in the figure, this longest path has length:

\(\boxed{\text{(value obtained from the figure)}}\)