Spanning Trees

Suppose every site in a network must be connected, but redundant connections cost money. A minimum spanning tree selects enough weighted undirected edges to connect every vertex while minimizing total weight. The problem models cable layout, road construction, circuit wiring, clustering, and a useful primitive inside approximation algorithms.

The phrase “minimum spanning tree” contains three independent requirements:

• spanning: includes every vertex;
• tree: connected and acyclic;
• minimum: has least total edge weight among all spanning trees.

Dropping any word changes the problem. A shortest-path tree minimizes distances from one source, not the sum of its selected edges. A minimum-cost connected subgraph with optional extra vertices is a Steiner-tree problem, not an MST.

Spanning Trees

For a connected undirected graph G=(V,E), a spanning tree is a subgraph (V,T) that is a tree. The following conditions are equivalent for a graph on V vertices:

1. it is connected and acyclic;
2. it is connected and has exactly V-1 edges;
3. it is acyclic and has exactly V-1 edges;
4. there is exactly one simple path between every pair of vertices.

These equivalences explain why MST algorithms can grow a forest while rejecting cycles or grow one connected tree while adding exactly one new vertex at each step.

When the original graph is disconnected, no spanning tree exists. The natural output is a spanning forest, one tree per connected component.

Minimum Spanning Trees

Given weight w(e) for each undirected edge, the weight of a spanning tree is:

An MST is any spanning tree minimizing this sum. Negative weights cause no difficulty: if an edge is safely selectable, a more negative weight simply makes it more attractive. This contrasts with Dijkstra’s shortest-path algorithm, whose correctness requires nonnegative edges.

An MST need not be unique. For a triangle whose three edges all weigh 1, any two edges form an MST of weight 2.

Cut Property

A cut partitions vertices into two nonempty sets (S, V-S). An edge crosses the cut if its endpoints lie on opposite sides.

Cut property: Let A be a set of edges contained in some MST. If a cut respects A—no edge of A crosses it—then any minimum-weight edge crossing that cut is safe to add to A: some MST contains A plus that edge.

Exchange Proof

Let e be a lightest crossing edge and let T be an MST containing A.

• If T already contains e, there is nothing to prove.
• Otherwise, add e to T. A tree plus one edge contains exactly one cycle.
• That cycle must contain another edge f crossing the same cut; the cycle enters the other side through e and must leave it.
• Because e is lightest across the cut, w(e) <= w(f).
• Replace f by e. The result remains a spanning tree and is no heavier than T, so it is also an MST.
• Since the cut respects A, f is not in A; therefore the replacement preserves every previously selected safe edge.

Kruskal and Prim choose different cuts, but this one proof supports both algorithms.

Cycle Property

The complementary view is:

Cycle property: In any cycle, an edge strictly heavier than every other edge on that cycle belongs to no MST.

If an MST contained the uniquely heaviest cycle edge e, removing it would split the tree. Another, lighter cycle edge crosses that split; replacing e would create a lighter spanning tree, contradicting minimality.

With ties, a maximum-weight cycle edge may belong to some MST, so “strictly heavier” matters. Cut properties justify inclusion; cycle properties justify exclusion.

Reverse Delete

The reverse-delete algorithm applies the cycle view directly. Process edges from heaviest to lightest. Tentatively delete an edge, and restore it only if its deletion disconnects the graph. A deleted edge lay on a cycle at the moment of deletion; among the edges still on that cycle it was at least as heavy as every edge that had not yet been processed, so an MST exists without it. When processing ends, the remaining graph is connected and contains no removable cycle edge, hence it is a spanning tree.

This is the exclusion-side counterpart of Kruskal. Kruskal starts empty and includes a light edge when it joins components; reverse delete starts with the whole graph and excludes a heavy edge when connectivity survives. A direct implementation that runs a traversal after every tentative deletion costs O(E(V+E)) after sorting, so Kruskal is normally preferable. Reverse delete is nevertheless valuable because it makes the cycle property operational rather than merely a proof statement.

Kruskal’s Algorithm

Kruskal processes edges globally from lightest to heaviest, accepting an edge exactly when it joins two different current components.

KRUSKAL(G):
    A = empty set
    make one disjoint set per vertex
    sort edges by nondecreasing weight
    for each edge (u,v) in sorted order:
        if FIND(u) != FIND(v):
            add (u,v) to A
            UNION(u,v)
    return A

The selected edges form a forest throughout. The disjoint-set structure answers whether adding an edge would form a cycle; it is a supporting data structure, not the source of Kruskal’s correctness.

