寻找树的中心

Question

我有一个问题，这是我的计划的一部分。

对于树 T=(V,E)，我们需要找到树中的节点 v，使从 v 到任何其他节点的最长路径的长度最小化。

那么我们如何找到树的中心呢？中心只能有一个还是多个？

如果有人能给我一个好的算法，这样我就可以了解如何适应我的程序。

Answer 1

有两种方法可以做到这一点（两者同时运行）：

• 使用 BFS（我将在此处描述）
• 使用 FIFO 队列。

---

选择树上的任意顶点 v1。从此顶点运行 BFS。您要处理的最后一个顶点 (v2) 将是距 v1 最远的顶点。现在运行另一个 BFS，这次从顶点 v2 开始，并获取最后一个顶点 v3。

从 v2 到 v3 的路径是树的直径，您的中心位于树上的某个位置。更准确地说，它位于它的中间。如果路径有 2n + 1 个点，则只有 1 个中心（在位置 n + 1）。如果路径有 2n 个点，则在位置 n 和 n + 1 处将有两个中心。

您仅使用 2 个 BFS 调用，其运行时间为 2 * O(V) 。

Answer 2

考虑一棵有两个节点的树？哪个是中心？任何一个就足够了，因此一棵树可以有多个中心。

现在，想想成为中心意味着什么。如果所有分支的高度相同，则中心为根（所有路径都经过根）。如果分支具有不同的高度，则中心必须是根或具有最大高度的分支，否则最大路径大于最高分支的高度，并且根将是更好的选择。现在，我们需要从最高的树枝往下看多远？最高的分支（从根开始）和下一个最高的分支之间的高度差的一半（如果差异最多为 1，则根就足够了）。为什么，因为当我们将最高的分支向下一层时，我们会将到下一个最高分支的最深节点的路径延长一级，并将到当前分支中最深节点的距离减少一级。最终，当您穿过深度差的一半时，它们将相等。现在，当我们沿着最高的分支走下去时，我们只需在每一层选择最高的分支即可。如果多个高度相同，我们只需任意选择一个即可。

本质上，您要做的就是找到图中的最长路径，即树的最高分支和下一个最高分支之间的距离，然后找到该分支上的中间节点。因为可能有多条路径与最长路径的长度相同，并且最长路径的长度可能是偶数，所以有多个可能的中心。

Answer 3

我不会为您做这个作业问题，而是会通过思考过程来问您以获得答案...

1) 您会如何处理图 abc（三个顶点，两条边，并且肯定是非循环的）？想象一下，您必须在某些顶点上放置一些标签，您知道您将获得“中心”顶点上最长路径的最小值。 （b，最终标签为“1”）但是一步完成这一任务需要心灵力量。所以问问自己 b 离什么远 1 步。如果到 b 的最长路径是 1，并且我们刚刚沿着该路径向后退了一步，那么到目前为止我们的路径长度是多少？ （最长路径 = 1，-1 表示后退一步。啊哈：0）。所以这一定是叶子的标签。

2）作为算法的第一步，这意味着什么？将叶子标记为“0”，将其上游标记为“1”，将其上游标记为“2”，依此类推。从树叶处行进，边走边计算距离...

3) 嗯...我们在图 abcd 方面遇到了问题。 （从现在开始，标记的顶点将被其标签替换。）将叶子标记为“0”给出 0-bc-0...我们不能得到两个中心...哎呀，我们在更简单的情况下做什么条件0-b-1？我们想用“1”和“2”来标记 b...以相反的顺序处理...

在 0-b-1 中，如果我们将 b 左边的路径延伸 1，我们会得到长度为 1 的路径如果我们从 b 的右侧延伸路径，我们会得到 2。我们想要跟踪“从 v 到任何其他节点的最长路径的长度”，因此我们想要跟踪到 b 的最长路径。这意味着我们用“2”标记 b。

 0-b-1  ->  0-2-1 

在 0-bc-0 中，计算机实际上并没有同时更新 b 和 c。它更新其中之一，给出 0-1-c-0 或 0-b-1-0，下一次更新给出 0-1-2-0 或 0-2-1-0。 b 和 c 都是该图的“中心”，因为它们都满足“树中的节点 v 最小化从 v 到任何其他节点的最长路径的长度”的需求。 （长度为 2。）

这导致了另一个观察结果：计算的结果不是标记图，而是找到我们标记的最后一个顶点和/或最终具有最大标签的顶点。 （我们可能找不到排序标签的好方法，所以我们最终需要在最后找到最大值。或者也许我们会。谁知道呢。）

4）所以现在我们有这样的东西：图表的两份副本——带标签的副本和燃尽副本。第一个将存储标签，并且其中将包含最终答案。当我们从中删除未标记的顶点（以查找新的可标记顶点）时，燃尽副本将变得越来越小。 （还有其他方法可以组织这个，以便只使用图表的一个副本。当您最终理解这个答案时，您应该找到一种方法来减少这种浪费。）大纲：

    label = 0
    while the burndown graph is nonempty
        collect all the leaves in the burndown-graph into the set X
        for each leaf in the set X
            if the leaf does not have a label
                set the leaf's label (to the current value of label)
            delete the leaf from the burn-down graph (these leafs are two copies of the same leaf in the input graph)
        label = label+1
    find the vertex with the largest label and return it

5）如果您真的观看了这个运行，你会发现有几个走捷径的机会。包括用更快的方法来识别答案，从而替换大纲最后一行的搜索。

现在介绍算法问题的一般策略技巧：
* 手工做一些小例子。如果你不明白如何处理小案件，你就无法直接跳到告诉计算机如何处理大案件。
* 如果上述任何步骤看起来没有动力或完全不透明，那么您将需要更加努力地学习才能在计算机科学方面取得好成绩。可能计算机科学不适合你......