Dev Study
← アルゴリズムの手法 — CLRS を読むための地図
レッスン 10 / 13·約 9 分·第29期 アルゴリズムの手法 — CLRS を読むための地図

カットを渡る最も軽い辺は使ってよい — 最小全域木

アプリと DB の下に何が積まれているか(左が下、右が上)
  1. 物理機リージョン/AZ
  2. ハイパーバイザVM exit で捕まえる
  3. VMゲストOS
  4. コンテナnamespace / cgroup
  5. プロセスアプリ / DB今ここ

Dijkstra 法の回が扱うのは「1点から各点への最短」です。今回は「全部の点を、合計が最小になるようにつなぐ」問題で、手順は似ていても求めるものが違います。

まず結論

頂点を2つの側に分ける切れ目(カット)を1つ決めると、そこを渡る辺のうち最も軽いものは、どれかの最小全域木に必ず入っています。

Kruskal 法も Prim 法もこの1つの性質を使っていて、違うのはカットを選ぶ順序だけです。5頂点の例では、総当たり125本の最小28と両方の結果が一致しました。

? 読む前に予測

5つの頂点があり、どの2点の間にも辺が1本ある図(全部で10本)を考えます。辺を4本選んで5点すべてを閉路なしでつなぐ選び方(全域木)は何通りあるでしょうか。

当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。

抽象原理

カットを渡る最も軽い辺は、入れ替えても損をしない

全域木は5頂点で125本、10頂点なら 10^8 本あります。全部を比べずに「この辺は採ってよい」と言うための性質が要ります。

頂点を2つの側に分けます。この分け方をカットと呼び、両側をまたぐ辺を「カットを渡る辺」と呼びます。性質は1行です。

カットを渡る辺のうち最も軽い辺 e は、どれかの最小全域木に入っている。

理由は、貪欲法の回で扱う入れ替えの考え方と同じです。e を含まない最小全域木 T があったとします。T に e を足すと閉路が1つできます。e はカットを渡っているので、閉路はどこかでもう一度カットを渡って戻ってきます。その辺を f とします。e が最も軽いので f は e 以上です。f を外して e を入れると、全域木のまま合計は増えません。

入れ替えの考え方 — e を含まない木も、e を含む木に直せる
カットで頂点を2つに分ける
渡る辺のうち最も軽いものを e とする
e を含まない木 T に e を足す閉路が1つできる
閉路はカットをもう一度渡る
そこの辺 f を外すf の重み ≥ e の重み
合計は増えない
e を含む最小全域木ができる
  • ・「必ず全ての」ではなく「どれかの」最小全域木に入る。同じ重みの辺があると木が複数ありうる
  • ・カットはどれを選んでもよい(どのカットでも成り立つ)
具体実物

5頂点で、15通りのカットを全部確かめる

検証用の図は、5頂点の全ペアに辺を張り、重みを random.Random(29).randint(1, 20) で決めたものです。

(0,1,18) (0,2,3) (0,3,12) (0,4,20) (1,2,20) (1,3,10) (1,4,3) (2,3,17) (2,4,12) (3,4,13)

総当たりの最小は28で、合計28の木は2本ありました。頂点0を含む側を決めて、15通りのカットすべてで「渡る辺のうち最も軽い辺」を調べました(Python 3.14.6 / macOS arm64、2026-10-07)。

$ python3 cuts.py(抜粋。左がカットの頂点0を含む側)コマンド出力
spanning trees: 125  min weight: 28  trees attaining it: 2
[0]           lightest [(0, 2, 3)]                in some MST: True
[0, 2]        lightest [(0, 3, 12), (2, 4, 12)]   in some MST: True
[0, 2, 3]     lightest [(1, 3, 10)]               in some MST: True
cuts: 15 / 15 True

カット {0, 2} では重み12の辺が2本並び、2本の最小全域木がそれぞれ片方を含んでいました。性質が「どれかの」と言う理由がこれです。Kruskal 1956 は冒頭で、一意になる条件を次のように書いています。

If a (finite) connected graph has a positive real number attached to each edge (the length of the edge), and if these lengths are all distinct, then among the spanning trees (German: Gerüst) of the graph there is only one, the sum of whose edges is a minimum; that is, the shortest spanning tree of the graph is unique.

✓ ここまでの確認

例の5頂点の図で、カットを {0, 2} と {1, 3, 4} に取ると、渡る辺のうち最も軽いのは重み12の (0,3) と (2,4) の2本でした。最小全域木は2本あります。正しい説明はどれですか。

抽象原理

手順の違いは、どのカットを使うかの違い

カットの性質は「どのカットでも成り立つ」ので、手順はカットの選び方で決まります。

  • Kruskal 法: 辺を軽い順に見て、閉路を作らなければ採る。採るとき、辺の一端を含むグループと残りがカットになる。より軽い辺は処理済みなので、その辺はこのカットで最も軽い。
  • Prim 法: 1点から始め、「今の木」と「それ以外」をカットにして、渡る辺のうち最も軽いものを足す。

Kruskal の閉路判定には Union-Find を使います。各頂点のグループの代表を持ち、辺の両端の代表が同じなら閉路になります。Union-Find の計算量の解析は本教材では扱いません。

具体実物

原論文の手順と、Dijkstra 法との近さ

Kruskal 1956 の Construction A がそのまま Kruskal 法です。

Construction A. Perform the following step as many times as possible: Among the edges of G not yet chosen, choose the shortest edge which does not form any loops with those edges already chosen.

