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

概要

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

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

計算量

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

実装

# G[v] = [w, ...]
#     グラフG上で頂点vが隣接する辺集合

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)