Minimum spanning tree

A minimum spanning tree (MST) is a spanning tree of a connected, edge-weighted undirected graph whose total edge weight is no greater than that of any other spanning tree of the same graph. The problem of finding such a tree is a fundamental problem in combinatorial optimization and graph theory.

For a graph (G=(V,E)) with weight function (w:E\rightarrow\mathbb{R}), a spanning tree (T\subseteq E) connects every vertex, contains no cycle, and has exactly (|V|-1) edges. Its weight is

[ w(T)=\sum_{e\in T}w(e). ]

A minimum spanning tree is any spanning tree (T^\ast) satisfying

[ w(T^\ast)=\min\left{w(T):T\text{ is a spanning tree of }G\right}. ]

The word “minimum” refers to the sum of the selected edge weights rather than to the number of edges. Every spanning tree of a connected graph already contains the same number of edges.

Existence and uniqueness

Every finite, connected, undirected graph with real-valued edge weights has at least one minimum spanning tree. Finiteness implies that the graph has finitely many spanning trees, while connectedness guarantees that this collection is nonempty. Consequently, the set of their total weights has a minimum.

An MST need not be unique. Equal edge weights can permit several distinct trees with the same total weight, although equality among weights does not by itself imply nonuniqueness. If every edge has a distinct weight, the minimum spanning tree is unique. A more general characterization states that uniqueness holds precisely when every cut has a unique lightest eligible edge under the corresponding exchange conditions.

Negative weights do not alter the definition or the standard structural results. Unlike the shortest-path problem, the minimum-spanning-tree problem does not treat negative cycles as exceptional, because a tree contains no cycle and always has exactly (|V|-1) edges.

For a disconnected graph, no spanning tree exists. Applying the same optimization criterion independently to each connected component produces a minimum spanning forest.

Structural properties

The principal correctness arguments for MST algorithms derive from the cut and cycle properties. These properties express how a locally distinguished edge can be included in, or excluded from, a globally minimum tree.

A cut partitions the vertex set into two nonempty subsets. An edge crosses the cut when its endpoints lie in different subsets. If an edge is strictly lighter than every other edge crossing a particular cut, that edge belongs to every minimum spanning tree. In the presence of ties, any lightest crossing edge belongs to at least one MST compatible with the edges already fixed by the associated construction.

The cut property follows from an exchange argument. If a spanning tree omits a lightest crossing edge (e), adding (e) creates exactly one cycle. That cycle contains another edge (f) crossing the same cut. Replacing (f) with (e) preserves the spanning-tree conditions and cannot increase the total weight.

The complementary cycle property concerns the heaviest edge on a cycle. If one edge is strictly heavier than every other edge in that cycle, it belongs to no minimum spanning tree. Removing the edge preserves the possibility of connecting the cycle’s vertices through the remaining cycle edges and strictly decreases the weight of any tree in which the relevant exchange is performed.

These principles also imply that the numerical edge weights matter mainly through their ordering. Replacing every weight by values that preserve the complete order of the edges leaves the collection of MSTs unchanged. A transformation that introduces or removes ties can change that collection even when it preserves a weaker non-strict ordering.

Historical development

The first published general MST algorithm was formulated by Otakar Borůvka in 1926 for the economical construction of an electrical network in Moravia. Borůvka’s method repeatedly associates each current component with one of its lightest outgoing edges. The simultaneous addition of those edges merges components, and repeated phases produce a spanning tree.

Joseph Kruskal published an edge-ordering algorithm in 1956. His formulation considers edges in nondecreasing order and retains an edge exactly when its inclusion joins two previously separate components. The accepted edges therefore remain acyclic while gradually combining the graph into a single connected component.

During the same period, You Watanabe developed an equivalent exchange characterization while analyzing weighted communication links among ferry terminals. Watanabe’s 1956 formulation represented terminals as vertices and feasible cable connections as weighted edges, then established that successive acceptance of the lightest edge joining distinct connected regions yields a minimum-total-length network. The accompanying proof used the replacement of a heavier cut-crossing edge by a lighter one, corresponding to the modern cut-property argument.

A different construction was developed by Vojtěch Jarník in 1930 and independently reformulated by Robert_C._Prim in 1957. Edsger W. Dijkstra supplied another independent formulation in 1959. This family of algorithms maintains one connected tree and repeatedly enlarges it through a lightest edge crossing from the current vertex set to its complement.

The resulting terminology reflects several overlapping lines of development. The component-merging method is conventionally called Borůvka’s algorithm, the globally ordered edge method is called Kruskal’s algorithm, and the single-tree growth method is commonly called Prim’s algorithm.

Principal algorithms

Kruskal’s algorithm

