最小全域木：PrimとKruskalのアルゴリズム

最小全域木（MST）

連結グラフの全域木は、すべての頂点を含み、最小限の辺（V-1本）でサイクルを含まない部分グラフです。最小全域木は合計辺重みが最小の全域木です。

性質

• V個のノードのMSTは正確にV-1本の辺を持つ
• 複数の辺が同じ重みを共有する場合、MSTは一意ではない
• カットの性質により、任意のカットを横切る最軽量の辺がMSTに属する

Kruskalのアルゴリズム

1. すべての辺を重みの昇順にソート
2. Union-Findデータ構造を初期化
3. 各辺（ソート順）について：異なる成分ならMSTに追加、同じ成分ならスキップ
4. V-1本の辺が追加されたら停止

時間: ソートによりO(E log E)

Primのアルゴリズム

1. 任意のノードから開始し、MSTセットに追加
2. MSTノードと非MSTノードを接続するすべての辺から最軽量を選択
3. 選択した辺とノードをMSTに追加
4. すべてのノードがMSTに含まれるまで繰り返す

時間: 優先度キューでO((V+E) log V)