Kruskal Trace

Consider:

Sorted processing:

The MST edges are {A-B, B-C, B-D, C-E} with total weight 13.

Kruskal in C

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    size_t u;
    size_t v;
    long long weight;
} WeightedEdge;

typedef struct {
    size_t *parent;
    unsigned *rank;
} DisjointSet;

typedef enum {
    KRUSKAL_OK,
    KRUSKAL_INVALID_INPUT,
    KRUSKAL_ALLOCATION_FAILED
} KruskalStatus;

static size_t find_set(DisjointSet *set, size_t x) {
    if (set->parent[x] != x) {
        set->parent[x] = find_set(set, set->parent[x]);
    }
    return set->parent[x];
}

static bool union_sets(DisjointSet *set, size_t a, size_t b) {
    a = find_set(set, a);
    b = find_set(set, b);
    if (a == b) {
        return false;
    }
    if (set->rank[a] < set->rank[b]) {
        size_t temporary = a;
        a = b;
        b = temporary;
    }
    set->parent[b] = a;
    if (set->rank[a] == set->rank[b]) {
        ++set->rank[a];
    }
    return true;
}

static int edge_compare(const void *left, const void *right) {
    const WeightedEdge *a = left;
    const WeightedEdge *b = right;
    return (a->weight > b->weight) - (a->weight < b->weight);
}

KruskalStatus kruskal(const WeightedEdge edges[], size_t edge_count,
                      size_t vertex_count, WeightedEdge forest[],
                      size_t forest_capacity, size_t *selected_out) {
    if (selected_out == NULL || (edge_count > 0U && edges == NULL)) {
        return KRUSKAL_INVALID_INPUT;
    }
    size_t max_selected = (vertex_count == 0U) ? 0U : vertex_count - 1U;
    if (edge_count < max_selected) {
        max_selected = edge_count;
    }
    if (forest_capacity < max_selected ||
        (max_selected > 0U && forest == NULL) ||
        edge_count > SIZE_MAX / sizeof(WeightedEdge) ||
        vertex_count > SIZE_MAX / sizeof(size_t) ||
        vertex_count > SIZE_MAX / sizeof(unsigned)) {
        return KRUSKAL_INVALID_INPUT;
    }
    for (size_t i = 0; i < edge_count; i++) {
        if (edges[i].u >= vertex_count || edges[i].v >= vertex_count) {
            return KRUSKAL_INVALID_INPUT;
        }
    }

    WeightedEdge *sorted = malloc(edge_count * sizeof(*sorted));
    size_t *parent = malloc(vertex_count * sizeof(*parent));
    unsigned *rank = calloc(vertex_count, sizeof(*rank));
    if ((edge_count > 0U && sorted == NULL) ||
        (vertex_count > 0U && (parent == NULL || rank == NULL))) {
        free(sorted);
        free(parent);
        free(rank);
        return KRUSKAL_ALLOCATION_FAILED;
    }
    if (edge_count > 0U) {
        memcpy(sorted, edges, edge_count * sizeof(*sorted));
    }
    if (edge_count > 1U) {
        qsort(sorted, edge_count, sizeof(*sorted), edge_compare);
    }

    DisjointSet set = {.parent = parent, .rank = rank};
    for (size_t v = 0; v < vertex_count; ++v) {
        parent[v] = v;
    }

    size_t selected = 0;
    for (size_t i = 0; i < edge_count; ++i) {
        if (union_sets(&set, sorted[i].u, sorted[i].v)) {
            forest[selected++] = sorted[i];
            if (vertex_count > 0U && selected == vertex_count - 1U) {
                break;
            }
        }
    }

    free(sorted);
    free(rank);
    free(parent);
    *selected_out = selected;
    return KRUSKAL_OK;
}

The comparator avoids subtracting weights, which could overflow. The function validates endpoints and output capacity and distinguishes allocation failure. It sorts a private edge copy, so the input order is preserved and the output buffer may safely alias any part of the caller’s input edge array. On success, selected_out is V-1 exactly when a nonempty graph is connected; otherwise the selected edges form a minimum spanning forest. The private copy uses Theta(E) auxiliary storage in addition to the disjoint-set arrays.

Kruskal Correctness

Maintain two invariants:

1. selected edges are acyclic;
2. selected edges are contained in some MST (or, for disconnected input, some minimum spanning forest).

