Offensive Security Researcher & Quantum Cryptography Analyst

Minimum Spanning Tree Algorithm: Working, Explanation, and Implementation

Abdul Wahab Junaid
Minimum spanning tree algorithm and working of this algorithm

Minimum spanning tree algorithm and working of this algorithm

I want to explain this as one of the most practical and intuitive graph algorithms I know: given a connected, weighted, undirected graph, I want to find a subset of edges that connects all the vertices together, without any cycles, at the minimum possible total edge weight. That subset is called a Minimum Spanning Tree (MST). I find it useful to think of it as the cheapest possible way to “wire up” a network — whether that’s roads, power lines, or computer cables — so that every point is reachable from every other point.

History and Background

The problem has a rich, somewhat tangled history I find genuinely interesting. The earliest known algorithm was developed by the Czech mathematician Otakar Borůvka in 1926, motivated by the practical problem of efficiently constructing an electrical network in Moravia. Joseph Kruskal published his now-famous algorithm in 1956, and Robert Prim independently published his in 1957 (though it turns out a similar idea had actually already appeared in a 1930 paper by Vojtěch Jarník, so Prim’s algorithm is sometimes called the Prim–Jarník algorithm). All three approaches — Borůvka’s, Kruskal’s, and Prim’s — solve the same problem using fundamentally different strategies, and I think comparing them side by side is one of the best ways to understand greedy algorithm design in general.

Problem Statement

I define it as: given a connected, weighted, undirected graph $G = (V, E)$ with edge weights $w: E \to \mathbb{R}$, find a spanning tree $T \subseteq E$ (a subset of edges connecting all vertices without forming any cycle) such that the total weight $\sum_{e \in T} w(e)$ is minimized.

Core Concepts

How It Works

A. Kruskal’s algorithm:

  1. I sort all edges in the graph by weight, from smallest to largest.
  2. I initialize each vertex as its own separate component (using a Union-Find structure).
  3. I process edges in increasing order of weight: for each edge, if its two endpoints are in different components, I add the edge to the MST and merge the components; otherwise, I discard the edge (since adding it would create a cycle).
  4. I stop once I’ve added $|V|-1$ edges.

B. Prim’s algorithm:

  1. I pick an arbitrary starting vertex and add it to the “MST so far” set.
  2. I maintain a priority queue of all edges crossing from the current MST set to vertices outside it.
  3. I repeatedly extract the minimum-weight crossing edge, add its outside endpoint to the MST set, and add that vertex’s new crossing edges to the priority queue.
  4. I repeat until every vertex has been included in the MST set.

Working Principle

Both algorithms rely on the cut property I mentioned above: at every step, whatever set of vertices I’ve grouped together so far defines a “cut” separating them from the rest of the graph, and the minimum-weight edge crossing that cut is always safe to add to the MST without risking suboptimality later. Kruskal’s algorithm applies this idea globally, sorting all edges up front and greedily accepting any edge that doesn’t create a cycle. Prim’s algorithm applies it locally and incrementally, always growing a single connected component outward by picking the cheapest available edge leaving it. Despite this difference in perspective, both are provably guaranteed to arrive at a genuinely minimum spanning tree.

Mathematical Foundation

The total MST weight is:

$$ W(T) = \sum_{(u,v) \in T} w(u,v) $$

The cut property states: for any cut $(S, V \setminus S)$ of the graph, if edge $e = (u,v)$ with $u \in S, v \in V \setminus S$ has the minimum weight among all edges crossing the cut, then:

$$ e \in \text{some MST of } G $$

The cycle property states: for any cycle $C$ in the graph, if edge $e \in C$ has strictly the maximum weight among edges in $C$, then:

$$ e \notin \text{any MST of } G $$

Every spanning tree on $n$ vertices has exactly:

$$ |T| = n – 1 \text{ edges} $$

Diagrams

flowchart TD
    Start([Start: sort edges by weight - Kruskal]) --> Init[Initialize each vertex as its own set]
    Init --> Loop["For each edge (u,v) in sorted order"]
    Loop --> Cycle{Do u and v belong to different sets?}
    Cycle -- No, same set --> Discard[Discard edge - would form cycle]
    Cycle -- Yes --> Add[Add edge to MST, union the two sets]
    Discard --> More{More edges and MST not complete?}
    Add --> More
    More -- Yes --> Loop
    More -- No --> End([Return MST])

Pseudocode

Kruskal’s algorithm:

