ano*_*ous 3 algorithm tree split graph-theory longest-path
我正在寻找一种算法,通过从中删除一个边缘来分割具有N个节点的树(其中每个节点的最大度数为3),从而使得作为结果的两棵树尽可能接近N/2 .如何找到"最集中"的边缘？
树来自算法的前一阶段的输入,并作为图形输入 - 因此它不平衡,也不清楚哪个节点是根.
我的想法是找到树中最长的路径,然后选择最长路径中间的边缘.它有用吗？
最理想的是,我正在寻找一种解决方案,可以确保这两棵树都没有超过2N/3个节点.
谢谢你的回答.
我不相信你的初始算法适用于我在评论中提到的原因.但是,我认为您可以使用修改后的DFS在O(n)时间和空间中解决此问题.
首先走图表来计算总节点数; 叫这个 现在,选择一个任意节点并将树根目录.我们现在将从根开始递归地探索树,并将为每个子树计算每个子树中有多少个节点.这可以使用简单的递归来完成:
此时,我们知道每个边缘通过移除边缘将得到什么分割,因为如果该边缘下面的子树中有k个节点,则溢出将是(k,n-k).因此,您可以通过迭代所有节点并寻找最均衡(k,n - k)平衡的节点来找到最佳切割.
计算节点花费O(n)时间,并且运行递归访问每个节点和边缘最多O(1)次,因此也花费O(n)时间.对于O(n)的净运行时间,找到最佳切割需要额外的O(n)时间.由于我们需要存储子树节点计数,因此我们也需要O(n)内存.
希望这可以帮助!
| 归档时间： |
|
| 查看次数： |
5408 次 |
| 最近记录： |