Minimum Spanning Tree

A Minimum Spanning Tree (MST) is a subset of edges that connects all vertices with the minimum total weight, without any cycles.

Concept

Graph:        MST:
A --1-- B     A --1-- B
|       |     |       |
4       2     4       2
|       |     |       |
C --3-- D     C       D

MST: A-B (1), B-D (2), A-C (4) = total 7

Kruskal's Algorithm

Sorts edges by weight, then adds the smallest edge if it does not form a cycle. It uses Union-Find.

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])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

def kruskal(n, edges):
    edges.sort(key=lambda x: x[2])  # Sort by weight
    uf = UnionFind(n)
    mst = []
    total = 0

    for u, v, w in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
            total += w
            if len(mst) == n - 1:
                break

    return mst, total

Prim's Algorithm

Starts from a single vertex and keeps adding the smallest edge that connects a vertex in the MST with a vertex outside the MST. It uses a Priority Queue.

import heapq

def prim(graph, start=0):
    n = len(graph)
    visited = [False] * n
    mst = []
    total = 0
    pq = [(0, start, -1)]

    while pq and len(mst) < n - 1:
        weight, u, prev = heapq.heappop(pq)

        if visited[u]:
            continue
        visited[u] = True

        if prev != -1:
            mst.append((prev, u, weight))
            total += weight

        for v, w in graph[u]:
            if not visited[v]:
                heapq.heappush(pq, (w, v, u))

    return mst, total

Kruskal vs Prim Comparison

Example

# Edges: (u, v, weight)
edges = [
    (0, 1, 4), (0, 2, 2), (1, 2, 1),
    (1, 3, 5), (2, 3, 8)
]

mst, total = kruskal(4, edges)
print(mst)    # [(1, 2, 1), (0, 2, 2), (0, 1, 4)] or similar
print(total)  # 7

Applications

• Network design: Cables/pipes at minimum cost.
• Clustering: Hierarchical clustering.
• Approximation algorithms: Traveling salesman.
• Image segmentation: Graph-based methods.

An MST connects all vertices. Big O Notation formally describes algorithmic complexity.