最小全域木 (クラスカル法)
(Graph/SpanningTree/kruskal.py)

• View this file on GitHub
• Last update: 2022-01-22 12:11:49+09:00

概要

クラスカル法により最小全域木の総コストを求める。

使い方

kruskal(n: int, edges: Iterable[Tuple[int, int, int]]) -> int
頂点数 n の無向グラフ $G=(V, E)$ に対して、重み付き辺集合 edges から構成される最小全域木の総コストを返す。計算量 $O(E\log V)$

Depends on

• Union Find (DataStructure/UnionFind/UnionFind.py)

Verified with

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

Code

#from operator import itemgetter
from standard_library.operator import itemgetter
from DataStructure.UnionFind.UnionFind import UnionFind


def kruskal(n, edges):
    edges = sorted(edges, key=itemgetter(2))
    uf = UnionFind(n)
    res = 0
    for u, v, cost in edges:
        if not uf.same(u, v):
            uf.merge(u, v)
            res += cost
    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