我正在尝试为树编写一个分而治之的算法。对于划分步骤，我需要一种算法，通过移除一个节点，将具有 n 个节点和 m 条边的给定无向图 G=(V,E) 划分为子树。所有子图都应具有不包含超过 n/2 个节点的属性(树应尽可能等分)。首先我尝试递归地从树中删除所有叶子以找到最后一个剩余节点，然后我尝试找到 G 中最长的路径并删除它的中间节点。下图显示这两种方法都不起作用:
是否有一些工作算法可以满足我的要求(在上述情况下返回节点 H)。
最佳答案
我想你可以用这样的算法来做到这一点:
从根开始(如果树没有根，选择任何节点)。
在每一步中，尝试下降到具有最大子树的子节点(它“下面”的节点数最大)。
如果这样做会使“上方”的节点数大于 n/2，则停止，否则继续处理该子节点。
如果树相当平衡并且我们为每个节点预先计算了子树的大小，则该算法应该是 O(log n)。如果其中一个条件不适用，则为 O(n)。
关于algorithm - 树的分而治之算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8193574/