function Kruskal(Graph):
    MST = empty set
    sort edges of Graph by weight ascending
    for each vertex v:
        MakeSet(v)  // union-find initialization

    for each edge (u, v, weight) in sorted order:
        if Find(u) != Find(v):
            MST.add((u, v, weight))
            Union(u, v)
        if |MST| == |V| - 1:
            break

    return MST

Prim’s algorithm:

function Prim(Graph, start):
    MST = empty set
    visited = { start }
    Q = priority queue of edges from start, keyed by weight

    while |visited| < |V|:
        (u, v, weight) = Q.extractMin()  // cheapest edge with v not yet visited
        if v in visited:
            continue
        MST.add((u, v, weight))
        visited.add(v)
        for each edge (v, x, w2) where x not in visited:
            Q.insert((v, x, w2))

    return MST

Step-by-Step Example

Using the graph above: edges A-B(2), A-C(3), B-C(1), B-D(4), C-D(5), C-E(6), D-E(2).

Kruskal’s trace:

Final MST edges: B-C(1), A-B(2), D-E(2), B-D(4). Total weight = 1+2+2+4 = 9.

Time Complexity

All three achieve essentially the same asymptotic performance in practice, though constant factors and ease of implementation differ.

Space Complexity

Kruskal’s algorithm needs $O(V)$ space for the union-find structure and $O(E)$ space to store and sort the edge list, giving $O(V+E)$ overall. Prim’s algorithm needs $O(V)$ space for the visited set and $O(E)$ space for the priority queue (which can hold up to one entry per edge in the worst case), also giving $O(V+E)$ overall.

Correctness Analysis

Both algorithms’ correctness follows directly from the cut property. For Kruskal’s algorithm: when I consider edges in increasing weight order and add an edge that connects two previously separate components, that edge is, by construction, the minimum-weight edge crossing the cut defined by those two components at that point in the process — so by the cut property, it’s guaranteed to belong to some MST, and adding it can never prevent reaching an optimal solution. For Prim’s algorithm: at every step, the vertex set “visited so far” defines a cut, and I always select the minimum-weight edge crossing that cut — again directly satisfying the cut property. Because both algorithms only ever add edges justified by the cut property, and because they both produce exactly $|V|-1$ edges connecting all vertices without cycles (a valid spanning tree), the resulting tree is guaranteed to be of minimum total weight.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>
#include <stdlib.h>

#define V 5  // A=0, B=1, C=2, D=3, E=4
#define E 7

struct Edge {
    int src, dest, weight;
};

int parent[V], rank_[V];

int find(int i) {
    if (parent[i] != i)
        parent[i] = find(parent[i]);  // path compression
    return parent[i];
}

void unionSets(int a, int b) {
    int rootA = find(a), rootB = find(b);
    if (rootA == rootB) return;
    if (rank_[rootA] < rank_[rootB]) {
        parent[rootA] = rootB;
    } else if (rank_[rootA] > rank_[rootB]) {
        parent[rootB] = rootA;
    } else {
        parent[rootB] = rootA;
        rank_[rootA]++;
    }
}

int compareEdges(const void *a, const void *b) {
    return ((struct Edge *)a)->weight - ((struct Edge *)b)->weight;
}

void kruskalMST(struct Edge edges[]) {
    qsort(edges, E, sizeof(struct Edge), compareEdges);

    for (int v = 0; v < V; v++) {
        parent[v] = v;
        rank_[v] = 0;
    }

    int mstWeight = 0, edgeCount = 0;
    printf("Edges in the MST:\n");

    for (int i = 0; i < E && edgeCount < V - 1; i++) {
        int u = edges[i].src, v = edges[i].dest, w = edges[i].weight;
        if (find(u) != find(v)) {
            unionSets(u, v);
            printf("%d - %d : weight %d\n", u, v, w);
            mstWeight += w;
            edgeCount++;
        }
    }

    printf("Total MST weight: %d\n", mstWeight);
}

int main() {
    struct Edge edges[E] = {
        {0, 1, 2},  // A-B
        {0, 2, 3},  // A-C
        {1, 2, 1},  // B-C
        {1, 3, 4},  // B-D
        {2, 3, 5},  // C-D
        {2, 4, 6},  // C-E
        {3, 4, 2}   // D-E
    };

    kruskalMST(edges);
    return 0;
}

Sample Input and Output

Input: the 5-vertex, 7-edge graph defined above.

Output:

Edges in the MST:
1 - 2 : weight 1
0 - 1 : weight 2
3 - 4 : weight 2
1 - 3 : weight 4
Total MST weight: 9

This matches my manual Kruskal’s trace exactly — same edges, same total weight of 9.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version