Linear time algorithm for the longest path in a tree

Question

I was asked a question about a task that puzzled me. I can just think too much about it ... Question follows.

Give a linear time algorithm to determine the longest unpacked path in an acyclic undirected graph (i.e., in a tree).

My first intention is to go with DFS. But it looks like DFS will provide me with the longest path from node, starting at another vertex; however, the problem sets the longest path in the tree ... not the longest path from node I start from. Can anyone put me right in front?

Thanks.

Answer 1

One such method is to select any node, A, and linear time calculations for all other nodes. Assume B is farthest from A. In step 2, find the node farthest from B.

Let d (P, Q) denote the distance from P to Q. Note that if E is the smallest 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: Algorithm or method - find B farthest from any A; find C farthest from B; argue that d (B, C) is maximal for all vertex pairs in the graph - it seems to sound, but it does not prove above.

On the one hand, it is not necessary that d (E, B) ≥ d (E, C), and on the other hand, this was not enough to establish d (B, C) ≥ d (F, G), where F, G - any nodes in the tree ....