The first holds because an accepted edge joins different components. For the second, just before accepting (u,v), use the cut whose one side is u’s current component. Previously accepted edges do not cross this cut, and because edges are processed in nondecreasing order, (u,v) is a lightest remaining crossing edge. The cut property makes it safe. When a connected graph has V-1 accepted edges, the forest is a spanning tree contained in an MST, so it is that MST.

Prim’s Algorithm

Prim grows one tree. Start from any vertex, then repeatedly select the cheapest edge crossing from vertices already in the tree to vertices outside it.

For each outside vertex v, store:

• key[v]: lightest known edge from the current tree to v;
• parent[v]: tree endpoint offering that edge.

PRIM(G, root):
    key[v] = infinity; parent[v] = none; in_tree[v] = false
    key[root] = 0
    repeat V times:
        u = outside vertex with minimum key
        if key[u] is infinity: graph is disconnected; stop or start another tree
        in_tree[u] = true
        for each edge (u,v,w):
            if not in_tree[v] and w < key[v]:
                key[v] = w
                parent[v] = u

Prim Trace

On the same graph, start at A:

The edge set matches the Kruskal trace. On graphs with ties, the algorithms may produce different MSTs of equal total weight.

Matrix C17 Implementation

This dense-graph version uses an adjacency matrix and a linear scan for the next minimum. has_edge[u][v] is separate from weight[u][v], so zero-weight edges are representable.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

#define PRIM_MAX_VERTICES 128
#define WEIGHT_INF INT64_MAX

bool prim_matrix(size_t n,
                 const bool has_edge[PRIM_MAX_VERTICES][PRIM_MAX_VERTICES],
                 const int64_t weight[PRIM_MAX_VERTICES][PRIM_MAX_VERTICES],
                 size_t root, int parent[], int64_t key[]) {
    if (n == 0U || n > PRIM_MAX_VERTICES || root >= n ||
        has_edge == NULL || weight == NULL || parent == NULL || key == NULL) {
        return false;
    }

    bool in_tree[PRIM_MAX_VERTICES] = {false};
    for (size_t v = 0; v < n; ++v) {
        parent[v] = -1;
        key[v] = WEIGHT_INF;
    }
    key[root] = 0;

    for (size_t iteration = 0; iteration < n; ++iteration) {
        size_t u = n;
        for (size_t v = 0; v < n; ++v) {
            if (!in_tree[v] && (u == n || key[v] < key[u])) {
                u = v;
            }
        }
        if (u == n || key[u] == WEIGHT_INF) {
            return false;                       /* disconnected from root */
        }

        in_tree[u] = true;
        for (size_t v = 0; v < n; ++v) {
            if (has_edge[u][v] && !in_tree[v] && weight[u][v] < key[v]) {
                key[v] = weight[u][v];
                parent[v] = (int)u;
            }
        }
    }
    return true;
}

For an undirected graph, both matrices must be symmetric. Every legitimate edge weight must be strictly less than INT64_MAX, which this compact implementation reserves as infinity. The selected edges are (parent[v],v) for every v != root, and their total is the sum of key[v] excluding the root; callers must also ensure that total is representable if they compute it.

Prim Correctness

At each iteration, let S contain vertices already in the tree. Prim selects the lightest edge crossing (S,V-S). Every earlier chosen edge lies within S, so the cut respects them. By the cut property, the new edge is safe. Repeating until all vertices enter produces an MST.

The key invariant is:

For every outside vertex v, key[v] is the minimum weight of any examined edge from S to v, and parent[v] identifies such an edge.

When a vertex joins S, scanning its outgoing edges incorporates all new cut edges and restores the invariant.

Priority Queues

The matrix implementation spends Theta(V) time selecting the minimum key in each of V iterations, for Theta(V^2) total. This is appropriate for dense graphs, where merely reading the matrix is Theta(V^2).

With adjacency lists and a binary min-heap:

• extract-min occurs V times;
• a successful key decrease occurs at most once per examined edge;
• total time is O((V+E) log V), usually written O(E log V) for connected graphs.

A common C implementation inserts a new (key,vertex) pair instead of implementing decrease-key. When a stale pair is later extracted, discard it if its key no longer equals key[vertex] or the vertex is already in the tree. This can grow the heap to O(E) entries but keeps the same O(E log E)=O(E log V) asymptotic bound for simple graphs.

Prim resembles Dijkstra syntactically, but their keys mean different things:

Prim:     key[v]  = cheapest single edge connecting v to current tree
Dijkstra: dist[v] = cheapest full path from source to v found so far

Confusing weight(u,v) with dist[u] + weight(u,v) changes the problem.

Tree Uniqueness

