KruskalとPrimは最小全域木をどのように構築しますか?

Question

Accepted Answer

**最小全域木 (MST)** は、加重連結グラフのすべての頂点を**最小の総辺重み**で接続し、サイクルを持たないグラフです。**Kruskal** と **Prim** は 2 つの古典的なグリーディアルゴリズムです。

## Kruskal (辺をソート、union-find)

すべての辺を重みでソートします。サイクルを形成しない最も安い辺を追加します。

```python
def kruskal(n, edges):                 # edges: (weight, u, v)
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path compression
            x = parent[x]
        return x
    mst, total = [], 0
    for w, u, v in sorted(edges):      # cheapest first
        ru, rv = find(u), find(v)
        if ru != rv:                   # no cycle -> take it
            parent[ru] = rv
            mst.append((u, v, w)); total += w
    return mst, total
```

## Prim (min-ヒープでツリーを成長させる)

任意の頂点から開始します。現在のツリーから出ていく最も安い辺を繰り返し追加します。

## 比較

| | Kruskal | Prim |
|---|--------|------|
| アプローチ | 辺をソート + union-find | ノードから成長 + ヒープ |
| 時間計算量 | O(E log E) | O(E log V) |
| 最適な用途 | スパースグラフ | 密グラフ |

## 使用時期 / 落とし穴

**ネットワーク設計** — ケーブルの敷設、水道管、クラスタリングに MST を使用します。両方ともグリーディで、ここでは証明可能に最適です。Kruskal はサイクルを効率的に回避するために union-find が必要です。

## なぜ重要なのか

MST はすべてを接続するコストを最小化します — インフラストラクチャとネットワークレイアウトに直接適用できます。

これはグリーディが証明可能に最適である明確なケースであり、グリーディ選択推論を強化します。

Kruskal は union-find も示しており、これは広いアルゴリズムの到達範囲を持つ構造です。

	Kruskal	Prim
アプローチ	辺をソート + union-find	ノードから成長 + ヒープ
時間計算量	O(E log E)	O(E log V)
最適な用途	スパースグラフ	密グラフ