GATE 2025 CS (CS2) – Question 59
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)
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 6
Explanation
On a tree, the double-BFS procedure returns the diameter. The longest path in the given tree has 6 edges, for example from a leaf on the far left through the central vertices to the far-right leaf.