Longest path in undirected tree

Problem Detail: 

Given an undirected tree (with no specific root), how to find the longest path, i.e. 2 vertices that are the farthest apart from each other? There are no lengths associated with the edges (each edge has length 1 by default).
Obviously one idea is to check the path lengths between all pairs of vertices (e.g. by doing a DFS from each vertex), but there should be a more efficient solution. Please include a short proof in your answer.

Asked By : aditsu

Answered By : aditsu

I think one solution is to do a single DFS (from any node) to determine the longest path, in "divide and conquer" fashion. Apologies in advance for the clumsiness of the description - I'm not sure what's the proper notation for these things.

First, some background: at each step of the DFS we're exploring a subtree T, with the current vertex R considered to be the root of that subtree. All the neighbors of the root (excluding the "parent" in the DFS sense, which is not part of T) form subtrees T1, T2 ... Tk of T.
At each step, we determine both the longest path in T, let's call it p(T), and the longest root path in T (root path = path starting from R), let's call that rp(T).
To do that, we find the same for each subtree T1, T2 ... Tk, then
rp(T) = R--longest(rp(Ti)), i=1...k (I'm using "--" to symbolize joining the vertex R to the path), and
p(T) = longest(rp(T), longest(p(Ti)), rp(T)--2ndlongest(rp(Ti)))
Some explanation about the last term: it only appears if k>1 (at least 2 subtrees), and it joins the 2 longest root paths in the subtrees, through R.
If k=0, then both p(T) and rp(T) are the 0-length path R.

I think a rigorous proof is not necessary - it is quite obvious that for each subtree T, p(T) is either in one of its subtrees Ti, or starts from R going into a subtree (this is rp(T)), or passes through R, going into 2 subtrees. And all the path parts going into subtrees must be the longest root paths in those subtrees. All the cases are handled.

As far as I can tell, the complexity is O(n) since this is a tree.

Implementation note: for each vertex we can store the lengths of p(T) and rp(T), a flag indicating which of the 3 situations we're in for p(T), references to (up to) 2 neighbors that contain a piece of p(T), and the next neighbor vertex for rp(T). At the end, we can reconstruct the longest path from this information.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10181