algorithm - 通过删除边将树分成相等的部分

Question

我正在寻找一种算法，通过从中删除一条边来拆分具有 N 个节点(其中每个节点的最大度数为 3)的树，以便作为结果的两棵树尽可能接近N/2。如何找到“最居中”的边缘？

这棵树是算法前一阶段的输入，并作为图形输入 - 因此它不平衡，也不清楚哪个节点是根。

我的想法是找到树中最长的路径，然后选择最长路径中间的边。有用吗？

最理想的是，我正在寻找一种解决方案，可以确保两棵树的节点数都不超过 2N/3。

感谢您的回答。

Answer 1

我不相信您的初始算法会因为我在评论中提到的原因而起作用。但是，我认为您可以使用修改后的 DFS 在 O(n) 时间和空间内解决此问题。

首先遍历图表以计算总共有多少个节点；称这个为 n。现在，选择一个任意节点并将树作为根节点。我们现在将从根开始递归地探索树，并为每个子树计算每个子树中有多少个节点。这可以使用简单的递归来完成:

• 如果当前节点为null，则返回0。
• 否则:
  • 对于每个 child ，计算以该 child 为根的子树中的节点数。
  • 返回1+所有子树的节点总数

在这一点上，我们知道对于每条边，通过删除该边我们将得到什么样的拆分，因为如果该边下方的子树中有 k 个节点，则溢出将为 (k, n - k)。因此，您可以通过遍历所有节点并寻找最均匀地平衡 (k, n - k) 的节点来找到最佳切割。

计算节点需要 O(n) 时间，并且运行递归最多访问每个节点和边缘 O(1) 次，因此这也需要 O(n) 时间。对于 O(n) 的净运行时间，找到最佳切割需要额外的 O(n) 时间。由于我们需要存储子树节点数，因此我们也需要 O(n) 内存。

希望这对您有所帮助!