Minimum Spanning Tree Explained (Prim's and Kruskal's)

Imagine you're wiring electricity to a set of towns and you want every town connected to the grid, using the least total cable possible, with no redundant loops. That's exactly the problem a Minimum Spanning Tree (MST) solves: given a connected, weighted, undirected graph, find the subset of edges that connects every vertex together with the smallest possible total edge weight.

A "spanning tree" by itself just means a subgraph that touches every vertex using exactly V−1 edges and contains no cycles (any fewer edges and some vertex would be disconnected; any more and you'd necessarily create a loop). Out of all the possible spanning trees a graph could have, the minimum one is the cheapest.

Prim's Algorithm

Prim's algorithm grows the MST one vertex at a time, starting from an arbitrary node. At each step, it looks at every edge connecting the tree built so far to a vertex not yet in the tree, and greedily adds the cheapest one. This continues until every vertex has been pulled in.

import heapq

def prims_mst(graph, start):
    # graph: {node: [(neighbor, weight), ...]}
    visited = {start}
    edges = [(w, start, v) for v, w in graph[start]]
    heapq.heapify(edges)
    mst = []

    while edges and len(visited) < len(graph):
        weight, u, v = heapq.heappop(edges)
        if v in visited:
            continue
        visited.add(v)
        mst.append((u, v, weight))
        for neighbor, w in graph[v]:
            if neighbor not in visited:
                heapq.heappush(edges, (w, v, neighbor))

    return mst

graph = {
    "A": [("B", 2), ("C", 3)],
    "B": [("A", 2), ("C", 1), ("D", 4)],
    "C": [("A", 3), ("B", 1), ("D", 5)],
    "D": [("B", 4), ("C", 5)],
}

print(prims_mst(graph, "A"))

Output:

[('A', 'B', 2), ('B', 'C', 1), ('B', 'D', 4)]

Because Prim's always picks from edges touching the growing tree, it behaves a lot like Dijkstra's shortest-path algorithm — same priority-queue machinery, different goal (cheapest connecting edge vs cheapest cumulative distance).

Kruskal's Algorithm

Kruskal's algorithm takes a completely different angle: instead of growing outward from one vertex, it looks at the whole graph's edges at once. Sort every edge by weight, then walk through them from cheapest to most expensive, adding an edge to the MST only if it doesn't create a cycle with what's already been added. A Union-Find (Disjoint Set) data structure is the standard tool for cheaply checking "would this edge create a cycle?"

def find(parent, i):
    while parent[i] != i:
        i = parent[i]
    return i

def kruskals_mst(vertices, edges):
    # edges: [(weight, u, v), ...]
    edges = sorted(edges)
    parent = {v: v for v in vertices}
    mst = []

    for weight, u, v in edges:
        root_u, root_v = find(parent, u), find(parent, v)
        if root_u != root_v:
            parent[root_u] = root_v
            mst.append((u, v, weight))

    return mst

vertices = ["A", "B", "C", "D"]
edges = [(2, "A", "B"), (3, "A", "C"), (1, "B", "C"), (4, "B", "D"), (5, "C", "D")]

print(kruskals_mst(vertices, edges))

Output:

[('B', 'C', 1), ('A', 'B', 2), ('B', 'D', 4)]

Prim's vs Kruskal's: Which to Use

Both produce an MST of the same total weight (though the exact edges chosen can differ when there are ties), and both run in roughly O(E log V) time. Prim's tends to be a better fit for dense graphs (lots of edges relative to vertices) since it only ever looks at edges touching the current tree. Kruskal's tends to be simpler to reason about and works well on sparse graphs, since sorting all edges up front is cheap when there aren't many of them.