树的分治算法

Question

我正在尝试编写一种树形分治算法。对于分割步骤，我需要一种算法来通过删除一个节点将给定的无向图G=(V,E)（具有n个节点和m条边）划分为子树。所有子图都应该具有以下属性：它们不包含超过n/2个节点（树应尽可能平均地分裂）。首先，我尝试递归地从树中删除所有叶子节点以找到最后剩下的节点，然后我尝试查找G中最长的路径并删除其中间节点。下面给出的图表明这两种方法都不起作用：

在上述情况下，是否有一些有效的算法可以实现我的需求（返回节点H）？

- Listing

---

我不明白，如果你移除 H，你会得到 9 个子树！ - Shahbaz

是的，对于这里表述不清我感到抱歉。我可以获取许多子树，但我不希望其中一个超过图形的一半，以确保我仅进行对数计算的分割步骤。 - Listing

还有一件事，你如何将“树应该尽可能平均地分裂”转化为可计算的值？ - Shahbaz

即使算法在每一步并非完全将树减半，仍然被认为是O(logN)。那么完全将其减半的重要性是什么？ - Jonathan Schneider

我想最多将树分割logN次，如果您总是将一个叶子作为分割步骤移除，则必须分割N次，这将减慢算法的速度。 - Listing

Answer 1

我认为您可以使用以下算法来完成此操作：

从根开始（如果树没有根，请选择任何节点）。 在每个步骤中，尝试进入具有最大子树的子节点（下面的节点数量最多）。 如果这样做会使上方的节点数增加到大于n/2，则停止；否则继续与该子节点一起进行。

如果树相对平衡且我们对每个节点的子树大小进行了预计算，则此算法应为O(log n)。如果其中一个条件不适用，则为O(n)。

- svick

---

什么是无向树中的根节点？另外，我如何知道子树有多大？ - Listing

就像我说的，如果没有给定根节点，你可以选择任何一个节点作为根。要知道子树的大小，你必须计算它，最好缓存结果，这样你就不必多次计数。 - svick

这绝对不止是O(n)，想象一下你从示例中的节点A开始。你首先要扫描整个子树，然后移动到B，再到C，以此类推，每次都要扫描整个子树，这会导致更高的时间复杂度。 - Listing

你不需要扫描整个子树，只需要知道计数。而且你可以在第一次需要一个计数时以O(n)的时间计算出所有计数。 - svick

现在我明白了，我接受了这个方案，因为它看起来更容易实现。 - Listing

Answer 2

一个精确的算法如下：

从叶子节点开始创建不相交的图（实际上都是K1），在每一步中找到这些叶子节点的父节点，并将它们合并成新的树。在每一步中，如果节点x有r个已知的孩子，并且节点的度为j，使得j=r+1，则该情况下不在x的子节点中的节点就是当前节点的父节点，我们称节点x为“好的”（nice）。否则，存在一些孩子，其相关的根子树尚未构建，此时我们称节点x为“坏的”（bad）。

所以，在每一步中，将“好的”节点连接到它们的相关父节点，很明显每一步需要花费“好的”父节点的度数之和，同时在每一步中至少有一个“好的”节点（因为你从叶子节点开始），所以该算法的时间复杂度为O(n)，并且可以完全完成。但是要找到应该删除的节点，则需要在每一步中检查不相交列表（子树列表）的大小，这可以在构造时以O(1)的时间完成。而如果列表的大小等于或大于n/2，则选择相关的“好的”节点。（实际上是在最小的列表中找到满足此条件的“好的”节点）。

显然，如果可能以良好的方式划分树（每个部分最多有n/2个节点），则可以通过该算法完成，但如果不可能（实际上无法将其划分为两个或更多大小小于n/2的部分），则该算法为其提供了良好的近似值。同时，正如你所看到的，输入树中没有任何假设。

注：我不知道是否可能存在一棵树，使得删除一个节点后无法将其划分为大小小于n/2的某些部分。

- Saeed Amiri

Answer 3

这里是我使用和测试过的一个方法。

从找到树的根节点开始，可以通过创建一个包含所有节点的集合并创建另一个数组NeighboursNumber[]，其中存储每个节点的邻居数目对应的索引来完成。然后遍历这个集合并消除叶子节点（即具有NeighboursNumber[i] == 1的节点），确保将这些节点添加到另一个集合RemovedSet中（以避免更新问题），然后在每次迭代之后遍历RemovedSet并减少每个集合元素的所有邻居的NeighboursNumber[]条目。

最后你将得到根节点。（确保实现剩下2个只有一个邻居的节点的情况）。

找到根节点后，我们继续寻找每个子树的大小。这里的技巧是在查找根节点时进行此操作：在第一次迭代中消除叶子节点之前，首先创建一个数组SubTreeSize[]，每次我们从集合中移除一个节点时，我们将该节点的值+1添加到其父节点的值中：SubTreeSize[parent] = SubTreeSize[parent] + SubTreeSize[removedNode] + 1；这样，当我们找到根节点时，我们也知道每个子树的大小。

然后我们从根节点开始，检查每个邻居是否满足其子树的大小+1> nodes/2，如果是，则选择该节点并重新开始。当所有子节点的大小<= nodes/2时，跳出循环并输出该节点。

这种方法在拥有10^5个节点的树上仅需不到一秒钟。

- Domarius

Answer 4

这个问题似乎类似于寻找一个物体的质心。

假设每个节点都是等质量（重量）的点质量，并且其位置由图中给定。您的算法尝试查找质心，即在所有连接的子树中具有类似节点累积权重的节点。

您可以计算每个节点上所有子树的累积权重。然后选择最平衡的那个，即没有子树的权重超过n / 2。这可能是一项动态规划任务。

- moooeeeep