The GATE Grind

GATE 2025 CS (CS2) – Question 59

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Numerical answer

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)

Diagram for GATE 2025 CS (CS2) question 59

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 6

Explanation

someAlgo is the standard two-BFS method for finding the **diameter** of a tree:
1. BFS from any vertex $v$. The farthest vertex $u$ is an end of some longest path.
2. BFS from $u$. The farthest vertex $z$ is the other end, and $d(u,z)$ is the diameter.

For the tree in the figure the longest path has 6 edges, so the output is $\mathbf{6}$.

More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →