最小全域木を求める2つのアルゴリズム

  • 投稿日:
  • by
  • Category:

あまりしないのですが、line君に頼まれたのでたまにはこういう話もいいかなと。

最小全域木とは、各辺に非負の重みが付いた無向連結単純グラフの重み最小の全域木です。

クラスカル(kruskal)のアルゴリズム

E(G) を重みが小さい順に整列して、E(G)={e[1],e[2],・・・,e[|E(G)|]} とする

初期化
  • V(T):=V(G), E(T):=φ
  • S=E(G), i=1 とする
繰り返し
  1. while (T が非連結)
  2. begin
    1. S = S - {e[i]}
    2. if (T ∪ e[i] が閉路を含まない) E(T) := E(T) ∪ e[i] ;
    3. i = i + 1;
  3. end

方針:重みが最小の辺を閉路を含まないように選択していく

プリム(prim)のアルゴリズム

初期化
  • V(T):={v}, E(T):=φ, ただし∀v∈V(G).
繰り返し
  1. while (V(G) - V(T) ≠ φ)
  2. begin
    1. V(T) と V(G) - V(T) を結ぶ、重みが最小の辺 e = xy を選ぶ(x∈V(T), y∈V(G)-V(T))
    2. V(T) := V(T) ∪ {y}
    3. V(T) := V(T) ∪ {e}
  3. end

方針:E(T)に隣接する重みが最小の辺を選択していく

例として次のようなグラフを考えます。

060825_1.png
グラフG

クラスカルのアルゴリズム

まず重みが1の辺をE(T)に含めます。
060825_2.png

次に2も同様に。
060825_3.png

3では、左上の頂点に隣接する辺をE(T)に含めると閉路ができてしまうので含めません。
060825_4.png

4を含めてTが連結になりました。
060825_5.png

プリムのアルゴリズム

左上の頂点を v(∈V(T)) とします。それに隣接する辺の中で重みが最小の辺は重み2の辺です。
060825_6.png

その頂点をTに含めます。そうすると隣接する最小の辺は重み1の辺です。
060825_7.png

同様に重み2の辺、
060825_8.png

重み3の辺、
060825_9.png

重み2の辺と続きます。
060825_10.png

重み3の辺ですが、V(T) と V(G) - V(T) を結ぶ辺は右の辺のみです。
060825_11.png

重み4の辺はどちらでもいいです。
060825_12.png

完成
060825_13.png

両方のアルゴリズムの結果が同じ形になりましたが、必ずしも同じになるとは限りません(ex.プリムのアルゴリズムの例で最後の重み4の辺の選択をもうひとつの辺にする)

このエントリーをはてなブックマークに追加

コメントする