プリムのアルゴリズム | アルゴリズムビジュアル大事典

シンボル

データ
Tに含まれるノードへ向かうエッジの重みの最小値dist
最小全域木における親parent
ノード間の距離weight

始点の決定と初期化
適当な始点のdistを0に初期化します。
他のノードのdistを大きな値で初期化します。
最小全域木の構築
distが最小のノードを探します。# find minimum
distが最小のノードを指します。u
ノードのdistとparentを更新します。dist[v] ← weight[u][v]
parent[v] ← u
最小全域木の暫定エッジを表します。(v, parent[v])
最小全域木を拡張していきます。Tにuを含める
最小全域木を出力
親の情報から最小全域木を構築します。

アニメーション

始点の決定と初期化
プリムのアルゴリズム | 始点の決定と初期化

最小全域木の構築
プリムのアルゴリズム | 最小全域木の構築

最小全域木を出力
プリムのアルゴリズム | 最小全域木を出力