algorithm - 树中最长路径的线性时间算法

Question

有人向我提出了一个让我难过的作业问题。我可能只是想得太认真了……问题如下。

给出一个线性时间算法来确定无环无向图(即树)中最长的未加权路径。

我的第一个意图是使用 DFS。但似乎 DFS 只会给我从我开始的节点到另一个顶点的最长路径；但是，问题要求树中最长的路径……而不是从我开始的节点开始的最长路径。有人能帮我弄清楚吗？

谢谢。

Answer 1

其中一种方法是选择任何节点 A，并在线性时间内计算到所有其他节点的距离。假设B离A最远。在第2步中，找到离B最远的节点。

令 d(P,Q) 表示从 P 到 Q 的距离。请注意，如果 E 是 A、B、C 的最低共同祖先，则 d(A,B) = d(A,E)+d( E,B) 同时注意 d(E,B) ≥ d(E,C)。

编辑 1: 算法或方法 – 找到距任何 A 最远的 B；找到距离 B 最远的 C；声称 d(B,C) 在图中的所有顶点对上都是最大的 - 似乎是合理的，但上面并没有证明这一点。

一方面，它不一定是 d(E,B) ≥ d(E,C)，另一方面，仅凭这一点还不足以建立 d(B,C) ≥ d(F, G) 其中 F、G 是树中的任意节点。 ...