What is Minimum spanning tree?
{{jargon|date=January 2024}} [[File:Minimum spanning tree.svg|thumb|300px|right|The minimum spanning tree of a [[planar graph]]. Each edge is labeled with its weight, which here is roughly proportional to its length.]] A number of problems from [[graph theory]] are called '''Minimum spanning tree'''. In graph theory, a [[tree (graph theory)|tree]] is a way of connecting all the [[vertex|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 [[city|cities]] connected by [[road]]s, 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. 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. ==Finding the minimum spanning tree== ===A first try=== It can be very simple to make an [[algorithm]] that will discover a minimum spanning tree: '''function''' MST(''G'',''W''): ''T'' = {} '''while''' ''T'' does not form a spanning tree: find the minimum weighted edge in ''E'' that is safe for ''T'' ''T'' = ''T'' union {(''u'',''v'')} '''return''' ''T'