0
1
2
3
4
5
6
0
∞
∞
∞
∞
∞
∞
4
2
11
9
4
1
4
2
1
2
8
7
9
2
11
2
2
3
4
8
1
7
3
1
1-1
始点と他のノードのdistを初期化します。
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
データ
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を含める
最小全域木を出力
親の情報から最小全域木を構築します。
