Kruskal 法

2025年10月20日

Kruskal 法

英語表記: Kruskal’s Algorithm

概要

Kruskal法（クラスカルほう）は、「アルゴリズムと計算量」の分野における「グラフアルゴリズム」の一つであり、特に最小全域木（Minimum Spanning Tree: MST）を求めるために用いられる非常に重要な手法です。これは、重み付きグラフにおいて、すべての頂点（ノード）を接続しつつ、使用する辺（エッジ）の重みの合計が最小となるような木構造を効率的に構築することを目的としています。直感的で分かりやすい動作原理を持つため、グラフ理論を学ぶ上で最初に習得すべきアルゴリズムの一つと言えるでしょう。

詳細解説

Kruskal法は、最小全域木を求めるアルゴリズムの中でも、辺（エッジ）に着目して動作する「貪欲法（Greedy Method）」の代表例です。このアルゴリズムが、指定された階層（グラフアルゴリズム → 最小全域木）においてなぜ重要なのかというと、そのシンプルな手順にもかかわらず、必ず最適解（最小コストの全域木）を導き出す保証があるからです。

Kruskal法の目的と動作原理

私たちの目標は、与えられたネットワーク（グラフ）を、コストを最小限に抑えながら完全に繋ぎきることです。Kruskal法は、この目標を達成するために以下のステップを踏みます。

辺のソート（計算量の基盤）
まず、グラフに含まれるすべての辺を、その重み（コスト）が小さい順に完全にソートします。この初期ソートが、Kruskal法の計算効率を大きく左右します。辺の数$E$が多い場合、このソートにかかる計算量$O(E \log E)$が、全体の計算量の上限を決めることが多いのです。
貪欲な選択と閉路のチェック
ソートされたリストの先頭から、重みが最も小さい辺を一つずつ選び出します。ここで重要な判断が入ります。選んだ辺を現在の木に追加した際に、閉路（サイクル）が形成されるかどうかをチェックします。
辺の採用と拒否
- 閉路が形成されない場合：その辺は採用され、最小全域木の一部となります。
- 閉路が形成される場合：その辺は拒否されます。なぜなら、既にその辺の両端の頂点は別の経路で繋がっているため、より高コストな迂回経路を追加することは最小化の目的に反するからです。この「今、最善（最小）の選択をする」という判断こそが貪欲法の核心です。
終了条件
このプロセスを繰り返し、最終的にグラフの全頂点$V$を繋ぐために必要な辺の数（$V-1$本）が揃った時点で、最小全域木が完成し、アルゴリズムは終了します。

Union-Find構造の貢献

Kruskal法が実用的な「グラフアルゴリズム」として成立するためには、ステップ2の「閉路チェック」をいかに高速に行うかが鍵となります。ここで活躍するのが、Union-Find構造（素集合データ構造）です。

Union-Find構造は、頂点がどの集合（グループ）に属しているかを管理します。

Find操作: ある頂点が現在どの集合の代表要素（ルート）に属しているかを高速に検索します。
Union操作: 2つの集合を統合します（新しい辺で頂点同士が繋がったことを示す）。

新しい辺を追加するとき、その辺の両端の頂点に対してFind操作を行い、もし両者が既に同じ集合に属していれば、その辺を追加すると閉路ができてしまうと判断できます。Union-Find構造は非常に効率的であり、計算量を大幅に削減してくれるため、Kruskal法の性能向上に不可欠な要素となっています。最小全域木を学習する際は、ぜひこのデータ構造の役割にも注目してみてください。

具体例・活用シーン

活用例

通信ネットワークの設計: 複数の拠点（頂点）を光ファイバーケーブル（辺）で繋ぐ際、ケーブルの敷設コスト（重み）を最小限に抑えつつ、すべての拠点が通信できるようにする設計図を作成します。
電力・ガス供給網: 全ての家庭や工場（頂点）にエネルギーを供給するためのパイプラインや送電線（辺）を、建設費用が最も安くなるように計画します。
交通網の整備: 複数の都市を結ぶ新しい道路や鉄道を建設する際、総建設距離や費用を最小化しながら、全ての都市がネットワークに組み込まれるように計画します。

