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 是树中的任意节点。...