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

Question

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

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

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

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

感谢您的回答。

Answer 1

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

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

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

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

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

希望这可以帮助！

Answer 2

如果您看到我对树的分而治之算法的回答，您可以看到我会找到一个将树划分为 2 个几乎相等大小的树的节点（自下而上算法），现在您只需要选择边缘之一这个节点做你想做的事。

您当前的方法不起作用假设您有一个完整的二叉树，现在将长度路径添加3*log n到叶子之一（命名为bad叶子），您的最长路径将在其他叶子之一内到连接到此bad叶子的路径末尾，并且您的中间边缘将在此路径内（实际上是在您通过坏叶之后），如果您在此边缘上划分基础，您将拥有O(log n)size 的一部分和另一部分O(n)。