algorithm - 计算任何一种树的直径？

Question

如何设计一种算法，以线性时间计算（图论）无向、所有边具有权重 1 树的直径？树的直径由两个顶点之间的最长路径的长度给出。

知道如何解决这个问题吗？

Answer 1

让 v1 是树中的任何顶点。

从 v1 开始进行深度优先搜索，得到所有其他顶点到 v1 的距离，选择 v2 作为距离最大的顶点。

从 v2 开始进行深度优先搜索，得到所有其他顶点到 v2 的距离，选择 v3 作为距离最大的顶点。

D(v2, v3) 是树的直径。复杂度为 O(|V|)，因为 DFS 对于树是线性的。