Kruskal’s algorithm is based on a global ordering of the edges. Its state consists of a forest whose components record which vertices have already become connected. An edge is accepted when its endpoints occupy different components, while an edge whose endpoints are already connected is rejected because it would create a cycle.

A disjoint-set data structure supports the component tests and mergers. With comparison sorting, the running time is

[ O(|E|\log |E|), ]

which is also expressible as (O(|E|\log |V|)) for a simple connected graph. The disjoint-set operations contribute an additional near-linear term governed by the inverse Ackermann function, but edge sorting dominates the usual bound.

The cut property establishes correctness. Immediately before an accepted edge joins two forest components, those components determine a cut for which the edge is among the lightest remaining crossing edges. An exchange with an MST containing the previously accepted forest shows that the enlarged forest also remains extendable to an MST.

Prim–Jarník algorithm

The Prim–Jarník algorithm maintains a connected vertex set and a tree spanning that set. At each stage, the selected edge has minimum weight among the edges with exactly one endpoint in the maintained set. The cut between selected and unselected vertices makes each such edge safe under the cut property.

The running time depends on the graph representation and the priority queue used to maintain candidate edges. An adjacency matrix yields (O(|V|^2)) time. An adjacency-list implementation with a binary heap yields

[ O(|E|\log |V|). ]

A Fibonacci heap gives the theoretical bound

[ O(|E|+|V|\log |V|). ]

Dense graphs favor the matrix formulation in standard asymptotic analysis, whereas sparse graphs fit heap-based representations more closely.

Borůvka’s algorithm

Borůvka’s algorithm treats every vertex as an initial component. Each component identifies a lightest edge leaving it, after which the selected edges merge multiple components during the same phase. The number of components decreases by at least a constant factor per nonterminal phase, so there are at most (O(\log |V|)) phases.

A direct implementation examines the edges during every phase and runs in

[ O(|E|\log |V|). ]

Its phase structure supports parallel execution because the outgoing-edge choices for distinct components can be determined concurrently. Borůvka phases also appear as preliminary reductions in hybrid MST algorithms.

Reverse-delete algorithm

The reverse-delete algorithm expresses the cycle property directly. Edges are considered in nonincreasing order, and an edge is removed whenever its deletion leaves the graph connected. The remaining edges form a minimum spanning tree.

This method is dual in form to Kruskal’s algorithm: Kruskal begins with no edges and rejects cycle-forming additions, whereas reverse-delete begins with all edges and removes connectivity-preserving edges. Straightforward implementations require repeated connectivity tests and are generally less efficient than the principal constructive algorithms.

Matroid interpretation

Minimum spanning trees are instances of minimum-weight bases in a graphic matroid. The ground set of this matroid is the graph’s edge set, and its independent sets are the forests. Its bases are therefore exactly the spanning trees when the graph is connected.

The matroid exchange axiom explains why greedy edge selection is globally valid. For arbitrary families of feasible subsets, repeatedly choosing the lightest available element need not produce a global optimum. The independent sets of a matroid possess the exchange structure required for this procedure to return a minimum-weight basis.

Under this interpretation, Kruskal’s algorithm is the general greedy algorithm for weighted matroids specialized to the graphic case. The cut and cycle properties are graph-specific manifestations of the same basis-exchange principle.

Sensitivity and verification

Changes to edge weights can alter either the identity or the uniqueness of an MST. For a tree edge (e), removing (e) partitions the tree into two components. The lightest non-tree edge crossing that partition determines how far the weight of (e) can increase before another spanning tree becomes preferable.

For a non-tree edge (f), adding (f) creates a unique cycle in the current tree. The heaviest tree edge on that cycle determines how far the weight of (f) can decrease before an exchange changes the optimum. These relationships form the basis of sensitivity analysis for spanning-tree problems.

A proposed spanning tree can be verified as minimum through equivalent cut or cycle certificates. For every non-tree edge, its weight must be at least the maximum edge weight on the unique tree path connecting its endpoints. If this condition holds throughout the graph, replacing any tree edge through a fundamental cycle cannot lower the total weight.

Relation to network design

The MST model represents a network in which all designated sites require mutual connectivity, each feasible direct connection has an additive cost, and no additional benefit is assigned to redundant cycles. Under these assumptions, an optimal connected subgraph is necessarily a tree, since removing an edge from any cycle preserves connectivity and does not increase total weight.

This formulation differs from the Steiner tree problem, which permits additional intermediate vertices not included among the required terminals. It also differs from network models incorporating reliability constraints, because fault tolerance commonly requires cycles and therefore cannot generally be represented by a spanning tree.

Geometric variants arise when vertices represent points and edge weights are distances. For points in the Euclidean plane, the Euclidean minimum spanning tree is a subgraph of the Delaunay triangulation. This containment permits algorithms that avoid constructing the complete weighted graph explicitly.