Minimum Spanning Tree
The subset of edges connecting all vertices in a weighted graph at the lowest possible total cost
A Minimum Spanning Tree (MST) is a subset of edges from a connected, weighted, undirected graph that connects all vertices together, without cycles, at the minimum possible total edge weight.
Definition
A Minimum Spanning Tree (MST) is a subset of edges from a connected, weighted, undirected graph that connects all vertices together, without cycles, at the minimum possible total edge weight.
Overview
A spanning tree of a connected graph with n vertices is any subset of n-1 edges that connects every vertex without forming a cycle — the minimum number of edges needed to keep the graph connected. When edges carry weights, typically representing cost, distance, or capacity, many different spanning trees are usually possible, and the minimum spanning tree is the one among them with the lowest total edge weight. If any two edge weights are distinct, the MST is guaranteed to be unique; ties can produce multiple valid minimum spanning trees with the same total weight. Two classic greedy algorithms solve MST optimally, and both rely on the same underlying insight, sometimes called the cut property: for any partition of a graph's vertices into two groups, the minimum-weight edge crossing between them must belong to some minimum spanning tree. Kruskal's algorithm sorts all edges by weight and greedily adds each one, skipping any edge that would create a cycle, using a Union-Find data structure to check connectivity efficiently, giving a total time of O(E log E). Prim's algorithm instead grows a single tree outward from an arbitrary starting vertex, repeatedly adding the cheapest edge that connects a vertex already in the tree to one that isn't, typically implemented with a priority queue for O(E log V) time. MST problems appear directly in network design — laying cable or fiber to connect a set of locations at minimum total cost, designing efficient road or utility networks — and as a building block inside more complex algorithms, including certain approximation algorithms for the traveling salesman problem, cluster analysis, and image segmentation. Because both Kruskal's and Prim's algorithms are conceptually simple, provably optimal, and efficient, MST is one of the cleaner examples in algorithms coursework of a greedy strategy that actually guarantees a globally optimal answer, in contrast to problems like the knapsack problem where naive greedy approaches fail.
Key Concepts
- Connects all vertices of a weighted graph with minimum total edge weight
- Uses exactly n-1 edges for n vertices and contains no cycles
- Unique if all edge weights are distinct; ties can allow multiple valid MSTs
- Relies on the cut property: the minimum crossing edge always belongs to some MST
- Solved optimally by Kruskal's algorithm using sorted edges and Union-Find
- Solved optimally by Prim's algorithm using a priority queue to grow the tree
- A rare example where a purely greedy strategy guarantees global optimality
- Building block for TSP approximation, clustering, and network design algorithms
Use Cases
Frequently Asked Questions
From the Blog
What Is a Decision Tree in Machine Learning
A decision tree predicts by asking a series of yes/no questions about your data, splitting it step by step until it reaches an answer. It is simple, visual, and easy to read.
Read More AI & TechnologyWhat Does MVP Stand For? Minimum Viable Product Explained
MVP stands for Minimum Viable Product - the simplest version of a product that still delivers real value and lets a team test an idea with actual users before investing further. Here's how to build one well.
Read More AI & TechnologyReAct, Chain-of-Thought and Tree of Thoughts Compared
Chain-of-thought adds reasoning tokens, ReAct interleaves reasoning with tool calls, and Tree of Thoughts explores multiple reasoning branches with backtracking. This article compares the three on cost, latency and the problem shapes where each genuinely improves accuracy, and shows how to escalate between them so that easy inputs never pay for the expensive scaffold.
Read More ProgrammingTrees in Programming: A Complete Beginner's Guide
A tree is a hierarchical data structure of nodes linked from a single root. Learn how trees work, key types like binary search trees, and how to traverse them.
Read More