比喩：ケチな工事監督の物語

Kruskal法の動作を理解するために、少し物語仕立ての比喩を紹介します。

あなたは、辺境の地にあるたくさんの小さな村々（頂点）を、予算を極限まで抑えて道路で繋ぐプロジェクトの「ケチな工事監督」だと想像してください。監督であるあなたのポリシーはただ一つ、「無駄を許さない」ことです。

全リストの作成と並べ替え: まず、建設可能なすべての道路の候補（辺）と、その建設費用（重み）をリストアップします。そして、費用が安い順に、上から下へと並べ替えます。「ふむ、この100万円の道が一番安いな」とブツブツ言いながら。
貪欲な選択: リストの一番上（最も安い道）から順に、道路を採用していきます。
閉路の厳重チェック: ここが肝心です。ある道路を選ぼうとしたとき、「待てよ、この道を通さなくても、既に別の遠回りな道でこの二つの村は繋がっているではないか！これ以上繋いでも無駄遣いだ！」とあなたは厳しくチェックします。
- もしその道路を追加することで、既に繋がっている村同士がさらに別の道で繋がれてしまう（閉路ができる）なら、その道は「無駄な出費」として即座に却下します。
- まだ繋がっていない新しい村同士を繋ぐ道であれば、「よし、これは必須経費だ」として採用します。
終了: すべての村が一本のネットワークで繋がった瞬間、「これ以上一円たりとも使う必要はない！」と監督は満足し、プロジェクトを終了します。

この「ケチな工事監督」の行動は、まさにKruskal法の「最小コストの辺を貪欲に選び、閉路ができたら却下する」という動作そのものです。この一見単純な貪欲な選択が、最終的に最も効率的（最小コスト）な全域ネットワークを生み出すという点が、Kruskal法の美しさであり、グラフアルゴリズムとしての強力な証明なのです。

資格試験向けチェックポイント

Kruskal法は、基本情報技術者試験や応用情報技術者試験において、「アルゴリズムと計算量」の分野、特にグラフ理論の核として頻出します。ITパスポートでは具体的な手順よりも概念が問われる傾向があります。

| 試験レベル | 典型的な出題パターンと学習のヒント |
| :— | :— |
| ITパスポート | 概念理解：最小全域木を求めるアルゴリズムの一つであること、通信網の最適化などに使われることなど、基礎的な用途が問われます。「最もコストの低い辺から選んでいく」という貪欲法の概念を押さえましょう。 |
| 基本情報技術者 | 手順の理解とPrim法との比較：具体的なグラフが提示され、Kruskal法を用いて最小全域木を導出させる問題が出ます。特に、辺をソートするステップと、閉路を避けるための判断プロセスを正確に実行できるかが重要です。また、最小全域木を求めるもう一つの代表的なアルゴリズムであるPrim法との違い（Kruskal法は辺ベース、Prim法は頂点ベース）を整理しておく必要があります。 |
| 応用情報技術者 | 計算量とデータ構造：アルゴリズムの効率性、特に計算量$O(E \log E)$がどこから来るのか（辺のソートが支配的であること）を理解しているかが問われます。さらに、閉路検出に使われるUnion-Find構造の概念や、その効率的な実装方法（経路圧縮やランク付け）が、グラフアルゴリズムの知識として深く問われることがあります。Kruskal法が貪欲法の一例として最適解を導く理由（カット特性）といった理論的な背景も求められる場合があります。 |

重要Tips:

貪欲法であること: Kruskal法もPrim法も貪欲法ですが、Kruskal法は「現時点で最も軽い辺」を、Prim法は「現時点で木に繋がる最も軽い辺」を選ぶという違いがあります。この選択基準の違いを明確にしましょう。
閉路検出の仕組み: 最小全域木は「木」でなければならないため、閉路を作らないことが絶対条件です。Kruskal法では、Union-Find構造を用いてこの閉路チェックを高速に行っている点を必ず覚えておきましょう。
計算量の理解: 辺のソートがボトルネックになるため、辺の数$E$に依存した計算量$O(E \log E)$を持つことを理解し、「アルゴリズムと計算量」の文脈で評価できるようにしましょう。