Kruskal
コードについての説明
グラフの最小全域木の重みを求めるアルゴリズム.
最小全域木とはもとのグラフの部分グラフでありかつすべての頂点を含む木のなかで辺の重みの総和が最小のもののことである. 同じく最小全域木を求めるアルゴリズムとして Prim 法 がある.
コストの小さい辺から(閉路ができないように)貪欲に取っていくことでアルゴリズムが正しく動くことが知られている. 証明はグラフ, マトロイドの両面から示せる.
グラフの側面から示した証明はよくあるので, マトロイドの側面から Kruskal 法の正当性を示してみた(⇒ 補足).
(関数)
add_edge$(u, v, cost)$ : $u$, $v$ の間に重み $cost$ の無向辺を追加する
solve(): 最小全域木の重みを計算する
時間計算量: $\O (m \log n)$
コード
class UnionFind:
def __init__(self, node_size):
self._node = node_size
self.par = [i for i in range(self._node)]
self.rank = [0] * self._node
def find(self, ver):
if self.par[ver] == ver:
return ver
else:
self.par[ver] = self.find(self.par[ver])
return self.par[ver]
def unite(self, ver1, ver2):
ver1, ver2 = self.find(ver1), self.find(ver2)
if ver1 == ver2:
return
if self.rank[ver1] < self.rank[ver2]:
ver1, ver2 = ver2, ver1
self.par[ver2] = ver1
if self.rank[ver1] == self.rank[ver2]:
self.rank[ver1] += 1
def same(self, ver1, ver2):
return self.find(ver1) == self.find(ver2)
class Kruskal:
class Edge:
def __init__(self, u, v, cost):
self.u, self.v, self.cost = u, v, cost
def __lt__(self, another):
return self.cost < another.cost
def __init__(self, node_size):
self._node = node_size
self._edge_list = []
def add_edge(self, u, v, cost):
self._edge_list.append(self.Edge(u, v, cost))
def solve(self):
uf = UnionFind(self._node)
res = 0
edge_count = 0
self._edge_list.sort()
for e in self._edge_list:
if not uf.same(e.u, e.v):
uf.unite(e.u, e.v)
res += e.cost
edge_count += 1
if edge_count == self._node-1:
break
return res
verify 用の問題
AOJ : Minimum Spanning Tree 提出コード