Day 007-Q3 | 最小全域木 Prim

問題

$N$ 頂点 $M$ 辺の重み付き無向グラフが与えられる。頂点 1 を起点として Prim 法で最小全域木を構築し、そのコストを出力せよ。非連結なら -1。

制約

$2 \le N \le 5\times10^5$

$1 \le M \le 10^6$

$1 \le u_i, v_i \le N$

$1 \le w_i \le 10^9$

入出力例

入力例 1

出力例 1

ヒント (段階的開示)

ヒント1: 方向性

Kruskal が「辺」を主役にするのに対し、Prim は「頂点」を主役にして木を少しずつ拡張する。

ヒント2: アプローチ

木に属する頂点集合 $S$ と、$S$ に隣接する辺の中で最小コストの辺を優先度付きキューで管理する。

ヒント3: 誘導

heap = [(0, 0)]
while heap:
    cost, v = heapq.heappop(heap)
    if visited[v]: continue
    visited[v] = True
    total += cost
    for next_v, w in graph[v]:
        if not visited[next_v]:
            heapq.heappush(heap, (w, next_v))

模範解答 (Python)

import sys
import heapq
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        u, v, w = map(int, input().split())
        u -= 1; v -= 1
        graph[u].append((v, w))
        graph[v].append((u, w))

    visited = [False] * N
    heap = [(0, 0)]
    total = 0
    count = 0

    while heap and count < N:
        cost, v = heapq.heappop(heap)
        if visited[v]:
            continue
        visited[v] = True
        total += cost
        count += 1
        for next_v, w in graph[v]:
            if not visited[next_v]:
                heapq.heappush(heap, (w, next_v))

    print(total if count == N else -1)

main()

Step-by-Step 解説

1Prim のアイデア
ダイクストラ法と非常に似た構造。「木から最も近い頂点を貪欲に追加する」。

2優先度付きキュー
木に隣接する辺をヒープで管理し、常に最小コストの辺を $O(\log M)$ で取り出す。

3訪問済みチェック
ヒープに古い辺が残るため、pop 後に if visited[v]: continue。

4Kruskal との使い分け
Kruskal: 疎グラフ向き、Prim: 密グラフ向き。

よくあるミス

ミス	原因	正しい書き方
無向グラフなのに片方向だけ追加	辺の追加を忘れる	`graph[u].append`, `graph[v].append` 両方
初期コストを忘れる	ヒープに `(0, 0)` を入れ忘れ	頂点0のコスト0で初期化
非連結の `-1` 出力忘れ	`count == N` チェック漏れ	最後に確認

次のステップ

発展問題: 辺に「使用できる辺数の上限」が設定された状況での最小全域木

自己評価

完全理解おおむね理解要復習

Day 007-Q3 — 最小全域木 Prim

問題

制約