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

概要

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

プリム法では、グラフ \(G\) の1頂点からなる木から始め、 木に含まれる頂点と木に含まれない頂点を繋ぐ辺のうち、一番コストが小さい辺が繋ぐ(木に含まれない方の)頂点を木に追加する、 ことを繰り返すことで最小全域木を求める。

計算量

Priority Queueを使うことで \(O(|E| \log |V|)\)

実装

# N: 頂点数
# G[v] = [w, ...]
#     グラフG上で頂点vが隣接する辺集合
N = ...
G = [[...] for i in range(N)]

from heapq import heappush, heappop, heapify
used = [0]*N
que = [(c, w) for w, c in G[0]]
used[0] = 1
heapify(que)
 
ans = 0
while que:
    cv, v = heappop(que)
    if used[v]:
        continue
    used[v] = 1
    ans += cv
    for w, c in G[v]:
        if used[w]:
            continue
        heappush(que, (c, w))

# ansが最小全域木の解

Verified

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

戻る