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

Prim法:今ある木から外へ最も軽く伸ばす

木の内外をまたぐ最小の辺を選ぶ手順を追い、Dijkstra法との優先度の違いを整理する。

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

更新日

この記事の目次
  1. 木を伸ばす境界の辺を選ぶ
  2. 境界を更新しながら進む
  3. Dijkstra法の距離とは違う
  4. キューとグラフ表現の選択
  5. この記事をロゲイアに質問する理解を確かめる

木を伸ばす境界の辺を選ぶ

Prim法は無向重み付きグラフの一頂点から始め、現在の木にある頂点集合と、その外側を結ぶ辺の中で最も軽い辺を選んで木を伸ばします。最小全域木を求める方法で、負の重みも扱えます。選ぶのは木に含まれる頂点と外側の頂点を結ぶ最小辺であり、直前に追加した頂点に接続する辺だけではありません。始点は任意ですが、出力は始点からの最短路木ではありません。全域木の合計重みを最小化するという目的を、探索の見た目から取り違えないようにします。

境界を更新しながら進む

A−B=2、A−C=3、B−C=1、B−D=4、C−D=5とし、Aから始めます。初めはA−Bを選び、木が{A,B}になったら境界のB−C=1を選びます。次はB−D=4で全頂点が入り、合計7です。最後に追加したCからDへ伸ばすと5になるため、そこだけを見ては最小辺を選べません。木に新しい頂点を入れたら、その頂点から外側への辺を候補に加え、両端が既に内側になった古い候補は採用しないようにします。

Dijkstra法の距離とは違う

頂点ごとの最良の接続辺を持つ実装では、外側の頂点vのキーは、現在の木からvへ渡る一本の辺の最小重みです。Dijkstra法のg(v)のように、始点からそこまでの辺の重みを合計した距離ではありません。この違いが、負の重みを許せることや求める木の目的と結びつきます。優先度付きキューを使うという共通点だけで同じアルゴリズムだと考えるのは誤りです。更新時には木へ接続する親の辺も記録し、どの辺で各頂点を取り込んだかを復元します。

キューとグラフ表現の選択

隣接リストと頂点キーを更新できる二分ヒープの実装はO(E log V)時間で説明できます。辺をすべて入れる遅延版では古い候補も保持するため、キューの領域と整列に近い費用を別に数えます。密なグラフには配列や行列で最小候補を走査するO(V²)版も選べます。非連結入力では一頂点からの処理だけでは全体を覆えず、未訪問成分ごとに再開して森を作るなどの仕様が必要です。同値重みでは答えが一意とは限らず、辺集合だけでなく木の条件と合計重みを検証します。

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

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

CS基礎を固める · STEP 11

学習コースから次を選ぶ