Kruskal's algorithmとは? わかりやすく解説

Weblio 辞書 > 学問 > OR事典 > Kruskal's algorithmの意味・解説 

クラスカル法

読み方くらすかるほう
【英】:Kruskal's algorithm

1956年, クラスカルによって提案され最小木問題を解くためのアルゴリズム1つ. のない点集合のみの状態から, 重み小さい順に閉路構成しない限り1本ずつ加えていく操作繰り返す. 全張木(全域木)が得られ時点終了すると, その全張木1つ最小木になっている. 貪欲算法一種. 多項式時間アルゴリズムである.

「OR事典」の他の用語
グラフ・ネットワーク:  NP困難  PERT  TSP多面体  クラスカル法  クラスター分析  グラフ  シュタイナー最小木

クラスカル法

(Kruskal's algorithm から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/08/30 08:14 UTC 版)

クラスカル法: Kruskal's algorithm)は、グラフ理論において重み付き連結グラフの最小全域木を求める最適化問題アルゴリズムである。

概要

このアルゴリズムは、1956年ジョゼフ・クラスカル英語版Proceedings of the American Mathematical Society で発表した (pp. 48–50)。

クラスカル法は貪欲法の一種で、最小全域木を求める他のアルゴリズムとしては、プリム法逆削除法英語版ブルーフカ法などがある。最小全域木とは、グラフの全ての頂点を含むで、辺の重みの総和が最小のものを言う。連結されていないグラフでは、「最小全域森」(それぞれの連結部分の最小全域木の集合)を求められる。

アルゴリズムの解説

クラスカル法の手順は次の通り。

グラフの各頂点がそれぞれのに属するように、森(木の集合) F を生成する(つまり頂点1個だけからなる木が頂点の個数だけ存在する)
S ← グラフの全ての辺を含む集合
while (S空集合ではない)
    S から重みが最小の辺 e を削除する
    if (e が2つの木を連結するもの)
        e を森に加え、2つの木を1つにまとめる

このアルゴリズムが終了した時点で、森は単一の木となっており、元のグラフの最小全域木になっている。

性能

グラフ内の辺数を E、頂点数を V とすると、クラスカル法の計算量はデータ構造が単純であれば O(E log E) または O(E log V) である。これらは次の理由で等価である。

  • E は最大でも V2 であり、log V2 = 2 log V であるから log EO(log V) である。
  • 孤立した頂点はそれ自体が必ず最小全域木となるので無視すると、VE+1 であるから log VO(log E) である。

この計算量は以下のように求められる。まず、辺を重みでソートするのに比較ソートを用いると O(E log E) となる。これにより、「S から重みが最小の辺を削除する」操作を定数時間で行えるようになる。次にどの頂点がどの木に属しているかを保持するのに素集合データ構造を使う。各辺について、2回の探索操作と1回の和集合操作が必要であり、O(E) 回となる。単純な素集合データ構造であっても O(E log V) の時間内に O(E) 回の操作を実行できる。したがって、総計算量は O(E log E) = O(E log V) である。

辺が事前にソート済みか(分布数えソート基数ソートを使って)線形時間でソートできる場合、より洗練された素集合データ構造を使うことができ、O(E α(V)) の計算量になる。ここでαはアッカーマン関数の逆関数で極めてゆっくり増加する。

元のグラフ。辺のそばにある数値は重みである。今のところ、どの辺も強調されていない。
ADCE が最短(重みが5)の辺なので、まず AD を無作為に選んで強調表示している。つまり、AD を木とした。
CE が最短の辺で、それによって閉路は形成されない(同じ木を連結する辺ではない)ので、新たに木に含める。
次に短い DF を選び、同様に処理する。
次に短いのは長さ 7 の ABBE なので、無作為に AB を選ぶ。なお、BD が同じ木に属すようになったため、BD を赤で示している。つまり BD は捨てるべき辺である。
次に同じ長さ 7 の辺 BE を選ぶ。ここでさらに多くの辺が赤になっている。BCDEEF は同じ木に属する頂点を結ぶ辺であるため、捨てられる。
最後に長さ 9 の辺 EG を選び、これで最小全域木が完成する。

正しさの証明

このアルゴリズムの正しさの証明は2つの部分に分けられる。第一は全域木を生成していること、第二はそれが最小の重みであることである。

全域木

重み付き連結グラフ

Optimization computes maxima and minima.
非線形(制約付き)
凸最適化
組合せ最適化
メタヒューリスティクス


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

カテゴリ一覧

すべての辞書の索引



Weblioのサービス

「Kruskal's algorithm」の関連用語


2
14% |||||




Kruskal's algorithmのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



Kruskal's algorithmのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2025 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのクラスカル法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS