アルゴリズム・データ構造図鑑 · 基礎から応用へ

Kruskal法:閉路を作らない軽い辺を選ぶ

辺を重み順に調べ、Union-Findで成分を管理して最小全域木・最小全域森を作る。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 求めるのは最短経路ではない
  2. 軽い辺から成分を結ぶ
  3. Union-Findが判断すること
  4. 同じ重みと計算量
  5. この記事をロゲイアに質問する理解を確かめる

求めるのは最短経路ではない

Kruskal法は無向の重み付きグラフから、全頂点をつなぐ辺の重みの合計が最小となる全域木を求めます。ある始点から各頂点までの経路が最短になる木とは別です。グラフが非連結なら成分ごとの最小全域木を合わせた最小全域森になります。負の重みも使えます。全頂点を含むという条件があるため、負の辺があるからといって閉路を自由に加えてよいわけではありません。木は連結で閉路がなく、連結グラフのV頂点ではV−1本の辺を持ちます。

軽い辺から成分を結ぶ

A−Bが1、B−Cが2、A−Cが3、C−Dが4、B−Dが5という例では、まずA−B、次にB−Cを選びます。A−Cの両端は既に同じ成分にいるので、この辺は閉路を作るとして飛ばします。C−Dを選ぶと4頂点が3本の辺でつながり、合計重みは7です。選択済みの辺が複数の木に分かれていても構いません。二つの成分を結ぶたびに森が大きくなり、最後に一つの全域木になります。

Union-Findが判断すること

Union-Findでは、各頂点が属する成分の代表元を管理します。辺u−vを見てfind(u)とfind(v)が異なれば、その辺を採用して成分を併合します。同じなら既に森の中にuからvへの道があり、辺を加えると閉路です。経路圧縮やサイズによる併合は、この判定を効率化します。Union-Findが重みの最小性を判断しているわけではありません。安全な辺を小さい順に検討する貪欲な選択と、閉路を防ぐ成分管理の役割を分けて理解します。

同じ重みと計算量

辺の整列が通常O(E log E)で、効率的なUnion-Findの費用はそれより小さいため、全体もこの整列費用で評価できます。既に辺が整列している場合は別に数えます。重みが同じ辺があると最小全域木が複数存在することがあり、出力の辺集合が違っても合計重みが最小なら正解です。自己ループは採用せず、多重辺は候補として扱えます。非連結入力でV−1本を得られなかったとき、存在しない木を返したふりをせず、森を返す仕様かエラーにする仕様かを明確にします。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 11

学習コースから次を選ぶ