algorithm - 正确性证明 : Algorithm for diameter of a tree in graph theory

Question

为了找到树的直径，我可以从树中取出任何节点，执行 BFS 以找到距离它最远的节点，然后对该节点执行 BFS。与第二个 BFS 的最大距离将产生直径。

不过我不确定如何证明这一点？我试过对节点数使用归纳法，但情况太多了。

任何想法将不胜感激......

Answer 1

我们将第一个 BFS 找到的端点称为 x。关键的一步是证明在第一步中找到的 x 总是“有效”——也就是说，它总是在某个最长路径的一端。 (请注意，通常可以有不止一条等长路径。)如果我们能够建立这一点，那么很容易看出以 x 为根的 BFS 将找到距离 x 尽可能远的某个节点，因此这必须是一个整体最长的路径。

提示:假设(相反)两个顶点 u 和 v 之间有一条较长的路径，其中两个顶点都不是 x。

观察到，在 u 和 v 之间的唯一路径上，必须有一些最高(最接近根)的顶点 h。有两种可能性:要么 h 在从 BFS 的根到 x 的路径上，要么不在。通过证明在这两种情况下，通过用到 x 的路径替换其中的某些路径段，u-v 路径至少可以变得一样长，从而证明矛盾。

[编辑] 实际上，毕竟可能没有必要分别对待这两种情况。但我经常发现将一个配置分解为多个(甚至多个)案例并分别对待每个案例更容易。这里，h 在从 BFS 根到 x 的路径上的情况更容易处理，并且为其他情况提供了线索。

[编辑 2] 稍后再谈这个问题，现在在我看来，需要考虑的两种情况是 (i) u-v 路径与从根到 x 的路径相交(在一些顶点y，不一定在u-v路径的最高点h)； (ii) 它没有。我们仍然需要 h 来证明每个案例。