如何将一棵树分割成两棵子树

Question

我有一个对称的二维数组“myMSTdata [] []”，它表示最小生成树MST的值为0，如果没有边或表示真实值代表边缘，现在我需要将此树划分为两个子树（part1，part2），其中切割标准是最大权重的边。然后反复保留对较大尺寸子树（意味着具有更多节点数的子树）进行分区，直到较大尺寸子树中剩余的节点数为K.

Answer 1

建议对这种操作使用邻接列表由于

1. 你需要单独的顶点反复
2. 边缘<数$ n $的顶点数量。
3. 大运行时间的好处。

我可以知道您正在查看的复杂性吗？

如果您对任何复杂性感到满意，我会建议重复的DFS，因为您正在使用树，重复的DFS将覆盖所有边缘&顶点。在最坏的情况下，运行时间大约为O（n^2）。