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.
Problem Contract
The standard MST problem expects a connected, undirected, weighted graph.
The output is a set of V - 1 edges that connects every vertex with minimum total edge weight. If the graph is disconnected, the comparable output is a minimum spanning forest, not one spanning tree.
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.
Step-by-Step Meaning
If four vertices must be connected, a spanning tree uses exactly three edges. Adding a fourth edge would create a cycle. Using fewer than three edges would leave something disconnected.
An MST chooses the cheapest set of enough edges to connect everything without cycles.
MST vs Shortest Path
Shortest path asks for the cheapest route between particular vertices or from one source. MST asks for the cheapest way to connect the whole graph.
A minimum spanning tree may not contain the shortest path between two specific vertices.
Common Algorithms
Kruskal’s algorithm sorts edges and adds them when they connect separate components. Prim’s algorithm grows one connected tree by repeatedly adding the cheapest outgoing edge.
Both are greedy algorithms, but they grow the solution in different ways.
Complexity
The complexity depends on the chosen algorithm and representation. Kruskal is often dominated by sorting edges. Prim is often dominated by priority-queue operations over adjacency lists.
How To Recognize It
Look for wording such as “connect all”, “minimum total cost”, “network”, or “build roads/cables/pipes so every place is connected.” Those phrases often point to MST.
If the problem asks for the cheapest way to travel from one place to another, that is shortest path instead. If it asks for the cheapest set of connections that makes the whole network connected, that is MST.
Valid Input Shape
The standard MST problem is about an undirected weighted graph. If the graph is disconnected, no single spanning tree exists across all vertices. The closest result is a minimum spanning forest, one tree per connected component.
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.
Another common mistake is applying MST ideas to directed graphs without checking the problem. Directed versions require different concepts.
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.
Do not use MST when the problem asks for the cheapest route from one node to another.
The Main Point
An MST minimizes total connection cost for the whole undirected graph. It is not a shortest-path structure from one source.