GATE CS 2025 (Afternoon) — Question 59

AlgorithmsGraph Traversals (BFS, DFS) & Single-Source Shortest PathsNAT2 marksMedium

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)
Question image
Practise the full 2025-AN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAPractise this subject in the exam simulatorTimed, GATE-style tests with analytics that find your weak topics.
Practise more on Graph Traversals (BFS, DFS) & Single-Source Shortest PathsTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group