Construction of the minimum spanning tree (MST)

1 Formulation of the problem

Let [math]G = (V, E)[/math] be a given connected, undirected graph with edge weights [math]f(e)[/math]. A subgraph that is a tree and connects all the vertices of [math]G[/math] is called a spanning tree. A spanning tree is said to be minimum if the total weight of its edges is minimal among all of the spanning trees.

The formulation of the problem and an algorithm for its solution appeared first in the paper .

2 Variants of the problem

If the original graph [math]G[/math] is disconnected, then a set composed of minimum spanning trees for all the connected components is called a minimum spanning forest (MSF).

For a graph with integer weights, special techniques such as digit-wise sorting can be used, which produces algorithms solving the problem in linear time.

A possible additional requirement in a distributed problem is that data exchanges occur only along the edges of the graph.

3 Properties of the problem

Weights. The solution to the problem depends on the relative rather than absolute values of the weights. Thus, instead of assigning the weights, one can define an ordering (that is, a "less than or equal to" predicate) on the set of edge pairs of the graph. Hence, without loss of generality, one can assume that the edge weights are pairwise distinct. To this end, the edges should be ordered first with respect to weights and then with respect to indices. Moreover, any increasing function can be applied to the original weights, and this will not change the solution. It follows that all the weights can be assumed to belong to a given interval, for instance, the interval [math][0, 1][/math].

Existence and uniqueness. The minimum spanning forest exists for every graph. It is unique if all the edge weights are pairwise distinct. As already noted, the edge weights can always be made distinct. In the case where this condition of distinct weights is not fulfilled, one can easily construct an example with more than one minimum spanning tree.

Merging fragments. Let [math]F[/math] be a fragment of the minimum spanning tree of a graph [math]G[/math], and let [math]G'[/math] be the graph obtained from [math]G[/math] by merging the vertices that belong to [math]F[/math]. Then the union of [math]F[/math] and a minimum spanning tree of the graph [math]G'[/math] is a minimum spanning tree of the original graph [math]G[/math].

"'Minimum edge of a fragment. Let [math]F[/math] be a fragment of the minimum spanning tree, and let [math]e_F[/math] be the edge with a minimum weight outgoing from [math]F[/math] (that is, exactly one end of this edge is a vertex of [math]F[/math]). If such an edge [math]e_F[/math] is unique, then it belongs to the minimum spanning tree. This property underlies Boruvka's algorithm and Prim's algorithm.

'Minimum edge of a graph. If [math]e^*[/math] is the only edge in a graph that has the minimum weight, then it belongs to the minimum spanning tree. This property underlies Kruskal's algorithm.

Associativity with respect to edges. Let [math]MSF(E)[/math] be a minimum spanning tree of the graph with edges [math]E[/math]. Then

[math] MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)). [/math]

The number of edges in a spanning forest of a graph with [math]n[/math] vertices consisting of [math]c[/math] connected components is [math]n-c[/math]. If the number of connected components is known a priori, then this property may be used for an earlier termination of the algorithms.

4 Input and output data

Input data: weighted graph [math](V, E, W)[/math] ([math]n[/math] vertices [math]v_i[/math] and [math]m[/math] edges [math]e_j = (v^{(1)}_{j}, v^{(2)}_{j})[/math] with weights [math]f_j[/math]).

Size of the input data: [math]O(m + n)[/math].

Output data: the list of edges of a minimum spanning tree (for a disconnected graph, the list of minimum spanning trees for all the connected components).

Size of the output data: [math]O(n)[/math].

5 Algorithms for solving the problem

There are three classical approaches to solving this problem:

• Boruvka's algorithm;
• Kruskal's algorithm;
• Prim's algorithm.

If usual data structures are used, then the serial complexity is [math]O(m \ln m)[/math] for all the three algorithms. (Notation: [math]m[/math] is the number of edges and [math]n[/math] is the number of vertices.)

All the other algorithms tend to be a variation of the above approaches or their combination.

• The GHS algorithm (Gallager, Humblet, Spira) and its subsequent versions are distributed variants of Boruvka's algorithm. This algorithm is usually used for the automatic distributed construction of a spanning tree by a commutator network.
• Gabow's algorithm uses a Fibonacci heap for ordering the edges in Boruvka's algorithm. The complexity is [math]O(m \ln \beta (m, n))[/math].
• The Fredman-Willard algorithm is designed for graphs with integer weights and has a linear complexity estimate [math]O(m)[/math]. It combines Prim's algorithm with a specially developed heap algorithm (AF-heap).
• Karger's algorithm solves the problem in linear average-time [math]O(m)[/math]. (The existence of a determinate algorithm with a linear complexity estimate is an open problem.)

It should be noted that the algorithms whose asymptotic complexity is better than [math]O(m \ln n)[/math] usually work slower in practice than the classical algorithms. The constants in the complexity estimates are so large that the better asymptotics gives a noticeable gain only for very large-scale graphs.

6 Parallelization resource

1. The properties of '"merging fragments"' and "'the minimum edge of a fragment"' make it possible to process the fragments independently of each other. Among the three classical algorithms, Boruvka's algorithm based on these properties has the maximum parallelization resource.
2. Associativity with respect to edges can be used to parallelize Kruskal's and Prim's algorithms, whose original versions are substantially serial.
3. The use of parallel algorithms for sorting the edges of the entire graph or the parallel sorting of edges incident to each vertex or the parallel sorting inside each fragment.