Minimum spanning tree

Basic definitions and properties

Formally, a spanning tree is an acyclic subgraph that includes all vertices of the original graph. When edges have weights, the total weight of a spanning tree is the sum of weights of its edges. An MST minimizes that total among all spanning trees. Important general properties include the cut property and the cycle property: the cut property says that, for any partition of vertices, the lightest edge crossing that partition belongs to some MST; the cycle property says that, within any cycle, the heaviest edge cannot belong to an MST. These properties justify the correctness of the common greedy algorithms for constructing MSTs.

Common algorithms

Three widely taught algorithms to compute an MST are:

• Kruskal's algorithm: sort edges by weight and add them one by one, skipping those that would form a cycle. Useful for sparse graphs and often implemented with a union-find data structure.
• Prim's algorithm: grow a tree from an arbitrary start vertex by repeatedly adding the cheapest edge that connects the tree to a new vertex. Efficient implementations use priority queues.
• Borůvka's algorithm: repeatedly add the cheapest outgoing edge from each component; it was among the earliest MST methods and can be parallelized.

All three rely on greedy choices validated by the cut and cycle properties. Typical efficient implementations run in near-linear or O(E log V) time for graphs with V vertices and E edges, making MST computation practical for large networks.

History and development

The MST problem emerged from early 20th-century investigations in network design and electrical circuits. Constructive greedy approaches were formalized in the 1920s–1950s era of combinatorial optimization. Over time researchers refined algorithms for different graph types (dense vs. sparse), developed parallel and external-memory variants, and explored theoretical limits on time complexity. The problem remains a canonical example in algorithm design courses because it illustrates greedy algorithms, data structures, and graph reasoning.

Applications and examples

MSTs are applied wherever one needs to connect a set of points at minimum total cost. Typical domains include telecommunication and utility network planning, road and pipeline layout, clustering in machine learning (single-linkage clustering), approximation algorithms for other combinatorial problems (e.g., travelling salesman problem heuristics), and image processing tasks such as segmentation. In phylogenetics, spanning trees appear in simplified models of evolutionary relationships, and in distributed computing MST protocols help build efficient broadcast trees.

Variants and notable facts

Several variants of the basic MST problem adapt the objective or constraints: maximum spanning trees select edges to maximize total weight; constrained or degree-bounded spanning tree problems impose additional limits and are typically harder. If all edge weights are distinct, the MST is unique; otherwise multiple distinct MSTs can exist with equal total weight. Because of the cut and cycle properties, many MST algorithms are greedy and easy to implement. For further reading on foundational concepts and formal proofs, see resources in graph theory and introductory texts on algorithms; for a basic explanation of vertices and edges consult vertex and edge definitions. Practical network design examples are often presented using city-and-road metaphors such as cities and roads.

Note: This article gives a conceptual overview. Implementations and theoretical refinements are extensive subjects with specialized literature and software libraries.