请提供一些算法来寻找树中距离其最远节点距离最小的节点。

Question

请提供一些算法，以找到树中距离其最远节点最短的节点。这不是一个图形，也没有权重。

- Sandeep

---

你需要重新表达你的问题。 - Layke

他的意思不太清楚。他基本上是在寻找图中最“中心”的顶点（其最远节点的距离是所有节点中最小的）。 - Peter Alexander

关于添加的“不是图表”：树是图表的一种特殊情况，因此即使效率不是最高的，图算法也应该适用于您的树形结构。 - Thomas Padron-McCarthy

只是一个通用树，还是二叉树，或者其他什么树？ - kennytm

你需要重新理解"图"这个术语。一棵树是一种图。 - Svante

树的问题（即使是非加权树）在于兄弟节点之间没有明确定义的距离。但是，将其转换为等连通图，则距离肯定为2。 - MSalters

Answer 1

选择树T中的任意节点v。 以v为根运行BFS。 BFS输出从v到T中所有其他节点的距离。

现在选择一个距离v最远的节点u。 再次以u为根运行BFS。 在新的距离输出中，找到一个距离u最远的节点w。

考虑u和w之间的路径。 这是树T中最长的路径。 路径中间的节点是T的中心。

请注意，树中可能存在两个中心。如果是这样，它们是相邻的。

性能：O(n)，其中n是T的节点数。

证明

声明：距离某个节点v最远的叶子节点(u)位于最长路径上。

如果我们证明了这一点，则该算法是正确的，因为它首先找到u，然后使用DFS找到这条路径本身，因为它是最长路径的一端。

证明声明：让我们使用反证法。假设u---r是树中最长的路径；对于某个节点v，既不是v---u，也不是v---r是从v到达的最长路径。相反，最长的路径是v---k。我们有两种情况：

a）u---r和v--k有一个共同的节点o。然后v--o--u和v--o--r比u---o---k短。那么o---r比o---k短。那么u---o---r不是图中最长的路径，因为u---o---k更长。这与我们的假设相矛盾。

b) u---r 和 v--k 没有共同的节点。但由于图是连通的，因此在这些路径上分别存在节点 o1 和 o2，使得它们之间的路径 o1--o2 不包含这两条路径上的其他节点。与假设相矛盾的证明与点 a 相同，但用 o1--o2 替换了简单的 o（实际上，点 a 只是点 b 的一个特例，其中 o1=o2）。

这证明了该算法的正确性。

（这是Pavel Shved编写的证明，原作者可能有更简短的证明）。

- Slava

---

你能透露一下你找到最长路径的方法的一些原因吗？ - Svante

Answer 2

去掉叶子节点。如果剩下的节点数大于2，则重复此步骤。留下的节点（或2个节点）将是您要查找的节点。

为什么这样做有效：

该节点（或节点对）位于树中最长路径P的中间。它们到任何节点的最大距离最多为路径长度的一半（否则它不会是最长的路径）。P上的任何其他节点显然与P的更远端的距离比已找到的节点更远。不在P上的任何节点n都将其最远节点至少为（从n到P上最近节点的距离，称为c）+（从c到P的更远端的距离），因此比算法找到的节点（或节点对）更多。

- Rafał Dowgird

---

我不知道什么是根节点，因此也不知道叶节点是什么。 - Sandeep

一个叶子节点将会恰好有一条边。 - Chowlett

这将始终找到根节点（假设它具有多个边缘，否则它将找到根上方的最低分支）。 - jk.

据我所知，这些边是无向的，因此没有“根”。这总是能够找到图中最长路径的中间点。只有一条边的节点是叶子节点，因此它将在第一次迭代中被删除。 - Rafał Dowgird

Answer 3

你可以在稀疏图中使用约翰逊算法，但否则只需使用弗洛伊德-沃舍尔算法，因为它很容易实现。

基本上，你想要找到每个节点到其他每个节点的距离，然后轻松地搜索你想要的属性。

- Peter Alexander

---

这些算法对我来说是新的，而且看起来比Djikstra更容易编码。 - Chowlett

请注意，FW算法的时间复杂度为O(n^3)，这可能不是最理想的选择。 - dirkgently

对于这个应用程序来说，与重复的Djikstra算法相同。 - Chowlett

Answer 4

您可以依次在每个节点上使用Dijkstra算法（http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm），以查找该节点到每个其他节点的所有距离；扫描结果列表以获取到最远节点的距离。一旦您对每个节点进行了Dijkstra处理，另一个扫描将为您提供这些最大距离的最小值。

Dijkstra通常被认为具有运行时间O(v^2)，其中v是节点数；您将对每个节点运行它一次，这将使得时间复杂度在朴素实现中增加到O(v^3)。您可以通过存储先前节点的Dijkstra运行的结果并在后续运行中将其用作已知值来获得收益。

- Chowlett

---

Floyd-Warshall编码比Dijkstra简单得多，但是它们的复杂度相同。 - Peter Alexander

Answer 5

正如其他评论中所说： 树是一种图形——准确地说，是一个无向连通无环图——请参见"树"（图论）。

- Joris Timmermans

---

一棵树不能是无向的，对吧？ - Thomas Padron-McCarthy

一棵树有一个隐含的方向。每个节点到根节点（树而非森林）都有明确定义的距离，两个相连的节点到根的距离相差一。距离根节点更近的节点是父节点；距离更远的节点是子节点。因此，在树形图中，父子关系是以纯图形术语定义的。此外，树是无环图，因此父节点和其子节点之间没有其他边缘。因此，连接节点的父子关系充当边缘的方向。 - MSalters