![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Minimum_spanning_tree.svg/langsimple-640px-Minimum_spanning_tree.svg.png&w=640&q=50)
Minimum spanning tree
data structure, subgraph of a weighted graph / From Wikipedia, the free encyclopedia
A number of problems from graph theory are called Minimum spanning tree. In graph theory, a tree is a way of connecting all the vertices together, so that there is exactly one path from any one vertex, to any other vertex of the tree. If the graph represents a number of cities connected by roads, one could select a number of roads, so that each city can be reached from every other, but that there is no more than one way to travel from one city to another.
![]() | This article uses too much jargon, which needs explaining or simplifying. (January 2024) |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Minimum_spanning_tree.svg/300px-Minimum_spanning_tree.svg.png)
A graph can have more than one spanning tree, just like there may be more than one way to select the roads between the cities.
Most of the time, graphs are weighted; each connection between two cities has a weight: It might cost something to travel on a given road, or one connection may be longer than the other, this means it takes more time to travel on that connection. In the language of graph theory, the connections are called edges.
A minimum spanning tree is a tree. It is different from other trees in that it minimizes the total of the weights attached to the edges. Depending on what the graph looks like, there may be more than one minimum spanning tree. In a graph where all the edges have the same weight, every tree is a minimum spanning tree. If all the edges have different weights (that is: there are no two edges with the same weight), there is exactly one minimal spanning tree.