The minimum spanning tree of a planar graph. Each edge is labelled with its weight, which here is roughly equal to its length.

Given a connected, undirected graph, a spanning tree of that graph is a subgraph which is a tree and connects all the vertices together. A single graph can have many different spanning trees. We can also assign a weight to each edge, which is a number representing how unfavorable it is, and use this to assign a weight to a spanning tree by computing the sum of the weights of the edges in that spanning tree. A minimum spanning tree or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree. More generally, any undirected graph has a minimum spanning forest. Image File history File links Minimum_spanning_tree. ... Image File history File links Minimum_spanning_tree. ... In mathematics and computer science, graph theory studies the properties of graphs. ... This article just presents the basic definitions. ... A spanning tree (red) of a graph (black), superimposed In the mathematical field of graph theory, a spanning tree T of a connected, undirected graph G is a tree composed of all the vertices and some (or perhaps all) of the edges of G. Informally, a spanning tree of G... One major problem that has plagued graph theory since its inception is the consistent lack of consistency in terminology. ... A tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ...

One example would be a cable TV company laying cable to a new neighborhood. If it is constrained to bury the cable only along certain paths, then there would be a graph representing which points are connected by those paths. Some of those paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. A spanning tree for that graph would be a subset of those paths that has no cycles but still connects to every house. There might be several spanning trees possible. A minimum spanning tree would be one with the lowest total cost.

In case of a tie, there could be several minimum spanning trees; in particular, if all weights are the same, every spanning tree is minimum. However, one theorem states that if each edge has a distinct weight, the minimum spanning tree is unique. This is true in many realistic situations, such as the one above, where it's unlikely any two paths have exactly the same cost. This generalizes to spanning forests as well.

If the weights are non-negative, then a minimum spanning tree is in fact the minimum-cost subgraph connecting all vertices, since subgraphs containing cycles necessarily have more total weight.

Algorithms

