Consider the following algorithm someAlgo that takes an undirected graph 𝐺 as…
2025
Consider the following algorithm someAlgo that takes an undirected graph 𝐺 as input.
someAlgo(𝐺)
1. Let 𝑣 be any vertex in 𝐺. Run BFS on 𝐺 starting at 𝑣. Let 𝑢 be a vertex in 𝐺 at maximum distance from 𝑣 as given by the BFS.
2. Run BFS on 𝐺 again with 𝑢 as the starting vertex. Let 𝑧 be the vertex at maximum distance from 𝑢 as given by the BFS.
3. Output the distance between 𝑢 and 𝑧 in 𝐺.
The output of someAlgo(𝑇) for the tree shown in the given figure is ___________. (Answer in integer)
Attempted by 74 students.
Show answer & explanation
Correct answer: 6
Key idea: in any tree, running BFS from an arbitrary vertex to find a farthest vertex u, then running BFS from u to find a farthest vertex z, returns the diameter of the tree (the maximum distance between any two vertices).
Reason why this works: in a tree, a farthest vertex found by BFS from any start is an endpoint of some longest path. A subsequent BFS from that endpoint reaches the opposite endpoint of a longest path, so the distance found is the diameter.
Apply to the given tree: identify one longest path across the tree from a leftmost leaf to a rightmost leaf. Tracing that path across the drawing visits 7 vertices and therefore has 6 edges.
Thus the algorithm outputs the distance between those two endpoints, which is 6.
Final answer: 6
A video solution is available for this question — log in and enroll to watch it.