プリムのアルゴリズム – 定義

最小重みスパニングツリー

プリムのアルゴリズムは、値接続グラフの最小スパニング ツリーを決定するアルゴリズムです。つまり、各エッジの重みの合計が最小になるように、すべての頂点を含むツリーを形成するエッジのサブセットを見つけます。グラフが接続されていない場合、アルゴリズムはグラフの接続されたコンポーネントの最小スパニング ツリーのみを決定します。 1957 年にロバート プリムによってデザインされました。

原理

このアルゴリズムは、頂点を任意に選択し、その頂点からツリーを成長させることで構成されます。各増加は可能な限り最も経済的な方法で行われます。

アルゴリズム

 
 PRIM手順 
 ローカルパラメータ: 整数 s、グラフ G 
 グローバルパラメータ：Tグラフ 
 変数: 
 整数 i、m、y 
 実数:v 
 セット：M 
 TVectNent: pp 
 TvectNReal: d 
 始まり 
 1 T <- 空のグラフ 
 2M <- 空のセット 
 3 For i <- 0 から N Do まで 
 4 d[i] <- コスト(s, i, G) 
 5 pp[i] <-s 
 6M <- (i,M) を加算 
 7 終了 
 8M <- 削除 (s,M) 
 9 While M <> Empty_set Do 
 10m <- (M,d) を選択 
 11M <- 削除 (m,M) 
 12 z <- pp[m] 
 13 v <- コスト (m,z,G) 
 14 T ← 加算停止 コスト v から T まで 
 15 For i <-1 から d° m in G Do 
 16 y <- i ith_succ_of m in G 
 17 もしそうなら 
$$ {\in} $$
 M と (コスト(m,y,G) < d[y]) の場合 
 18 d[y] <- コスト(m,y,G) 
 19 pp[y] <- m 
 20 エンドイフ 
 21 エンドフォー 
 22 途中で終了 
 終了アルゴリズム 
 

(以下の原則は提案された実装とは異なることに注意してください)。

初期化ステップでは、頂点をランダムに選択します。最初のステップが終了すると、頂点が 1 つ、エッジが 0 つ含まれるツリーが完成します。次に、次の方法で最小ツリーを再帰的に構築します。ステップ n で、n 個の頂点と n-1 個のエッジを含むツリーがすでに構築されているので、ツリーの頂点を頂点にリンクするすべてのエッジのリストを確立します。木の上ではありません。次に、最小の重みのエッジを選択し、それをツリーに追加します。ツリーには n+1 個の頂点と n 個のエッジが含まれます。グラフのすべての頂点がツリーに含まれると、アルゴリズムは終了します。

アルゴリズムの複雑さはO( A * S ) で、A はエッジの数、S は頂点の数です。