A minimum spanning tree connects all vertices in a weighted undirected graph with the smallest possible total edge cost.
It is about connecting the whole graph cheaply, not about shortest routes from one vertex.
Core Idea
A spanning tree uses enough edges to connect every vertex without cycles. For V vertices, a spanning tree has V - 1 edges.
The minimum spanning tree is the spanning tree with the lowest total weight.
Python Example
edges = [
(1, "A", "B"),
(4, "A", "C"),
(2, "B", "C"),
]MST algorithms choose a subset of edges like these so all vertices are connected with minimum total cost.
Common Confusions
A minimum spanning tree is not a shortest path tree. It minimizes total connection cost, not the distance from a start vertex to every other vertex.
MST problems usually assume an undirected connected weighted graph. If the graph is disconnected, the result is a minimum spanning forest.
When To Use It
Use MST reasoning for network design, clustering-like connection problems, and cases where every vertex must be connected at minimum total edge cost.