分而治之算法树木 [英] Divide-And-Conquer Algorithm for Trees

问题描述

我想写一个鸿沟和放大器;征服算法树。对于鸿沟一步我通过删除节点需要一个算法，划分一个给定的无向图G =（V，E）有n个节点和条边为子树。所有子图应该有它们不包含多属性的 N / 2 节点（树应分别尽可能相等）。首先，我想递归地从树中删除所有的叶子，找到最后剩下的节点，然后我试图找到G中最长的路径，并删除它的中间节点。下面给出的图表显示，这两种方法不起作用：

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:

有一些工作的算法，我想要做什么（返回节点中的H上述情况）。

Is there some working algorithm that does what I want (returns the node H in the above case).

推荐答案

我想你可以用这样的算​​法做到这一点：

I think you could do it with an algorithm like this:

开始在根（如果树没有根，选择的任何节点）。
在每个步骤中，尽量降入具有最大的子树（节点下方它是最大的数）的子节点。
如果这样做，会使高于大于N / 2节点的数量，停止，否则继续这个孩子。

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.

这个算法应该是O（log n）的，如果树是合理的平衡，我们有pcomputed每个节点的子树$ P $大小。如果这些条件之一不适用，这将是为O（n）。

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).

这篇关于分而治之算法树木的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！