CODEWITHSUNDEEP
algorithmgraph-algorithmpseudocode
winston smith
winston smith

Reputation: 121

Compute the diameter of any kind of tree?

How to design an algorithm that computes in linear time the diameter of a (graph theoretical) undirected, all-edges-have-weight-1 tree? The diameter of a tree is given by the length of the longest path between two vertices.

Any idea of how to aproach this problem?

Upvotes: 2

Views: 1935

Answers (1)

svinja
svinja

Reputation: 5566

Let v1 be any vertex in the tree.

Do a depth first search from v1 to get the distances of all other vertices from v1, choose v2 as the vertex with the highest distance.

Do a depth first search from v2 to get the distances of all other vertices from v2, choose v3 as the vertex with the highest distance.

D(v2, v3) is the tree diameter. The complexity is O(|V|), as DFS is linear for a tree.

Upvotes: 7

Related Questions