GATE CS 2025 Set 2 Q.59: Graph Traversals, Topological Sort and Connectivity

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)

Unlabeled tree T with 14 vertices and 13 edges whose longest path (diameter) consists of 6 edges.

Your answer

Official answer and solution

Official answer: 6
From: Official GATE 2025 answer key

Solution

Recognize that two-pass BFS on a tree always outputs the diameter (number of edges on the longest simple path) of the tree.

For any tree $T$ , running BFS from an arbitrary vertex $v$ to find a farthest vertex $u$ , and then running BFS from $u$ to find a farthest vertex $z$ , is the standard two-BFS algorithm that computes the diameter of $T$ (the maximum distance in edges between any two vertices in $T$ ).

In the given tree $T$ , the longest path goes from the bottom-left leaf (or either of the two top-left leaves at distance 2 from the left degree-4 hub) through the 5 internal nodes on the main backbone to the rightmost leaf, spanning $6$ edges.

Final answer

Common trap

Counting the number of vertices (7) on the longest path instead of the number of edges (6).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 2 (CS2)
Question: 59 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source