Prim, Kruskal and disjoint set union

A spanning tree connects all vertices without cycles using V−1 edges. MST minimises total tree weight, not every root-to-vertex distance. Disconnected graphs yield spanning forests; negative weights are allowed.

The cut property justifies a cheapest crossing edge. Prim grows one tree through its cheapest crossing edge; Kruskal sorts edges and joins distinct components. Equal weights can produce multiple valid MSTs.

DSU supplies find and union. Path compression plus union by rank/size gives amortised O(α(n)) over operation sequences, not literally constant complexity. Arbitrary deletion needs different machinery; rollback DSU uses different compression policies.

class DSU:
    def __init__(self, n): self.p=list(range(n)); self.size=[1]*n
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]; x = self.p[x]
        return x
    def union(self, a, b):
        a,b = self.find(a), self.find(b)
        if a == b: return False
        if self.size[a] < self.size[b]: a,b=b,a
        self.p[b]=a; self.size[a]+=self.size[b]
        return True
d=DSU(3)
assert d.union(0,1) and d.union(1,2) and not d.union(0,2)