Cormen Edition 3 Exercise 22.2 Question 8 (Page No. 539)

Question

The diameter of a tree $T= (V, E)$ is defined as $max_{u,v\ \epsilon\ V}\ \delta(u,v)$, that is, the largest of all shortest-path distances in the tree. Give an efficient algorithm to compute the diameter of a tree, and analyze the running time of your algorithm.

Comments

U can do bfs and compute the distance of the leaf which is at a maximum distance from the root node

Now consider that leaf node as root node and do breadth first search to find a leaf node which is at a maximum distance from the this leaf node the distance will be the answer

so time complexity of this is o(v+e) and space complexity is also o(v) for maintaining distance of each leaf node

Answer 1

we can use Floyd-Warshall Algortihm to calculate the shortest distance between every pair of vertices and then find the maximum.

so, the time complexity would be O(n^3)

Space Complexity is O(n^2).