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.
$\begingroup$
$\endgroup$
8
-
$\begingroup$ @uli, that problem talks about a rooted tree, this one doesn't. Sure, this problem can be solved like the other one by selecting an arbitrary root and looking for the two longest paths to a leaf, but that isn't immediately obvious IMHO. $\endgroup$– vonbrandMar 1, 2013 at 19:30
-
$\begingroup$ @uli that problem talks about a directed tree and each edge has its own length $\endgroup$– aditsuMar 1, 2013 at 19:33
-
$\begingroup$ @vonbrand the arbitrary root may not be on a longest path, so you'd have to try all vertices.. but then you can simply find one longest path, and I already mentioned this idea $\endgroup$– aditsuMar 1, 2013 at 19:40
-
1$\begingroup$ @aditsu „all edges have no length“ and „all edges have the same length“ is equivalent. Because I can give all edges the same arbitrary length $c$. Then all edges will be treated alike. $\endgroup$– uliMar 1, 2013 at 19:52
-
$\begingroup$ @aditsu Calling an acyclic graph a tree and then stating that it is unrooted confused me. Additionally mentioning „unrooted“ in the parentheses behind „undirected“ is confusing too. So you want to compute the diameter of an acyclic graph? $\endgroup$– uliMar 1, 2013 at 20:02
|
Show 3 more comments
2 Answers
$\begingroup$
$\endgroup$
1
I would use breath-first search and dynamic programming.
Let $A$ be a matrix where $A[i,j]$ is the distance between $v_i$ and $v_j$.
As we are in a tree, there are no loops and you can just counting the distances by taking the distances to the previous vertex and adding 1 to them.
Let $v_v$ a vertex that has already been visited. In our matrix we know the distances from the other vertices. Let $v_n$ be a new vertex, then the distances of the other vertices will be the ones for $v_v$ plus 1.
So in every step of the algorithm you will know all the distances between all the vertices that have already been visited.
Base case is that you have visited just one vertex and it has zero distance to itself.
You also need to save the length of the longest path found so far and the indices of the vertices of the longest path and check them every time that you visit a new node.
answered Mar 1, 2013 at 22:33
-
1$\begingroup$ That seems O(n^2), not more efficient than a DFS from each vertex $\endgroup$– aditsuMar 1, 2013 at 22:41
$\begingroup$
$\endgroup$
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.