クラスカル法（Kruskal’s Algorithm）とは
クラスカル法とは、
です。
最小全域木とは、すべての頂点を含み、辺の重みの合計が最小となるグラフのことです。
以下の例では、最小全域木はこのように辺が選択されます。
クラスカル法は、辺をコストの小さい順に選択していき、閉路（サイクル）が生じないように最小全域木を構築していきます。
辺のコストをソートするので、計算量はO（E log E）となります。
Eは辺の数を表しています。
他にも最小全域木を求める方法は、 プリム法などがあります。
アルゴリズムの概要
1. 全ての辺をソート
全ての辺をコストの昇順にソートします。
ソート結果は以下のようになりました。
B-E間(3), A-D間(5), C-F間(7), E-F間(7), B-C間(10), D-E間(10), A-E間(11), C-E間(15), A-B間(20)
2. 辺を順に取り出し、頂点を連結する
まず、一番コストの小さいB-E間(3)が取り出されます。
頂点Bと頂点Eは連結されていないので、B-E間(3)の辺でつなぎます。
3. 全ての頂点が連結するまで繰り返す
全頂点が連結済みになるまで、「2. 辺を順に取り出し、頂点を連結する」を繰り返します。
実装(Python)
クラスカル法をpythonで実装した例です。
実装にはUnion-Findを使用しています。
from collections import defaultdict
class UnionFind:
def __init__(self, n):
self.parent = defaultdict(lambda: -1)
self.rank = defaultdict(int)
def is_root(self, node):
return self.parent[node] == -1
def find(self, node):
while not self.is_root(node):
node = self.parent[node] # 経路圧縮
return node
def union(self, node1, node2):
root1 = self.find(node1)
root2 = self.find(node2)
if root1 == root2:
return
if self.rank[root1] < self.rank[root2]:
smaller, bigger = root1, root2
else:
smaller, bigger = root2, root1
self.parent[smaller] = bigger
self.rank[bigger] = max(self.rank[bigger], self.rank[smaller] + 1)
def kruskal(n, edges):
edges.sort(key=lambda x: x[2]) # 辺の重みでソート
uf = UnionFind(n)
mst = []
for u, v, weight in edges:
if uf.find(u) != uf.find(v): # 違うグループのときに追加
uf.union(u, v)
mst.append((u, v, weight))
return mst実行してみます。
# 使用例（頂点数 6, 辺リスト [(頂点1, 頂点2, 重み)]）
n = 6
graph = [('A', 'B', 20), ('A', 'D', 5), ('A', 'E', 11),
('B', 'C', 10), ('B', 'E', 3),
('C', 'E', 15), ('C', 'F', 7),
('D', 'E', 10), ('E', 'F', 7)]
mst = kruskal(n, graph)
print("最小全域木:", mst) # 最小全域木の辺一覧最小全域木: [('B', 'E', 3), ('A', 'D', 5), ('C', 'F', 7), ('E', 'F', 7), ('D', 'E', 10)]
参考文献
コメント