c++ - ツリーを2つのサブツリーに分割する方法

Question

エッジの重みを表すエッジまたは実際の値がない場合、値が0の最小スパニングツリーMSTを表すポイントの対称2D配列 "myMSTdata [] []"があり、このツリーを2つに分割する必要があります。サブツリー（part1、part2）。ここで、切断基準は最大の重みを持つエッジです。次に、大きいサイズのサブツリー内の残りのノード数がKになるまで、大きいサイズのサブツリー（つまり、ノード数が多いサブツリー）を繰り返し分割し続けます。

Answer 1

この種の操作には隣接リストを使用することをお勧めします。

1. 頂点を繰り返し分離する必要があります
2. エッジの数<$n$頂点の数。
3. 実行時間のメリットが大きい。

あなたが見ている複雑さを教えてもらえますか？

複雑さに満足している場合は、DFSを繰り返すことをお勧めします。ツリーで作業しているため、DFSを繰り返すとすべてのエッジと頂点がカバーされます。最悪の場合、実行時間は約O（n ^ 2）になります。