algorithm - 树的分而治之算法

Question

我正在尝试为树编写分而治之的算法。对于除法步骤，我需要一种算法，通过删除一个节点将给定的无向图 G=(V,E) 与 n 个节点和 m 个边分割成子树。所有子图都应具有不包含超过n/2个节点的属性（树应尽可能相等地拆分）。首先我尝试递归地从树中删除所有叶子以找到最后一个剩余节点，然后我尝试找到 G 中最长的路径并删除它的中间节点。下图显示这两种方法都不起作用：

是否有一些工作算法可以满足我的要求（在上述情况下返回节点 H）。

Answer 1

我认为你可以用这样的算法来做到这一点：

从根开始（如果树没有根，选择任何节点）。
在每一步中，尝试下降到具有最大子树的子节点（它“下方”的节点数最大）。
如果这样做会使“上方”的节点数大于 n/2，则停止，否则继续该子节点。

如果树是合理平衡的并且我们为每个节点预先计算了子树的大小，则该算法应该是 O(log n)。如果其中一个条件不适用，则为 O(n)。

Answer 2

一种精确的算法是这样的，

从叶子开始并创建不相交的图（实际上都是K1），在每一步中找到这个叶子的父节点，并将它们合并到新树中，在每一步如果节点x已经r知道子节点并且节点的度数是j这样的j = r+1，简单地说不在子节点中的节点x是当前节点的父节点，在这种情况下我们说节点x是nice，否则，有一些子节点没有构造它们的相关根子树，在这种情况下我们说节点x是bad。

所以在每一步中将nice节点连接到它们相关的父节点，很明显每一步sum of {degree of parent nice nodes}在每一步中你至少有一个好的节点（因为你从叶子开始），所以算法是 O(n)，它会完成完全，但是为了找到应该删除的节点，实际上在每个步骤中都需要检查双联列表（子树列表）的大小，这可以在 O(1) 中完成，如果列表的大小相等或大于n/2，然后选择相关的nice节点。（实际上是在满足这个条件的最小列表中找到好的节点）。

显而易见的事情是，如果可以以良好的方式划分树（每个部分最多有 n/2 个节点），您可以通过此算法完成，但如果不是这样（实际上您不能将其划分为两个或更多部分尺寸小于 n/2）这为您提供了很好的近似值。同样如您所见，输入树中没有假设。

注意：我不知道是否有可能拥有一棵树，从而无法通过删除一个节点将其划分为小于 n/2 的某些部分。

Answer 3

这个问题似乎类似于寻找物体的质心。假设您的每个节点都是等质量（重量）的点质量，其位置由图中的位置给出。您的算法试图找到质心，即在所有连接的子树中具有相似的节点累积权重的节点。

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

Answer 4

这是我使用和测试的一种方法。

从找到树的根开始，您可以通过创建一个包含其中所有节点的集合，然后创建另一个数组 NeighboursNumber[]，其中每个节点的邻居数存储相应的索引。然后遍历集合并消除叶子（节点 i 具有 NeighboursNumber[i] == 1 ），确保将这些节点添加到另一个集合 RemovedSet （以避免更新问题），然后在每次迭代后通过 RemovedSet 并减少集合中每个元素的所有邻居的 NeighboursNumber[] 条目。最后，您将拥有根节点。（确保您实现的情况是剩下 2 个节点和 1 个邻居）。在找到根之后，我们继续找到每个子树的大小。这里的技巧是在寻找根的同时执行此操作：在第一次迭代中消除叶子之前，首先创建一个数组 SubTreeSize[] ，每次我们从集合中删除一个节点时，我们将该节点的值 + 1 添加到父节点的值：SubTreeSize[parent] = SubTreeSize[parent] + SubTreeSize[removedNode] + 1 ; 这样，当我们找到根时，我们也有每个子树的大小。然后我们从根开始检查每个邻居的子树大小 + 1 > nodes / 2 ，如果是，那么我们选择那个节点并重新开始。当所有子节点大小为 <= nodes / 2 时，打破循环并输出该节点。然后我们从根开始检查每个邻居的子树大小 + 1 > nodes / 2 ，如果是，那么我们选择那个节点并重新开始。当所有子节点大小为 <= nodes / 2 时，打破循环并输出该节点。然后我们从根开始检查每个邻居的子树大小 + 1 > nodes / 2 ，如果是，那么我们选择那个节点并重新开始。当所有子节点大小为 <= nodes / 2 时，打破循环并输出该节点。

对于具有 10^5 个节点的树，这种方法花费了不到一秒的时间。