Linear time algorithm for longest path in tree

Question

I have been given a question on an assignment that has got me stumped. I may just be thinking too hard about it... The question follows.

Give a linear time algorithm to determine the longest unweighed path in an acyclic undirected graph (that is, a tree).

My first intention is to go with a DFS. But it seems like a DFS would only give me the longest path from the node I start at to another vertex; however, the problem asks for the longest path in the tree... not the longest path from the node I start at. Could someone set me straight?

Thanks.

Answer 1

One such method is to pick any node, A, and in linear time compute distances to all other nodes. Suppose B is most distant from A. In step 2, find the node most distant from B.

Let d(P,Q) denote distance from P to Q. Note that if E is the lowest common ancestor of A, B, C, then d(A,B) = d(A,E)+d(E,B) and also note that d(E,B) ≥ d(E,C).

Edit 1: The algorithm or method – find B most distant from any A; find C most distant from B; claim that d(B,C) is maximal over all vertex pairs in the graph – seems to be sound, but the above does not prove it.

On one hand, it need not be that d(E,B) ≥ d(E,C), and on another, that alone would not be quite enough to establish d(B,C) ≥ d(F,G) where F, G are any nodes in the tree. ...