If every edge weight is distinct, the MST is unique. For any cut, its lightest edge is then unique and forced by the cut property.

The converse is false: a graph may have repeated weights but still a unique MST if tied edges never compete across a relevant cut.

A useful uniqueness test after constructing MST T is:

For every non-tree edge (u,v,w), let m be the maximum edge weight on the unique u-to-v path in T. If w == m, replacing that path edge yields another MST. If w > m for every non-tree edge, the MST is unique.

Efficiently answering maximum-on-tree-path queries can use binary lifting after preprocessing; a direct implementation may scan each path when inputs are small.

MST Verification

Suppose a program returns edge set T and claims it is minimum. Re-running a different MST algorithm is useful testing, but it does not explain what property certifies the answer. A direct verifier checks two layers.

First verify that T is a spanning tree:

1. every selected edge belongs to the input graph;
2. exactly V-1 edges are selected when V>0;
3. a traversal through selected edges reaches every vertex;
4. equivalently, union-find accepts every selected edge without finding a cycle.

Then verify optimality. For every input edge e=(u,v,w) outside T, find the maximum edge weight m on the unique tree path from u to v. The required condition is:

If w<m, adding e creates a cycle and removing an edge of weight m gives a lighter spanning tree, so the claim is false. Conversely, if every non-tree edge passes, transform any other spanning tree into T one tree edge at a time. Each exchange can replace a non-tree edge by a no-heavier tree-path edge, so no alternative tree is lighter. This is the cycle property strengthened into a complete optimality certificate.

A direct verifier finds each path with DFS in O(EV) total on a sparse graph. Binary-lifting tables store, for every vertex and power of two, an ancestor and the maximum edge on the jump. After O(V log V) tree preprocessing, each maximum-path query takes O(log V), making the complete check O((V+E) log V).

Spanning Forests

Kruskal naturally returns a minimum spanning forest on disconnected input: it selects safe edges within each component. If the original graph has c connected components, the completed forest has exactly V-c edges. Fewer than V-1 selected edges therefore certifies disconnection when V > 0.

Prim needs an outer loop:

for each vertex r:
    if r is not yet in a tree:
        set key[r] = 0
        run Prim's growth for that component

The result minimizes total selected weight independently inside every original connected component. It is invalid to describe such an output as one spanning tree.

Bottleneck Paths

For a path P, its bottleneck value is the maximum edge weight on P. The unique u-to-v path in any MST minimizes this value among all u-to-v paths, even though it need not minimize the sum of edge weights.

Let e be a maximum-weight edge on the MST path from u to v. Removing e separates the tree into a cut with u and v on opposite sides. Every alternative u-to-v path must cross that cut. If it crossed using an edge lighter than e, replacing e with that edge would produce a lighter spanning tree. Therefore every alternative path contains an edge of weight at least w(e), and the MST path is bottleneck-optimal.

For example, an MST path may have weights 4,4,4, total 12, while another path has weights 1,9, total 10. The second path is better for ordinary shortest-path distance, but its bottleneck is 9; the MST path guarantees bottleneck 4. This distinction matters when the weakest link determines feasibility, such as vehicle clearance, bandwidth limits, or threshold connectivity.

MST Clustering

Single-linkage clustering defines the distance between two clusters as the smallest edge joining them. Build an MST and delete its k-1 heaviest edges; the remaining k components are exactly the clusters produced by stopping single linkage at k groups.

For two clusters, let e be a heaviest MST edge. Deleting it produces parts S and V-S whose spacing is the lightest original edge crossing between the parts. The cut property implies that no crossing edge is lighter than e; otherwise replacing e would improve the MST. Thus the spacing equals w(e). Any different two-cluster partition must separate the endpoints of some edge on the MST, and its spacing is no greater than the weight of a heaviest MST edge it cuts. Deleting a heaviest edge therefore maximizes the minimum intercluster spacing.

With ties, several deletions can yield different but equally spaced clusterings. The statement also depends on single-linkage’s minimum-cross-edge definition; centroid, complete-linkage, balance, and capacity-constrained clustering are different optimization problems.

MST Costs

Because E <= V^2 for simple graphs, log E = O(log V), so Kruskal is also commonly written O(E log V). Union-find contributes O(E alpha(V)), dominated by sorting.

Choosing an MST Method

Choose Kruskal when:

• the input is naturally an edge list;
• the graph is sparse;
• a forest is acceptable or disconnected input is common;
• edges arrive already sorted or can be externally sorted.

Choose Prim when:

• the graph is connected and explored through neighbors;
• a matrix represents a dense graph;
• you want to grow outward from a chosen region;
• a heap-backed adjacency-list implementation is available.

