[解決済み] 最大スパニングツリーの求め方は？

質問

最小スパニングツリーには、クラスカルのアルゴリズムの逆が通用するのでしょうか？つまり、毎ステップ最大の重み（エッジ）を選ぶということ？

他に最大分散木を求めるアイデアがあれば教えてください。

どのように解決するのですか？

はい、そうです。

ネットワークGの最大重量スパニングツリーを計算する方法の1つ -。 Kruskalによるもので、以下のようにまとめることができる。

1. Gの辺を重さの降順に並べ替える。最大重量のスパニングツリーを構成するエッジの集合をTとする。T = ∅ とする。
2. Tに最初の辺を追加する。
3. 次の辺がTのサイクルを形成しない場合のみ、Tに追加する。 残りの辺がない場合は終了し、Gが切断されたことを報告する。
4. Tがn-1個のエッジを持つ場合（nはGの頂点の数）、停止して を出力する。そうでない場合はステップ 3 に進む。

出典 https://web.archive.org/web/20141114045919/http://www.stats.ox.ac.uk/~konis/Rcourse/exercise1.pdf .