Minimum Spanning Tree (MST) — Prim's, Kruskal's and Borůvka's Algorithms (Interactive Simulator)

The Story — Connecting Villages With Fibre Cable

A spanning tree of a connected graph uses all the nodes and just enough edges to connect them, with no cycles. If there are V nodes, a spanning tree always has exactly V − 1 edges. The minimum spanning tree is the one with the smallest total edge weight.

The Three Algorithms at a Glance

Watch Them Build — Prim vs Kruskal

Same graph, same answer (total = 39). Watch how they build it. Prim's green tree grows from A. Kruskal's colours show separate groups that merge. A red dotted edge was rejected because it would make a cycle.

The MST Simulator — Build Your Own Graph

Draw nodes and weighted edges. Pick Prim's, Kruskal's or Borůvka's. Each click on Step runs one line. Watch the priority queue, the sorted edge list, or the component list change. The Union-Find table shows each node's parent. You can also build your own tree and check it against the real MST.

Union-Find Playground — The Engine Inside Kruskal

Kruskal asks one question again and again: "Are u and v already in the same group?" A Union-Find (also called Disjoint Set) answers it almost instantly. Each node points to a parent. Follow the parents up to the root. Two nodes with the same root are in the same set.

Step-by-Step Traces on the Classic Graph

Edges: A–B 7, A–D 5, B–C 8, B–D 9, B–E 7, C–E 5, D–E 15, D–F 6, E–F 8, E–G 9, F–G 11.

Prim's (start at A)

Kruskal's (edges sorted by weight)

Borůvka's

Python Implementation

# Shared graph for all three examples
edges = [('A','B',7), ('A','D',5), ('B','C',8), ('B','D',9), ('B','E',7), ('C','E',5),
         ('D','E',15), ('D','F',6), ('E','F',8), ('E','G',9), ('F','G',11)]
nodes = ['A', 'B', 'C', 'D', 'E', 'F', 'G']

graph = {n: [] for n in nodes}          # adjacency list
for u, v, w in edges:
    graph[u].append((v, w))
    graph[v].append((u, w))

1. Prim's Algorithm (heapq)

import heapq

def prim(graph, start):
    in_tree = {start}
    pq = [(w, start, v) for v, w in graph[start]]
    heapq.heapify(pq)
    mst, total = [], 0
    while pq and len(in_tree) < len(graph):
        w, u, v = heapq.heappop(pq)         # cheapest edge
        if v in in_tree:
            continue                           # stale: would make a cycle
        in_tree.add(v)
        mst.append((u, v, w))
        total += w
        for x, wx in graph[v]:              # new edges leaving the tree
            if x not in in_tree:
                heapq.heappush(pq, (wx, v, x))
    return mst, total

mst, total = prim(graph, 'A')
print("MST edges:", mst)
print("Total weight:", total)

2. Union-Find + Kruskal's Algorithm

class DSU:
    def __init__(self, items):
        self.parent = {x: x for x in items}   # each node is its own set
        self.rank = {x: 0 for x in items}

    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, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                     # same set: cycle!
        if self.rank[ra] < self.rank[rb]:    # union by rank
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

def kruskal(nodes, edges):
    dsu = DSU(nodes)
    mst, total = [], 0
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        if dsu.union(u, v):
            mst.append((u, v, w))
            total += w
            print(f"  take   {u}-{v} ({w})")
        else:
            print(f"  reject {u}-{v} ({w})  -> would make a cycle")
        if len(mst) == len(nodes) - 1:
            break                            # V - 1 edges: done
    return mst, total

mst, total = kruskal(nodes, edges)
print("Total weight:", total)

3. Borůvka's Algorithm

def boruvka(nodes, edges):
    dsu = DSU(nodes)
    mst, total, rnd = [], 0, 0
    comps = len(nodes)
    while comps > 1:
        rnd += 1
        cheapest = {}                          # root -> best edge
        for i, (u, v, w) in enumerate(edges):
            ru, rv = dsu.find(u), dsu.find(v)
            if ru == rv:
                continue                       # inside one component
            for r in (ru, rv):
                # tie-break by (weight, index) to avoid cycles
                if r not in cheapest or (w, i) < (cheapest[r][2], cheapest[r][3]):
                    cheapest[r] = (u, v, w, i)
        if not cheapest:
            break                              # graph is not connected
        added = []
        for u, v, w, i in cheapest.values():
            if dsu.union(u, v):              # may be chosen twice
                mst.append((u, v, w))
                total += w
                comps -= 1
                added.append(f"{u}-{v}({w})")
        print(f"  Round {rnd}: added {added}, components left = {comps}")
    return mst, total

mst, total = boruvka(nodes, edges)
print("Total weight:", total)

Prim vs Kruskal vs Borůvka

V = number of nodes. E = number of edges.

Where MSTs Are Used

Golden Rules