Both rely on the cut property, accept negative weights, and return optimal total edge weight. Neither solves shortest paths, directed arborescences, or Steiner trees.

MST Failures

• Running MST algorithms on a directed graph without converting to an appropriate undirected model.
• Treating zero as “no edge,” thereby losing legitimate zero-weight edges.
• Returning V-1 unverified edges without checking connectivity or acyclicity.
• Using subtraction in a qsort comparator and overflowing.
• Assuming a Kruskal interface either preserves or mutates edge order without checking its contract; the chapter implementation sorts a private copy.
• Letting Prim select an infinite-key vertex in a disconnected graph.
• Reporting only total weight when callers need selected edges or parent structure.
• Assuming uniqueness because one implementation returned the same tree repeatedly.
• Mistaking MST total weight for minimum source-to-destination distance.

MST Applications

• minimum physical network layout when edge costs are independent;
• single-linkage hierarchical clustering by removing the largest MST edges;
• image segmentation over neighboring pixels or regions;
• bottleneck paths: the path between two vertices in an MST minimizes the maximum edge weight among all paths between them;
• approximating metric travelling-salesperson tours using an MST preorder;
• reducing a dense candidate network to a connectivity-preserving backbone.

Models matter: real networks may require redundancy, degree limits, directed links, capacity, reliability, or economies shared across routes. A plain MST captures none of those additional constraints.

MST Review

• A spanning tree connects every vertex without cycles and contains exactly V-1 edges.
• An MST minimizes total selected edge weight, not path distance from a source.
• The cut property proves light crossing edges safe; the cycle property rules out uniquely heavy cycle edges.
• Kruskal sorts edges and uses disjoint sets to reject cycles.
• Prim grows one tree using the cheapest crossing edge and benefits from a min-priority queue.
• Both are greedy algorithms justified by the same exchange argument.
• Disconnected input yields a minimum spanning forest, not one spanning tree.
• Distinct weights guarantee uniqueness, but repeated weights do not necessarily imply multiple MSTs.
• A candidate tree is minimum exactly when every non-tree edge is at least as heavy as the maximum edge on its tree path.
• MST paths minimize bottleneck weight, and deleting the largest MST edges produces maximum-spacing single-linkage clusters.

MST Problems

Tree Vocabulary

1. Give four equivalent characterizations of a tree.
2. Distinguish an MST from a shortest-path tree with a concrete objective for each.
3. State the cut and cycle properties, including the role of ties.
4. Why are negative edge weights harmless for MST algorithms?

Greedy Traces

5. Trace Kruskal on the worked graph after changing C-D to weight 2. List every safe choice and rejection.
6. Trace Prim from each possible root. Which selected edge sets change, and which total weights change?
7. For a disconnected graph with components of sizes 4,3,1, how many edges must a spanning forest contain?

Exchange Proofs

8. Complete the exchange proof of the cycle property.
9. Prove that distinct edge weights imply a unique MST using either the lightest edge on a distinguishing cut or the first edge where two hypothetical MSTs differ.
10. Prove the bottleneck-path property of an MST.

Implementation Faults

11. Construct a disconnected graph on which the matrix Prim implementation would read an invalid vertex if its infinity check were removed.
12. Give large long long weights that make return a->weight - b->weight; overflow or convert incorrectly as a comparator.
13. Show a graph where replacing Prim’s update by key[v] = key[u] + w produces a shortest-path tree rather than an MST and has greater total tree weight.

MST Programming

14. Add explicit status reporting to kruskal for invalid edges, allocation failure, disconnected input, and success.
15. Implement heap-backed Prim using lazy duplicate entries. Count stale extractions on several graph families.
16. Extend both algorithms to return component identifiers and a minimum spanning forest.

MST Scenarios

17. You have one million vertices and two million edges already stored in a file sorted by weight. Choose an MST strategy and account for memory and I/O.
18. You have a dense 10,000 x 10,000 symmetric weight matrix generated on demand. Choose a strategy and justify why a heap may not help.
19. Design a test that checks a reported tree is minimum without enumerating every spanning tree. Use the maximum edge on paths condition.

Tree Extensions

20. Derive the second-best spanning tree: for each non-tree edge, add it, remove a maximum-weight edge on the created cycle, and choose the lightest result strictly heavier than the MST. Discuss ties.
21. Prove that deleting the heaviest edge of an MST partitions the graph into two clusters that maximize the minimum spacing for two-cluster single-linkage clustering.