kruskal
(byslib/graph/kruskal.py)

• View this file on GitHub
• Last update: 2022-04-18 22:29:22+09:00

Verified with

• tests/graph/kruskal.test.py

Code

# @title kruskal
from typing import List, Tuple

from ..data.union_find import UnionFindTree
from .edge import Edge


def kruskal(edges: List[Edge], n_node: int) -> Tuple[int, List[Edge]]:
    """Kruskal

    Parameters
    ----------
    edges
        List of Edges
    n_node
        Node size

    Returns
    -------
    Minimum (cost, Tree)

    Notes
    -----
    Time complexity

    O(E log(E))

    References
    ----------
    ..[1] 🐜 p.99
    """

    edges.sort()
    uft = UnionFindTree(n_node)
    mst: List[Edge] = []
    cost = 0
    for e in edges:
        if uft.union(e.src, e.dest):
            cost += e.weight
            mst.append(e)
    return cost, mst

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.4/x64/lib/python3.10/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], 'release': True}).decode()
  File "/opt/hostedtoolcache/Python/3.10.4/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/python.py", line 80, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page