Prim and Kruskal

The Minimum Spanning Tree exists if and only if the graph is connected.

Interface

class UnionFind(num_item)

__init__(num_item) → None

find(x: int) → int

Path compression.

union(x: int, y: int) → None

Union by rank.

class MinHeap(item_list: list[int] | None = None)

__init__(item_list: list[int] | None = None) → None

Initialize an minimum heap.

push(item: int) → None

pop() → int

class Edge(v: int, w: int, weight: int | float)

For kruskal.

__init__(v: int, w: int, weight: int | float) → None

__lt__(other: Edge) → bool

Return self<value.

class AdjVNode(vertex: int, weight: int | float = inf)

__init__(vertex: int, weight: int | float = inf) → None

__lt__(other: AdjVNode) → bool

Implementation of operation <.

class LGraph(num_vertex: int)

Adjacency list Graph.

__init__(num_vertex: int) → None

join(v: int, w: int, weight: int | float = inf) → None

prim() → list

kruskal()

test_union_find() → None

test_graph() → None

test_heap() → None