c++ - 如何将一棵树划分为两个子树

Question

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

Answer 1

建议对这种操作使用邻接列表，因为

1. 您需要反复分离顶点
2. 边数 < $n$ 顶点数。
3. 运行时间大的好处。

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

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