The diameter of a tree T = ( V , E ) is given by (where ?( u , v ) is the number
ID: 3543682 • Letter: T
Question
The diameter of a tree T = (V,E) is given by
(where ?(u,v) is the number of edges on the path from u to v). Describe an efficient algorithm to compute the diameter of a tree, and show the correctness and analyze the running time of your algorithm.
The diameter of a tree T = (V,E) is given by max toi(u,v) (where ?(u,v) is the number of edges on the path from u to v). Describe an efficient algorithm to compute the diameter of a tree, and show the correctness and analyze the running time of your algorithm.Explanation / Answer
Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u
remembering the node v discovered last. d(u; v) is the diameter of the tree.
Correctness: Let a and b be any two nodes such that d(a; b) is the diameter of the tree. There is a unique
path from a to b. Let t be the ?rst node on that path discovered by BFS.
1If the paths p1 from s to u and p2 from a to b do not share edges, then the path from t to u includes s so
d(t; u) d(s; u)
d(t; u) d(s; a)
d(t; u) d(t; a)
d(b; u) d(b; a)
Since d(a; b) d(u; b), d(a; b) = d(u; b).
If the paths p1 and p2 do share edges, then t is on p1. Since u was the last node found by BFS, d(t; u)
d(t; a). Since p2 is the longest path, d(t; a) d(t; u). Thus d(t; a) = d(t; u) and d(u; b) = d(a; b).
d(a; b) d(u; v) and d(u; v) d(u; b) so all three are equal. Thus d(u; v) is the diameter of the tree