プリム法: 今つながっている場所から木を広げよう
プリム法は、すでにつながっているグループから、外へ伸びる一番安い辺を選んで広げる方法です。
クラスカル法が「辺を安い順に見る」のに対して、プリム法は「今いる場所から広げる」考え方です。
使いどころ
- 最小全域木を作る
- つながっている範囲を少しずつ広げたい
- 優先度付きキューの使い方を学ぶ
手順
- スタートの点を決める
- そこから出ている辺を候補に入れる
- 一番安い辺を選ぶ
- 新しくつながった点から、さらに候補を追加する
図で見る
コピペ用コード
import heapq
graph = {0: [(1, 1), (2, 3)], 1: [(0, 1), (2, 2)], 2: [(0, 3), (1, 2)]}
visited = {0}
queue = graph[0][:]
heapq.heapify(queue)
total = 0
while queue and len(visited) < len(graph):
cost, node = heapq.heappop(queue)
if node in visited:
continue
visited.add(node)
total += cost
for edge in graph[node]:
heapq.heappush(queue, edge)
print(total)
コードの読み方
visitedは、すでに木に入った頂点です。queueには、次に選べる辺を入れています。heapq.heappop(queue)で、一番安い辺を取り出します。
注意点
すでに訪問済みの点へ向かう辺は、輪っかを作るので飛ばします。
AOJで挑戦してみよう！
学んだレシピを実際に使って、ジャッジから「Accepted（正解）」を勝ち取ろう！