algorithm - 验证无向树中最长路径的不同方法

Question

我正在尝试这个问题 -在未加权的无向树中寻找最长路径。

方法一

Perform BFS from any node(say X) to the farthest possible node(say Y).
*   Then, perform BFS again from Y to its farthest node(say Z).
*   Y-Z is the required length.
*   For keeping track of length we can either keep a flag in the queue
*   or keep a predecessor array which can be updated for every node that we insert
*   in the queue.

简短、直观的解释——我们开始的节点 X 将始终尝试到达最长路径(比如 YZ)的一部分的节点。因此，穿过最长的路径(比如在节点 N)。从那里开始，它将有两个选择——要么在最长路径的一侧(NZ)走，要么在另一侧(NY)走。这将需要 NY 和 YZ 中较长的一个。所以，我们最终会到达最长路径的一端(节点 Y)。现在，如果 X 采取了与最长路径 (YZ) 重叠的一条 (max(NY,NZ)) 以外的路径，这将概括地暗示存在比最长路径 (YZ) 更长的路径。

反证法-

案例 1-让我们假设是否有一些路径 XT 不与 YZ 重叠并且比 XN+max(NY,NZ) 长。假设 S 是 N 和 T 的最低公共(public)祖先。现在，设 Length(UV) 是一个函数，表示两个节点 u 和 v 之间的路径长度。

We know, Length(XT) = Length(XS) + Length(ST)                 ..... 1
         Length(XY) = Length(XS) + Length(SN) + Length(NY)    ..... 2     
         Length(XZ) = Length(XS) + Length(SN) + Length(NZ)    ..... 3

不失一般性，让我们假设，Length(NY)>Length(NZ) ... 4现在，我们声称 Length(XT) > Length(XY)。因此，使用 1,2 和 4， 我们得到，Length(ST) > Length(SN) + Length(NY)。 但是，在那种情况下，在最长路径 YZ 中，如果我们用 NT 替换 NY，即 NS+ST，我们将得到比 YZ 更长的路径。那么YZ就不会保持最长的路径。因此，矛盾!

因此证明了 XN + max(NY,NZ) 是从 X 开始并将带我们到 Y 的最长路径，Y 被证明是绝对最长路径的一端。

类似地，我们可以证明情况 2 - 当 XT 与 YZ 有部分重叠时。它留给读者作为练习。

方法 2(尚待验证是否正确)

我的解决方案以及 akul 建议的更正( http://codeforces.com/blog/entry/2845#comment-200512 )

(我可能很久以前读过这个或类似的东西，但我无法关联/记忆)-

*   START -
*   Store all the nodes with their degrees.
*   1. Make a list of nodes of the Tree storing the "Degree" of each node along with the neighbors of the node. 
*
*   2.Initialize length=0;
*
*   3. While there are edges present in the tree, perform the following
*      a. remove the edges connecting all the nodes having degree 1. 
*
*      b.   if(number of edges removed >=2 ) length+=2;
*           else length+=1
*
*      c. update degree of node and its neighbors and the edge information
*
*   return length
*   END.

所以，在这里，我基本上在做的是沿着最长的路径逐渐变细，从所有边界(1 级)节点开始，因为最长的路径将是是连接两个 1 度节点(最远的节点)的节点。

我的问题 - 这种方法(方法 2)有效吗？

Answer 1

我同意@j_random_hacker 的观点，该方法是有效的，并且可以通过矛盾来证明:

证明两端节点的度数一定为1

• 假设有一个端节点A，度数为N，其中N>1
• 注意路径必须包含进入A的N条边之一
• 请注意，通过其他边之一退出 A 会延长路径
• 因此A不能是端节点

证明度数为1的节点(两端节点除外)不能成为路径的一部分

• 假设有一个度为1的节点B是路径的一部分，但不是结束节点
• 注意路径必须使用唯一的边进入B
• 注意没有剩余边可以退出B
• 因此 B 不能成为路径的一部分

但是，我会以稍微不同的方式表达该算法。第一次阅读步骤 3b 时，我对需要将长度递增 1 的 else 子句感到困惑。经过进一步审查，我终于明白了 else仅在算法结束时才需要子句。通过步骤 3a 的最后一次传递将留下一个具有一个或两个剩余节点的图。

如果最后还有两个节点，则该图由两个度数为 1 的节点和一条边组成。通过该图的最长路径的长度为 1。因此这是一种特殊情况，其中删除两个端节点只会删除一条边。因此，我将重写算法，如下所示，以明确特殊情况只发生在最后。

START
1. Make a list of nodes of the Tree storing the "Degree" of each node 
   along with a list of neighbors of the node. 

2. Initialize length=0

3. While the number of remaining nodes > 2
     a. remove all nodes having degree 1, and remove the corresponding edges  
     b. length+=2
     c. update the degree and the neighbor list of any remaining nodes 

4. if ( number of remaining nodes == 2 )
     length+=1

return length 
END