树的分而治之算法
我正在尝试写一个divide &树的征服算法。对于划分步骤，我需要一种算法，通过删除节点，将具有 n 个节点和 m 个边的给定无向图 G=(V,E) 划分为子树。所有子图都应具有不包含超过 n/2 个节点的属性（树应尽可能平等地分割）。首先，我尝试递归地从树中删除所有叶子以找到最后一个剩余节点，然后我尝试找到 G 中的最长路径并删除其中的中间节点。下面给定的图表显示这两种方法都不起作用：
是否有一些工作算法可以完成我想要的操作（返回上例中的节点 H）。
I am trying to write a divide & conquer algorithm for trees. For the divide step I need an algorithm that partitions a given undirected Graph G=(V,E) with n nodes and m edges into sub-trees by removing a node. All subgraphs should have the property that they don't contain more than n/2 nodes (the tree should be split as equal as possible). First I tried to recursively remove all leaves from the tree to find the last remaining node, then I tried to find the longest path in G and remove the middle node of it. The given graph below shows that both approaches don't work:
Is there some working algorithm that does what I want (returns the node H in the above case).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
我认为你可以使用这样的算法来做到这一点：
从根开始（如果树没有根，则选择任何节点）。
在每一步中，尝试下降到具有最大子树的子节点（它“下面”的节点数量是最大的）。
如果这样做会使“上面”的节点数大于 n/2，则停止，否则继续处理该子节点。
如果树是合理平衡的并且我们为每个节点预先计算了子树的大小，则该算法应该是 O(log n)。如果其中一个条件不适用，则复杂度为 O(n)。
I think you could do it with an algorithm like this:
Start in the root (if the tree isn't rooted, pick any node).
In each step, try to descend into the child node that has the largest subtree (the number of nodes “below” it is the biggest).
If doing that would make the number of nodes “above” bigger than n/2, stop, otherwise continue with that child.
This algorithm should be O(log n) if the tree is reasonably balanced and we have sizes of subtrees precomputed for each node. If one of those conditions doesn't apply, it would be O(n).
一个确切的算法是这样的，
从叶子开始，创建不相交的图（实际上都是K1），在每一步中找到该叶子的父节点，并将它们合并到新树中，在每一步中如果节点
x 有r已知子节点，节点度为j，使得j = r+1，只是一个不在子节点中的节点x是当前节点的父节点如果我们说节点x是nice，否则，有一些子节点没有构建它们的相关根子树，在这种情况下我们说节点x< /code> 是坏。因此，在每个步骤中，将
nice节点连接到其相关的父节点，很明显，每个步骤都需要{parent Nice 节点的度数}之和，而且在每个步骤中，您至少有一个好的节点（因为你从叶子开始），所以算法是 O(n)，并且它会完全完成，但是为了找到应该删除的节点，实际上在每个步骤中都需要检查双交列表的大小（子树列表），这可以在构造时复杂度为 O(1)，并且如果列表的大小等于或大于 n/2，则选择相关的好节点。 （实际上是在最小列表中找到满足这个条件的好节点）。显然，如果可以很好地划分树（每个部分最多有 n/2 个节点），则可以通过此算法完成，但如果不是这样（事实上，您不能将其划分为两个或多个部分）尺寸小于 n/2），这为您提供了很好的近似值。正如您所看到的，输入树中没有假设。
注意：我不知道是否有可能有一棵树，无法通过删除一个节点将其划分为大小小于 n/2 的某些部分。
One exact algorithm is as this,
Start from leafs and create disjoint graphs (in fact all are K1), in each step find the parent of this leafs, and merge them into new tree, in each step if node
xhasrknown child and degree of node isjsuch thatj = r+1, simply a node which is not in child node ofxis parent of current node in this case we say nodexisnice, else, there are some child such that related rooted subtree of them not constructed, in this case we say the nodexisbad.So in each step connect
nicenodes to their related parent, and it's obvious each step takessum of {degree of parent nice nodes}also in each step you have at least one nice node (cause you start from leaf), So the algorithm is O(n), and it will be done completely, but for finding node which should be removed, In fact in each step is required to check size of a dijoint list (subtree lists), this can be done in O(1) in construction, Also if the size of list is equal or bigger than n/2, then select related nice node. (in fact find the nice node in minimum list which satisfies this condition).Obvious thing is that if is possible to divide tree in good way (each part has at most n/2 node) you can done it by this algorithm, but if is not so ( in fact you cant divide it in two or more part of size smaller than n/2) this gives you good approximation for it. Also as you can see there is no assumption in input tree.
note: I don't know is possible to have a tree such that it's impossible to partition it into some parts of size smaller than n/2 by removing one node.
这个问题看起来类似于寻找物体的质心。
假设每个节点都是质量（重量）相等的点质量，其位置由图中的位置给出。您的算法尝试找到质心，即在所有连接的子树中具有相似的节点累积权重的节点。
您可以计算每个节点的所有子树上的累积权重。然后选择最平衡的一棵，没有子树的权重超过
n/2。这可能是某些动态规划的任务。This problem seems similar to finding the center of mass of an object.
Assume each of your nodes is a point mass of equal mass (weight) and its position is given by the position in the graph. Your algorithm tries to find the center of mass, i.e. the node that has a similar accumulated weight of nodes in all connected sub-trees.
You may compute the accumulated weights on all sub-trees for each node. Then choose the one that is most balanced, s.t. no sub-tree weighs more than
n/2. Probably this is a task for some dynamic programming.这是我使用和测试的一种方法。
首先找到树的根，您可以通过创建一个包含所有节点的集合，然后创建另一个数组 NeighboursNumber[] 来完成此操作，其中每个节点的邻居数量存储相应的索引。
然后迭代该集合并消除叶子（具有 NeighboursNumber[i] == 1 的节点 i ），确保将这些节点添加到另一个集合RemovedSet（以避免更新问题），然后在每次迭代后遍历RemovedSet并减少集合中每个元素的所有邻居的 NeighboursNumber[] 条目。
最后你将得到根节点。 （确保您实现的情况是剩下 2 个节点和 1 个邻居）。
找到根后，我们继续计算每个子树的大小。这里的技巧是在寻找根的同时执行此操作：在第一次迭代中消除叶子之前，首先创建一个数组 SubTreeSize[] ，每次从集合中删除一个节点时，我们都会添加该节点的值 + 1 到父节点的值： SubTreeSize[parent] = SubTreeSize[parent] + SubTreeSize[removedNode] + 1 ；
这样，当我们找到根时，我们也就知道了每个子树的大小。
然后我们从根开始并检查每个邻居，其子树的大小 + 1 > >节点/ 2 ，如果是，那么我们选择该节点并重新开始。当所有子节点大小都 <= 节点 / 2 时，中断循环并输出该节点。
对于具有 10^5 个节点的树，此方法花费的时间不到一秒。
Here is a method that I used and tested.
Begin by finding the root of your tree, you can do this by creating a set with all the nodes in them and then making another array NeighboursNumber[] with the number of neighbours of each node stored the corresponding index.
Then iterate through the set and eliminate the leafs ( nodes i which have NeighboursNumber[i] == 1 ) , make sure you add those nodes to another set RemovedSet ( to avoid updating problems ) and then after each iteration go through the RemovedSet and decrease the NeighboursNumber[] entry for all neighbours of each element of the set.
At the end you will have the root node . ( make sure you implement the case were 2 nodes with 1 neighbours are left ) .
After finding the root we proceed to find the size of each subtree. The trick here is to do this while looking for the root :Before eliminating the leafs at the first iteration, start by creating an array SubTreeSize[] and each time we removing a node from the our set, we add the value of that node + 1 to the value of the parent : SubTreeSize[parent] = SubTreeSize[parent] + SubTreeSize[removedNode] + 1 ;
this way, when we find the root , we also have the size of each subtree.
Then we start from the root and check each neighbour it its subtree's size + 1 > nodes / 2 , if yes then we choose that node and start again. When all the children nodes sizes are <= nodes / 2 , break your loop and output that node.
This method took less than a second for a tree with 10^5 nodes.