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

Question

対称2d配列 "myMSTdata [] []"は、最小スパニングツリーを表すポイントの値です。このツリーを2つのサブツリー（part1、part2）に分割する必要があります。ここで、カット基準は最大の重みを持つエッジです。大きいサイズのサブツリー内の残りのノード数がKになるまで、より大きなサイズのサブツリー（ノードの数が多いサブツリーを意味する）を繰り返し分割したままにしておきます。

Answer 1

この種の操作に隣接リストを使用することを推奨します、

1. ので、あなたは繰り返し頂点
2. エッジ< $ N $の頂点の数の数を区切る必要があります。
3. 実行時に大きなメリットがあります。

あなたが見ている複雑さは分かりますか？

複雑さに満足しているのであれば、繰り返されるDFSをお勧めします。ツリーで作業しているので、繰り返しDFSはすべてのエッジ&の頂点をカバーします。最悪の場合、ランタイムは約O（n^2）になります。