概要
概要
最小全域木を作るアルゴリズムです。現在の木から外へ伸びる最小の辺を選び続けます。
グラフ / Prim（プリム法）
最小全域木を作るアルゴリズムです。現在の木から外へ伸びる最小の辺を選び続けます。
目次
このページでわかること
概要
最小全域木を作るアルゴリズムです。現在の木から外へ伸びる最小の辺を選び続けます。
考え方
start from any node
repeatedly choose minimum edge leaving the tree要点
O(E log V)
最小全域木
Priority Queue
Kruskal
補足
今ある木を少しずつ広げます。
辺を全体から選ぶのではなく、木の境界から選びます。
木の中と外を色分けすると良いです。
動きで確認
ここでは「どの頂点が注目か」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。