Minimum Spanning Tree

Graph (V=4, E=5):
  A -1- B
  |   / |
  4  2  3
  | /   |
  C -5- D

All spanning trees connect A,B,C,D with 3 edges.
MST picks the minimum-weight set:
  A-B (1), B-C (2), B-D (3)  → total = 6

Applications: network cable layout, road construction,
cluster analysis, approximation algorithms for TSP.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank   = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False          # already in same component — would form cycle
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx       # union by rank: attach smaller tree under larger
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

uf = UnionFind(4)    # 4 nodes: 0,1,2,3
uf.union(0, 1)
uf.union(1, 2)
print(uf.find(0) == uf.find(2))   # True — connected
print(uf.find(0) == uf.find(3))   # False — not connected

def kruskal(vertices, edges):
    """
    vertices: list of vertex labels
    edges: list of (weight, u, v)
    Returns (mst_edges, total_weight)
    """
    v_to_idx = {v: i for i, v in enumerate(vertices)}
    uf       = UnionFind(len(vertices))
    mst      = []
    total    = 0

    for w, u, v in sorted(edges):           # sort by weight
        ui, vi = v_to_idx[u], v_to_idx[v]
        if uf.union(ui, vi):                # no cycle → include edge
            mst.append((u, v, w))
            total += w
            if len(mst) == len(vertices) - 1:
                break                       # MST complete (V-1 edges)

    return mst, total

vertices = ["A", "B", "C", "D"]
edges    = [(1,"A","B"), (4,"A","C"), (2,"B","C"), (3,"B","D"), (5,"C","D")]
mst, cost = kruskal(vertices, edges)
print(mst)    # [('A', 'B', 1), ('B', 'C', 2), ('B', 'D', 3)]
print(cost)   # 6

import heapq
from collections import defaultdict

def prim(graph, start):
    """
    graph: adjacency list {u: [(v, weight), ...]}
    Returns (mst_edges, total_weight)
    """
    in_mst  = {start}
    heap    = [(w, start, v) for v, w in graph[start]]
    heapq.heapify(heap)
    mst     = []
    total   = 0

    while heap and len(in_mst) < len(graph):
        w, u, v = heapq.heappop(heap)
        if v in in_mst:
            continue                     # vertex already in MST
        in_mst.add(v)
        mst.append((u, v, w))
        total += w
        for nb, weight in graph[v]:
            if nb not in in_mst:
                heapq.heappush(heap, (weight, v, nb))

    return mst, total

g = defaultdict(list)
for w, u, v in [(1,"A","B"),(4,"A","C"),(2,"B","C"),(3,"B","D"),(5,"C","D")]:
    g[u].append((v, w))
    g[v].append((u, w))

mst, cost = prim(g, "A")
print(mst)    # [('A', 'B', 1), ('B', 'C', 2), ('B', 'D', 3)]
print(cost)   # 6