Kruskal法
Abstract
Kruskal法は, 辺重み$ wが与えられたネットワーク$ \mathcal{N} = \left((V, E), w \right)に対する最小全域木問題を解くためのアルゴリズム. Union-Findを利用することで, $ 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
class Kruskal:
def __init__(self, N):
self.E = []
def add_edge(self, init, end, weight):
self.E.append((weight, init, end))
def min_spanning_tree(self):
N, E = self.N, self.E
weight = 0; edges = []
n_edges = 0
uf = UnionFind(N) # for judging connectivity
E = sorted(E)
for w, a, b in E:
if uf.union(a, b):
edges.append((a, b))
n_edges += 1; weight += w
if n_edges == N - 1: break
return edges, weight
Verification
References
T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 『アルゴリズムイントロダクション 第3版』, 近代科学社, 2009.
R. E. Tarjan, 『新訳 データ構造とネットワークアルゴリズム』毎日コミュニケーションズ, 2008.
繁野麻衣子, 『ネットワーク最適化とアルゴリズム』, 朝倉書店, 2010.