Prim法
Abstract
Prim法は, 辺重み$ wが与えられたネットワーク$ \mathcal{N} = \left((V, E), w \right)に対する最小全域木問題を解くためのアルゴリズム. ヒープを利用することで, $ O(|E| \log |V|)time. Explanation
TODO 書く.
Implementation
グラフ構築
Input
グラフの頂点数 N
グラフの各辺の始点 init, 終点 end, 重み weight
無向グラフになるため, 始点と終点は交換可能.
Output
グラフの隣接リスト E
Time complexity
$ O(|E|)time.
最小全域木の計算
Input
なし
Output
最小全域木の辺のリスト edges
最小全域木の重み weight
Time complexity
$ O(|E|\log |V|)time.
code:python
from heapq import heapify, heappop, heappush
class Prim:
def __init__(self, N):
self.E = [[] for _ in range(N)]
def add_edge(self, init, end, weight):
self.Einit.append((end, weight)) self.Eend.append((init, weight)) def min_spanning_tree(self):
N, E = self.N, self.E
weight = 0; edges = [[] for _ in range(N)]
used = False * N; used0 = True; n_used = 1; heap = [(c, 0, v) for v, c in E0] # (cost, end1, end2) heapify(heap)
while heap and n_used < N:
c, u, v = heappop(heap)
usedv = True; n_used += 1; edges.append((u, v)); weight += c if not usedw: heappush(heap, (d, v, w)) return edges, weight
Verification
References
T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 『アルゴリズムイントロダクション 第3版』, 近代科学社, 2009.
R. E. Tarjan, 『新訳 データ構造とネットワークアルゴリズム』毎日コミュニケーションズ, 2008.
繁野麻衣子, 『ネットワーク最適化とアルゴリズム』, 朝倉書店, 2010.