最小全域木 (プリム法)
(Graph/SpanningTree/prim.py)

• View this file on GitHub
• Last update: 2022-01-20 17:35:30+09:00

概要

プリム法により最小全域木の総コストを求める。

使い方

prim(graph: Sequence[Iterable[Tuple[int, int]]]) -> int
隣接リストで表現される無向グラフ graph に対して、最小全域木の総コストを返す。計算量 $O((V + E)\log V)$

Verified with

• TestCase/AOJ/GRL_2_A.prim.test.py

Code

# from heapq import heappop, heappush
from standard_library.heapq import heappop, heappush


def prim(graph):
    res = 0
    used = [False] * len(graph)
    hq = [(0, 0)]  # hq = [(辺のコスト, 現在地)]
    while hq:
        cost, v = heappop(hq)
        if used[v]:
            continue
        used[v] = True
        res += cost
        for nxt_v, cost in graph[v]:
            heappush(hq, (cost, nxt_v))
    return res

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page