Minimum spanning trees

Overview

A minimum spanning tree connects every vertex of a weighted undirected graph using a subset of edges with the least possible total weight. Prim's algorithm grows the tree outward: repeatedly add the cheapest edge that connects a new vertex to the tree. If at some point no edge reaches a still-outside vertex, the graph is disconnected and no spanning tree exists.

Why it matters

MSTs minimise the cost to connect everything: laying cable or pipe, designing networks, clustering data, approximating hard tour problems. Prim's growth strategy is also a clean template for greedy algorithms in general.

Core concepts

Prim's growth. Maintain a key[] = cheapest known edge into the tree for each outside vertex; add the minimum, then update its neighbours' keys.

Disconnection. If the minimum key is ∞, some vertex is unreachable → return 'no MST'.

Connectivity. Whether an undirected graph is connected at all is just one DFS/BFS reaching every vertex.

Prim vs Kruskal. Prim grows one tree; Kruskal sorts edges and unions components — both give the same total weight.

Syntax notes

#include <stdlib.h>

/* Prim: grow one tree, always adding the cheapest edge to a new vertex.
   Symmetric w[]; 0 = no edge. Returns -1 if the graph is disconnected. */
long mst_weight(const int *w, int n) {
    if (n <= 0) return 0;
    const long INF = 1000000000L;
    long *key = malloc((size_t)n * sizeof *key);
    int  *in  = calloc((size_t)n, sizeof *in);
    if (!key || !in) { free(key); free(in); return -1; }
    for (int i = 0; i < n; i++) key[i] = INF;
    key[0] = 0;
    long total = 0;
    for (int it = 0; it < n; it++) {
        int u = -1; long best = INF;
        for (int i = 0; i < n; i++)
            if (!in[i] && key[i] < best) { best = key[i]; u = i; }
        if (u < 0) { free(key); free(in); return -1; }   /* DISCONNECTED */
        in[u] = 1; total += key[u];
        for (int v = 0; v < n; v++) {
            int e = w[u*n + v];
            if (e > 0 && !in[v] && e < key[v]) key[v] = e;   /* edge weight, NOT a path cost */
        }
    }
    free(key); free(in);
    return total;
}

Key points:

• key[v] is the weight of the single cheapest edge into the tree — not a cumulative distance. That one difference is what separates Prim from Dijkstra.
• u < 0 with vertices still outside the tree means the graph is disconnected.
• key[0] = 0 seeds the tree at vertex 0; any start vertex gives the same total weight.

Lesson

A minimum spanning tree connects every vertex of a weighted undirected graph using edges of least total weight. Prim's algorithm grows a tree, always adding the cheapest edge that reaches a new vertex; if no such edge remains while vertices are still outside, the graph is disconnected and has no spanning tree. Connectivity itself is just a single traversal.

Code examples

#include <stdio.h> int main(void){ int n=4; /* undirected weighted (symmetric) */ int w[16]={ 0,1,3,0, 1,0,1,4, 3,1,0,1, 0,4,1,0 }; long INF=1000000000L, key[4]; int in[4]={0}; long total=0; for(int i=0;i<n;i++) key[i]=INF; key[0]=0; for(int it=0;it<n;it++){ int u=-1; long best=INF; for(int i=0;i<n;i++) if(!in[i]&&key[i]<best){best=key[i];u=i;} in[u]=1; total+=key[u]; for(int v=0;v<n;v++){ int e=w[u*n+v]; if(e>0&&!in[v]&&e<key[v]) key[v]=e; } } printf("MST total weight = %ld\n", total); return 0; }

Line by line

Common mistakes

Not detecting disconnection (an unreachable vertex). Re-adding an edge to a vertex already in the tree. Treating weight 0 as an edge. Assuming the graph is connected without checking.

Debugging tips

Compiler errors and warnings:

• -Wsign-compare mixing int weights with long accumulators.
• Nothing warns if you accidentally implement Dijkstra.

Runtime symptoms:

• You computed shortest paths, not an MST. The update used key[u] + e instead of e. Prim compares edge weights alone.
• A disconnected graph returns a plausible number. The u < 0 check is missing, so the loop silently stops early. It must return the "no MST" signal.
• Total is too small on an undirected graph. You treated the matrix as directed and only saw one direction of each edge; the matrix must be symmetric.
• Zero-weight edges are ignored. In this representation 0 means "no edge"; if genuine zero-weight edges are needed, use a separate adjacency flag.
• Infinite loop. in[u] = 1 missing, so the same vertex is selected forever.

Technique: verify the total against Kruskal's result on the same graph — two independent algorithms agreeing is strong evidence. Also test a deliberately disconnected graph.

Memory safety

• Disconnection must be detected, not assumed. Returning a partial total for a disconnected graph is a silent wrong answer; the u < 0 branch is the correctness guard.
• Two allocations, one failure path. Check both, free whatever succeeded — note this function has an early return -1 inside the loop that must also free.
• in must be zeroed (calloc); garbage marks vertices as already in the tree and produces an under-weight result.
• Symmetric-matrix precondition is unchecked; document that w must be symmetric for an undirected MST.
• Overflow. total sums up to n-1 edge weights — use a wide accumulator when weights are large.
• Validate n before the size_t casts.

Real-world uses

Concrete uses: Laying cable, pipe or fibre at minimum total cost; designing low-cost network backbones; clustering (removing the heaviest MST edges splits data into groups); approximation algorithms for the travelling-salesman problem; and image segmentation via minimum spanning forests. Connectivity checking alone — a single traversal — answers "is this network in one piece?", which is a common monitoring question.

Professional best practices:

Beginner:

• Keep key[v] as an edge weight and say so in a comment; the Dijkstra confusion is extremely common.
• Always handle the disconnected case explicitly.

Intermediate:

• Prim with an O(n^2) selection loop suits dense matrices; Kruskal with union-find suits sparse edge lists. Choose from the representation.
• Record the chosen edges, not just the total, when the caller needs the actual tree.
• If several edges share a weight the MST is not unique — do not write tests that assume a particular edge set, only a particular total.

Practice tasks

1. (Beginner) MST weight. Implement mst_weight returning -1 for a disconnected graph. Example: the demo graph -> 3. Concepts: Prim's growth, disconnection detection.

2. (Beginner) Connectivity. Implement int is_connected(const int *adj, int n) with a single DFS or BFS. Concepts: one traversal is enough.

3. (Intermediate) Report the edges. Extend Prim to record which edge was chosen for each added vertex and print the tree. Concepts: tracking provenance.

4. (Intermediate) Cross-check with Kruskal. Implement Kruskal with union-find and confirm both give the same total on random graphs. Concepts: independent-oracle validation.

Summary

A minimum spanning tree connects every vertex at the least total edge weight, and Prim's algorithm builds it by repeatedly adding the cheapest edge that reaches a vertex still outside the tree. The crucial distinction from Dijkstra is that key[v] holds a single edge weight, not a cumulative path cost — comparing e rather than key[u] + e is the entire difference between the two algorithms. If no outside vertex has any edge into the tree while vertices remain, the graph is disconnected and no spanning tree exists; that case must be reported rather than silently returning a partial total. Prim's O(n^2) form suits dense matrices, while Kruskal with union-find suits sparse edge lists.

Practice with these exercises

• Minimum spanning tree weight
• Is the graph connected?