Minimum spanning tree (MST)

Given a connected, undirected graph with non‑negative edge weights (typical textbook setup), a minimum spanning tree is a spanning tree whose total edge weight is as small as possible. If the graph is disconnected, each connected component has its own MST and together they form a minimum spanning forest.

1) Definition

A spanning tree of G = (V, E) uses |V| − 1 edges, connects every vertex, and has no cycles. Among all spanning trees, an MST minimizes Σ weight(e) over selected edges. With distinct edge weights the MST is unique; with ties there may be several optimal trees with the same total weight.

2) Cut property (idea)

Partition vertices into two non‑empty sets S and V \ S. Among all edges crossing the cut, every lightest crossing edge belongs to some MST. Greedy MST algorithms repeatedly add such safe edges—Kruskal picks globally cheapest edges that do not form a cycle; Prim always grows one tree using the cheapest edge from the current vertex set to the outside.

3) Prim vs Kruskal

• Prim: Start from an arbitrary root. Maintain the tree’s frontier; repeatedly attach the minimum‑weight edge from a vertex already in the tree to a vertex not yet in the tree (priority queue / min‑heap when using adjacency lists). Natural when the graph is dense or you stream from one source region.
• Kruskal: Sort all edges by weight ascending. Scan in order and accept an edge if its endpoints lie in different connected components (union–find); otherwise skip it (would close a cycle). Natural when edges are given as a list or E is moderate.

See Prim's algorithm and Kruskal's algorithm for full implementations (heap vs sorted edges + DSU).

4) Example graph (for traces below)

Vertices 0 … 3. Undirected edges (weight in parentheses):

Vertices 0 … 3. All six edges of K4 with weights:

  0–1 : 1     2–3 : 2     0–3 : 3     1–2 : 4     0–2 : 5     1–3 : 6

Kruskal scan (sorted): 0–1, 2–3, 0–3, ··· — the first three are acyclic and connect
the graph; every later edge has both endpoints already in one component.

5) C — Kruskal with union–find

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

typedef struct { int u, v, w; } Edge;

static int cmp_edge(const void *a, const void *b) {
    Edge *ea = (Edge*)a, *eb = (Edge*)b;
    return ea->w - eb->w;
}

enum { V = 4 };
static int dsu[V];

static int dsu_find(int x) {
    while (dsu[x] != x) x = dsu[x];
    return x;
}

static void dsu_union(int a, int b) {
    a = dsu_find(a); b = dsu_find(b);
    if (a != b) dsu[b] = a;   /* tie-break: attach b's root under a */
}

int main(void) {
    Edge edges[] = {
        {0,1,1}, {2,3,2}, {0,3,3},
        {1,2,4}, {0,2,5}, {1,3,6}
    };
    int E = (int)(sizeof edges / sizeof edges[0]);
    qsort(edges, E, sizeof(Edge), cmp_edge);

    for (int i = 0; i < V; i++) dsu[i] = i;

    long long total = 0;
    int taken = 0;
    for (int i = 0; i < E && taken < V - 1; i++) {
        int u = edges[i].u, v = edges[i].v;
        if (dsu_find(u) != dsu_find(v)) {
            dsu_union(u, v);
            total += edges[i].w;
            taken++;
            printf("take (%d,%d) w=%d\n", u, v, edges[i].w);
        }
    }
    printf("MST total weight %lld\n", total);
    return 0;
}

6) Complexity

• Kruskal: O(E log E) or O(E log V) for sorting edges (union–find with union by rank / path compression is nearly constant amortized per operation).
• Prim (binary heap): O(E log V) with adjacency lists; O(V²) with an array for dense graphs.
• Space: O(V + E) for the graph plus auxiliary structures.

7) Trace — Kruskal on the example

8) Trace — Prim starting at vertex 0

Greedy attachment by cheapest edge from the growing vertex set S to V \ S (ties broken arbitrarily).