Graphs/Minimum Spanning Tree

Notes

A minimum spanning tree (MST) of a weighted, connected, undirected graph G is a spanning tree (a tree that connects all vertices) whose total edge weight is minimized. In other words, it is a subset of edges that forms a tree, includes every vertex, and has the minimum possible sum of edge weights.

For a graph G with vertices V and edges E where each edge e has weight w(e), the weight of a spanning tree T is:

$ w(T) = \sum_{e \in T} w(e) $

An MST minimizes this sum.

Properties

Two fundamental properties underlie MST algorithms: the cut property and the cycle property.

Cut Property

A cut of a graph is a partition of its vertices into two nonempty, disjoint sets. A crossing edge is an edge that connects a vertex in one set to a vertex in the other.

Given any cut, the minimum-weight crossing edge belongs to some MST. This is the basis of Prim's algorithm.

More formally: let S be any subset of vertices, and let e be the minimum-weight edge with exactly one endpoint in S. Then there exists an MST containing e.

Cycle Property

Given any cycle in the graph, the maximum-weight edge on that cycle does not belong to any MST. This is the basis of Kruskal's algorithm.

More formally: let C be any cycle, and let f be the maximum-weight edge in C. Then no MST contains f.

Uniqueness

If all edge weights are distinct, the MST is unique. If edge weights are not distinct, there may be multiple MSTs, all with the same total weight.

Algorithms

Two classic greedy algorithms compute the MST. Both run in $ O(E \log V) $ time using efficient data structures.

Prim's Algorithm

See Graphs/Prim Jarnik

Prim's algorithm grows a single tree one edge at a time, starting from an arbitrary vertex. At each step, it adds the minimum-weight edge that connects a vertex in the growing tree to a vertex outside the tree — following the cut property.

The algorithm uses a priority queue to track crossing edges. It maintains a set of visited vertices and iteratively adds the cheapest edge leading to an unvisited vertex.

Pseudocode:

Prim(G, w):
    initialize priority queue PQ
    for each vertex v:
        dist[v] = infinity
        parent[v] = null
    dist[r] = 0
    insert all vertices into PQ with key dist[v]
    while PQ is not empty:
        u = extract-min(PQ)
        mark u as visited
        for each neighbor v of u:
            if v not visited and w(u,v) < dist[v]:
                dist[v] = w(u,v)
                parent[v] = u
                decrease-key(PQ, v, dist[v])

Kruskal's Algorithm

See Graphs/Kruskal

Kruskal's algorithm considers edges in increasing order of weight. It adds the next edge to the growing forest if and only if that edge does not create a cycle — following the cycle property.

The algorithm uses a union-find (disjoint-set) data structure to efficiently test whether adding an edge would create a cycle.

Pseudocode:

Kruskal(G, w):
    sort edges by weight in ascending order
    initialize union-find structure UF with each vertex in its own set
    T = empty set
    for each edge e = (u,v) in sorted order:
        if find(u) != find(v):
            add e to T
            union(u,v)
    return T

Comparison

Prim's algorithm performs better on dense graphs (where $ E \approx V^2 $) when implemented with an adjacency matrix and a simple priority queue.

Kruskal's algorithm performs better on sparse graphs (where $ E \approx V $) because sorting dominates the runtime and the union-find operations are nearly constant.

Applications

Minimum spanning trees have numerous practical applications:

• Image segmentation - Graphs/Miminum Spanning Tree/Image Segmentation
• Network design (electrical grids, telecommunications, road networks)
• Cluster analysis (see Graphs/Cluster Finding)
• Approximation algorithms for NP-hard problems (e.g., the traveling salesman problem)
• Circuit design

Related Pages

• Graphs/Shortest Path - different problem: minimizes sum along a path, not sum across a tree
• Graphs/Prim Jarnik - detailed implementation of Prim's algorithm
• Graphs/Kruskal - detailed implementation of Kruskal's algorithm
• Graphs/Cluster Finding - uses MSTs for clustering
• Graphs/Connectivity - related graph property