クラスカル法 (Kruskal’s Algorithm)

概要

グラフ \(G\) 上の最小全域木(Minimum Spanning Tree)を求める。

クラスカル法では、コストが小さい辺から、連結でない頂点同士を繋いでいくことで、最小全域木を求める。

計算量

\(O(|E| \log |V|)\)

実装

# N: 頂点数
# E = [(cost, v, w), ...]
#   G上の全ての辺(v, w)とそのcostを含むlist
N = ...
E = [...]

# Union-Findを使うことで頂点間の連結判定を行う
*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
 
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
    else:
        p[px] = py
    return 1
 
E.sort()
ans = 0
for c, v, w in E:
    if unite(v, w):
        ans += c

# ansが最小全域木の解

Verified

  • AOJ: "ALDS1_12_A: Graph II - Minimum Spanning Tree": source (Python3, 0.02sec)

戻る