Minimum spanning tree

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.

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

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

In this case, "safe" means that including the edge does not form a cycle in the graph. A cycle means starting at a vertex, travelling to a number of other vertices and ending up at the starting point again without using the same edge twice.

History

Czech scientist Otakar Borůvka developed the first known algorithm for finding a minimum spanning tree in 1926. He wanted to solve the problem of finding an efficient coverage of Moravia with electricity. Today, this algorithm is known as Borůvka's algorithm. Two other algorithms are commonly used today. One of them was developed by Vojtěch Jarník in 1930, and put in practice by Robert Clay Prim in 1957. Edsger Wybe Dijkstra rediscovered it in 1959, and called it Prim's algorithm. The other algorithm is called Kruskal's algorithm, and was published by Joseph Kruskal in 1956. All three algorithms are greedy, and run in polynomial time.

The fastest minimum spanning tree algorithm to date was developed by Bernard Chazelle. The algorithm is based on the soft heap, an approximate priority queue. Its running time is O(m α(m,n)), where m is the number of edges, n is 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 linear time.

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. For general weights, there are randomized algorithms whose expected running time is linear.

The problem can also be approached in a distributed manner. If each node is considered a computer and no node knows anything except its own connected links, one can still calculate the distributed minimum spanning tree.