同じ論文の Construction B は、頂点の部分集合 V から育てる形で、V を1点にすれば1点から育てる手順になります。

Dijkstra 1959 の2つの問題のうち、Problem 1 が最小全域木です。

Problem 1. Construct the tree of minimum total length between the n nodes.

Step 1. The shortest branch of set II is removed from this set and added to set I. As a result one node is transferred from set B to set A.

1本足すたびに頂点が1つ移る、1点から育てる書き方です。Dijkstra は Kruskal と比べています。

In their solutions all the - possibly ½n (n -1) - branches are first of all sorted according to length. … Our method only requires the simultaneous storing of the data for at most n branches

Dijkstra 法の回で扱う最短経路の手順とは、取り込む点を選ぶ値が違うだけです。

heapq.heappush(pq, (dist[u] + w, v))  # Dijkstra: 始点からの距離の合計
heapq.heappush(pq, (w, v))            # Prim: 木から伸びる辺1本の重み

同じ図で、採る順序は違っても、この実行では結果の木は同じでした。

手順採った辺の重みの順合計
Kruskal 法3, 3, 10, 1228
Prim 法(頂点0から)3, 12, 10, 328

ただし頂点 {0, 2} まで育てた時点で、(0,3) と (2,4) が重み12で並びます。同点の扱いで (2,4) を先に取れば、順は 3, 12, 3, 10 になり、もう一方の最小全域木ができます。

誰が最初かは言い切りません。書誌を年の順に並べると Borůvka 1926・Jarník 1930・Kruskal 1956・Prim 1957・Dijkstra 1959 です。Kruskal の参考文献は Borůvka の1件だけで、Jarník は冒頭で Borůvka の論文を挙げ、別の、より簡単に思える方法で解けると書いています。

lze řešiti ještě jiným a — jak se mi zdá — jednodušším způsobem.

✓ ここまでの確認

Prim 法と Dijkstra 法は、どちらも「集合の外から1点ずつ取り込む」手順です。違いはどこにありますか。

⇄ 2つを見比べる
具体例 A

Kruskal 法 — 辺を軽い順に

辺を全部、重みの順に並べてから見ていきます。木は途中で何本にも分かれていて、最後に1本につながります。閉路の判定に Union-Find を使います。NetworkX 3.7 の minimum_spanning_tree は、既定がこちらです。

具体例 B

Prim 法 — 1点から育てる

1点から始め、木と外側の境目を渡る最も軽い辺を足していきます。木は常に1本です。手順は Dijkstra 法とほぼ同じで、点を選ぶ値が距離の合計でなく辺1本の重みになります。

採る辺の順序が違うのに、例の図で両方とも合計28の木を返したのはなぜでしょうか。

それぞれの手順で、1本採るたびに「どのカットで最も軽い辺だったか」を考えてみてください。

この章のまとめ

  • カットを渡る最も軽い辺は、どれかの最小全域木に入る。 e を含まない木に e を足すと閉路ができ、カットを渡る別の辺と入れ替えても合計は増えない。
  • 重みが同じ辺があると最小全域木は複数ありうる。例の図では2本あった。
  • Kruskal 法と Prim 法は同じ性質を、違うカットの順序で使う。 例の図では採る順序が違い、合計はどちらも28で総当たりと一致した。
  • Prim 法は Dijkstra 法と、点を選ぶ値が違うだけ。Dijkstra 1959 の Problem 1 は最小全域木そのもの。
  • 最小全域木と最短経路木は別物。 「最小コスト」と言われたら、何の合計を最小にしたかを確かめる。
  • 誰が最初かは言い切らない。Borůvka 1926 から Dijkstra 1959 まで書誌を並べるにとどめる。

既存クイズでは、「アルゴリズムとデータ構造 III(発展編)」の algorithm-3-2・-3-3、「アルゴリズムとデータ構造」の algorithm-16(Union-Find)が対応します。「ネットワーク機器とレイヤー」の network-devices-12(STP)も木を作りますが、どの種類の木かは一次ソース(IEEE 802.1D 本文)を確認できなかったため、本教材では扱いません。

CLRS(『アルゴリズムイントロダクション』)の目次や索引で minimum spanning tree(最小全域木) を探すと、この回の内容に対応する章や節が見つかります。章の題と番号は版で変わるので、手元の目次で確かめてください。

自分の現場で確かめる

読んだだけでは身につきません。手元の環境で実際に見てみてください。

環境:

理解度チェック

読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。

問題 1 / 3正解: 0

エージェントが「本社から各拠点への最短経路を集めた木を作ったので、回線の合計コストも最小です」と報告してきました。この説明の評価はどれですか。

用語集(4語)
全域木
グラフの全頂点を、閉路を作らずにつなぐ辺の選び方。頂点が n 個なら辺は n−1 本になる。
最小全域木
全域木のうち、辺の重みの合計が最小のもの。重みに同じ値があると複数ありうる。NetworkX の文書も「There may be more than one tree with the same minimum or maximum weight.」と書く。
カット
頂点全体を2つの側に分ける切れ目。両側をまたぐ辺を「カットを渡る辺」と呼ぶ。最大フローの回でも同じ語を使う。
Union-Find
頂点がどのグループに属するかを代表で表し、2つのグループを1つにまとめる仕組み。Kruskal 法では、辺の両端の代表が同じなら閉路になると判定するのに使う。

出典(一次ソース)