Computer Sciences > GATE 2025 SET-2 > Graph Algorithms
Consider the following algorithm someAlgo that takes an undirected graph G as input.
The output of someAlgo (T) for the tree shown in the given figure is ______ (Answer in integer)
Correct : 6
This algorithm computes the diameter of the tree - the longest shortest path between any two vertices.
BFS from any vertex finds the farthest vertex u. BFS from u then finds the farthest vertex z. The distance between u and z is the diameter.
Finding the diameter of tree T:
The tree T in the figure is an unweighted tree. All edges have weight 1.
Starting BFS from any arbitrary vertex v, we find the farthest vertex u.
Then BFS from u finds the farthest vertex z.
The longest path (diameter) in tree T = 6 edges
∴ The output of someAlgo(T) = 6
Similar Questions
Let G(V,E) be an undirected and unweighted graph with 100 vertices. Let d(u,v) denote the number of edges in a shortest path between vertices u and v in V. Let...
Let G be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant a is added to the weight of every edge. Which ONE of the foll...
Let G(V, E) be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of...
Total Unique Visitors
Loading......