プリム法（Prim’s Algorithm）とは
プリム法とは、
です。
最小全域木とは、すべての頂点を含み、辺の重みの合計が最小となるグラフのことです。
以下の例では、最小全域木はこのように辺が選択されます。
プリム法は、任意の頂点からスタートし、貪欲法で順次コストの低い頂点を追加していきます。
優先度付きキュー（ヒープ） + 隣接リストで効率的に実装でき、計算量はO（E log V）となります。
Eは辺の数、Vは頂点の数を表しています。
他にも最小全域木を求める方法は、 クラスカル法などがあります。
アルゴリズムの概要
1. 初期化
全ての頂点に対して、コストを無限大（∞）に設定します。
次に任意の頂点をスタート地点に設定し、スタート自身のコストを0とします。
2. 新規ノードの追加し、隣接ノードのコストを更新
未訪問のノードの中で到達コストが最小のノードを選択して、そのノードへ移動します。
現在の頂点から伸びた辺を使い、隣接ノードの到達コストが小さくなる場合、コストを更新します。
そして現在の頂点を訪問済みにします。
3. 全頂点を訪問するまで繰り返す
全頂点が訪問済みになるまで、「2. 新規ノードの追加し、隣接ノードのコストを更新」を繰り返します。
実装(Python)
プリム法をpythonで実装した例です。
import heapq
def prim(graph):
start_node = list(graph.keys())[0] # 任意の頂点を開始点にする
mst = [] # 最小全域木の辺を格納するリスト
visited = set()
min_heap = [(0, start_node, None)] # (重み, 現在の頂点, 親頂点)
while min_heap:
weight, node, parent = heapq.heappop(min_heap)
if node in visited:
continue
visited.add(node)
if parent:
mst.append((parent, node, weight))
for next_node, edge_weight in graph[node]:
if next_node in visited:
continue
heapq.heappush(min_heap, (edge_weight, next_node, node))
return mst実行してみます。
# グラフの定義（隣接リスト表現）
graph = {
'A': [('B', 20), ('D', 5), ('E', 10)],
'B': [('A', 20), ('C', 10), ('E', 3)],
'C': [('B', 10), ('E', 15), ('F', 7)],
'D': [('A', 5), ('E', 10)],
'E': [('A', 10), ('B', 3), ('C', 15), ('D', 10), ('F', 7)],
'F': [('C', 7), ('E', 7)],
}
# プリム法の実行
mst = prim(graph)
print("最小全域木:", mst)最小全域木: [('A', 'D', 5), ('A', 'E', 10), ('E', 'B', 3), ('E', 'F', 7), ('F', 'C', 7)]
参考文献
コメント