Minimum Spanning Tree Construction

Minimum spanning tree connects all vertices with minimum total edge weight—Kruskal sorts edges; Prim grows from a seed with a priority queue.

Why this shows up in the real world

Maps & routing, social networks, and dependency systems are modeled as graphs—vertices are places or tasks, edges are roads or prerequisites.

Core idea (explained for students)

Cut property: lightest edge crossing a cut is safe. Kruskal + Union-Find skips cycles. Prim similar to Dijkstra on tree growth.

Try this in Python

class UnionFind:
    def __init__(self, n: int) -> None:
        self.p = list(range(n))
        self.r = [0] * n

    def find(self, x: int) -> int:
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]
            x = self.p[x]
        return x

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.r[ra] < self.r[rb]:
            ra, rb = rb, ra
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]:
            self.r[ra] += 1
        return True


uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
print(uf.find(0), uf.find(3))

Common mistakes

• Building MST on disconnected graph (forest, not tree).
• Forgetting to sort edges in Kruskal.

Key takeaways

• MST weight is baseline for many approximations.
• Unique MST when all weights distinct.