The first algorithm for finding a minimum spanning tree was developed by Czech scientist Otakar Borůvka in 1926 (see Boruvka's algorithm). Its purpose was an efficient electrical coverage of Bohemia. There are now two algorithms commonly used, Prim's algorithm and Kruskal's algorithm. All three are greedy algorithms that run in polynomial time, so the problem of finding such trees is in P. Otakar Boruvka (May 10, 1899-July 22, 1995) was a Czech mathematician best known today for his work in graph theory. ... 1926 (MCMXXVI) was a common year starting on Friday (link will take you to calendar). ... Borůvkas algorithm is an algorithm for finding minimum spanning trees. ... Flag of Bohemia Bohemia (Czech: ; German: ) is a historical region in central Europe, occupying the western and middle thirds of the Czech Republic. ... Prims algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. ... Kruskals algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. ... Greedy Algorithms are algorithms which follow the problem solving meta-heuristic of making the locally optimum choice at each stage with the hope of finding the global optimum. ... In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ...

The fastest minimum spanning tree algorithm to date was developed by Bernard Chazelle, and based on Borůvka's. Its running time is O(e α(e,v)), where e is the number of edges, v refers to the number of vertices and α is the classical functional inverse of the Ackermann function. The function α grows extremely slowly, so that for all practical purposes it may be considered a constant no greater than 4; thus Chazelle's algorithm takes very close to O(e) time. Bernard Chazelle Bernard Chazelle (born November 5, 1955) is a professor of computer science at Princeton University. ... It has been suggested that this article or section be merged into Asymptotic notation. ... In computability theory, the Ackermann function or Ackermann-Péter function is a simple example of a computable function that is not primitive recursive. ... It has been suggested that this article or section be merged into Asymptotic notation. ...

What is the fastest possible algorithm for this problem? That is one of the oldest open questions in computer science. There is clearly a linear lower bound, since we must at least examine all the weights. If the edge weights are integers with a bounded bit length, then deterministic algorithms are known with linear running time, O(e). For general weights, randomized algorithms are known that run in linear expected time. A randomized algorithm or probabilistic algorithm is an algorithm which is allowed to flip a truly random coin. ...

Whether there exists a deterministic algorithm with linear running time for general weights is still an open question. However, Seth Pettie and Vijaya Ramachandran have found a provably optimal deterministic minimum spanning tree algorithm, the computational complexity of which is unknown. [1]

More recently, research has focused on solving the minimum spanning tree problem in a highly parallelized manner. For example, the pragmatic 2003 paper "Fast Shared-Memory Algorithms for Computing the Minimum Spanning Forest of Sparse Graphs" by David A. Bader and Guojing Cong demonstrates an algorithm that can compute MSTs 5 times faster on 8 processors than an optimized sequential algorithm.[2] Typically, parallel algorithms are based on Boruvka's algorithm — Prim's and especially Kruskal's algorithm do not scale as well to additional processors. David A. Bader is an Associate Professor in the College of Computing at Georgia Institute of Technology. ...

Other specialized algorithms have been designed for computing minimum spanning trees of a graph so large that most of it must be stored on disk at all times. These external storage algorithms, for example as described in "Engineering an External Memory Minimum Spanning Tree Algorithm" by Roman Dementiev et al.,[3] can operate as little as 2 to 5 times slower than a traditional in-memory algorithm; they claim that "massive minimum spanning tree problems filling several hard disks can be solved overnight on a PC." They rely on efficient external storage sorting algorithms and on graph contraction techniques for reducing the graph's size efficiently. In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ...

MST on complete graphs

It has been shown by J. Michael Steele based on work by A. M. Frieze that given a complete graph on n vertices, with edge weights chosen from a continuous random distribution f such that f'(0) > 0, as n approaches infinity the size of the MST approaches ζ(3) / f'(0), where ζ is the Riemann zeta function. In the mathematical field of graph theory a complete graph is a simple graph where an edge connects every pair of vertices. ... The infinity symbol ∞ in several typefaces The word infinity comes from the Latin infinitas or unboundedness. ... In mathematics, the Riemann zeta-function, named after Bernhard Riemann, is a function of significant importance in number theory, because of its relation to the distribution of prime numbers. ...

For uniform random weights in [0,1], the exact expected size of the minimum spanning tree has been computed for small complete graphs.

Related problems

A related graph is the k-minimum spanning tree (k-MST) which is the tree that spans some subset of k vertices in the graph with minimum weight. In mathematics, the K-minimum spanning tree is a graph G that spanns some K of N vertices in the input set S with the minimum total length. ...

A set of k-smallest spanning trees is a subset of k spanning trees (out of all possible spanning trees) such that no spanning tree outside the subset has smaller weight. [4] (Note that this problem is unrelated to the k-minimum spanning tree.)

A geometrically related problem is the Euclidean minimum spanning tree. An EMST computed and drawn by Leda, a C++ commercial algorithm library; see the External Links section The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of points in the plane, where the weight of the edge between each pair of points is the...

In the distributed model, where each node is considered a computer and no node knows anything except its own connected links, one can consider Distributed Minimum Spanning Tree. Mathematical definition of the problem is the same but has different approaches for solution.

See also

• Prim's algorithm
• Kruskal's algorithm
• Borůvka's algorithm
• Dijkstra's algorithm

Prims algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. ... Kruskals algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. ... Borůvkas algorithm is an algorithm for finding minimum spanning trees. ... Dijkstras algorithm, named after its discoverer, Dutch computer scientist Edsger Dijkstra, is an algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weights. ...

References

• Otakar Boruvka on Minimum Spanning Tree Problem (translation of the both 1926 papers, comments, history) (2000) Jaroslav Nesetril, Eva Milková, Helena Nesetrilová (section 7 gives his algorithm, which looks like a cross between Prim's and Kruskal's)
• A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity, Bernard Chazelle, 1999
• [5]
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 23: Minimum Spanning Trees, pp.561–579.
• Two Algorithms for Generating Weighted Spanning Trees in Order, Harold Gabow, 1977

Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ... Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ...

External links

• Implemented in BGL, the Boost Graph Library