Fast Implementations of the Kruskal Method for Constructing the Minimum Spanning Tree of a Graph

Abstract

Constructing the minimum spanning tree of a weighted graph falls in the category of fundamental problems in the graph theory. The minimum spanning tree of a graph is generally applied for setting up communication between the nodes of discrete systems that is optimal in terms of cost (weight). Two basic methods for constructing the minimum spanning tree were known before the advent of modern computers. Reduction of computational complexity has become the main line of improving the methods. Inventions made in the field of computational structures facilitated these efforts. The previously published paper by V.S. Zubov and V.V. Kraskov gave a detailed analysis of the most sophisticated implementation of the Prim method. The competing Kruskal’s method features a high computational complexity of its first stage, at which the graph edges are sorted in ascending order of their weights. It is exactly this stage that determines the overall complexity of the method. The article analyzes the effect from constructing special data structures for the first stage of the method. As a result, the status of the Kruskal method has been changed, which becomes faster than the Prim method. Three implementations of the Kruskal method are proposed, in which an idea of partially ordering the set of edges is used. In the first of them, the weak pyramid is used. The number of edge comparison operations in the course of its construction is minimal. The average number of edges extracted from the pyramid for constructing the minimum spanning tree is L ≈ V(0.333 log2V + 0.45). The average time taken to construct the minimum spanning tree has become shorter, but the Prim method still remains more advantageous. A so-called dth pyramid was not previously used in the Kruskal method. Its special implementation contains a fewer average number of not only the main operations, but also a fewer number of the auxiliary operations. The computational complexity of the pyramid construction stage was found to be minimal at d > 4. A formula for estimating the average time taken to construct the minimum spanning tree is given, in which the first, second, and third terms correspond, respectively, to the time taken to construct the pyramid, to extract L edges from it, and to check the edges and include them into the minimum spanning tree; the formula also contains machine-dependent coefficients which are determined experimentally. This implementation is faster than the Prim method, except for low-density graphs. The system of chained lists (stacks) can be used to speed up the edge ordering process at the first stage of the new implementation of the Kruskal method. Edge lists are drawn up within a single graph description viewing cycle. Each list includes edges of equal weight. The lists are used in ascending order of edge weight, until the minimum spanning tree construction process is completed. This implementation is significantly faster than the Prim method. The new implementations of the method were tested on graphs random (pseudorandom) in terms of edge content and weights. References to the implementation codes are also given in the article.