# Minimum Spanning Tree Method for Sparse Graphs

Authors: Xianchao Wang; Shaoyi Li; Changhui Hou; Guoming Zhang
Journal: Mathematical Problems in Engineering
 (2023)

---

## Abstract

The minimum spanning tree (MST) is widely used in planning the most economical network. The algorithm for finding the MST of a connected graph is essential. In this paper, a new algorithm for finding MST is proposed based on a deduced theorem of MST. The algorithm first sorts the edges in the graph according to their weight, from large to small. Next, on the premise of ensuring the connectivity of the graph, it deletes the edges in this order until the number of edges of the graph is equal to the number of vertexes minus 1. Finally, the remaining graph is an MST. This algorithm is equivalent to an inverse Kruskal algorithm. For sparse graphs, the proposed algorithm has higher efficiency than the Kruskal algorithm. Experiments and analysis verify the effectiveness of the algorithm proposed in this paper. The algorithm provides a better choice for finding the MST of the sparse graph.


---

## Body

## 1. Introduction

The spanning tree of a connected graph is the connected subgraph with the least edges, which must contain all vertexes of the connected graph [1]. In all spanning trees of a connected graph, the minimum spanning tree (MST) is that in which the sum of the weights of all edges is the smallest [2, 3]. MST is widely used in many fields [4–6], especially graph theory mode and its solution [7]. For example, it is necessary to lay optical cables between some cities so that any two of these cities can communicate, but the cost of laying optical cables is very high, and the cost of laying optical cables between various cities is different. For this computation, it is necessary to consider how to realize communication between cities at the lowest cost. This problem can be first converted into a graph problem and then solved by the MST. The cities are regarded as the vertexes of a graph. The optical cable laid between the two cities is an edge, and the weight of each edge is the cost of laying the optical cable. In essence, to minimize the total cost of laying the optical cables, it is necessary to find the MST of the graph. Therefore, designing the optimal network structure can often be transformed into finding the MST.The algorithms to find the MST mainly include the Kruskal algorithm [8, 9] and the Prim algorithm [10]. Assume that G = (V, E) is a connected graph with n vertexes, where V and E are the vertex set and edge set, respectively. The Kruskal algorithm selects the edges from small to large according to their weight on the premise of ensuring the connectivity of the graph. When the number of selected edges is equal to n − 1, the algorithm terminates. The main process of the Prim algorithm is as follows: firstly, construct a subgraph (U, F) containing an arbitrary vertex of graph G; the initial edge F set is empty. Then, find the edge with the smallest weight among the edges associated with all vertexes in the vertex set U. If the end point of the edge is in the vertex set V-U, add the end point to the vertex set U, and add the edge to the edge set F, and so on, until all vertexes of the graph G are added to the vertex set U. The obtained subgraph is the MST.Through the implementation process of the Kruskal algorithm and the Prim algorithm, it can be seen that the computational complexity of the Kruskal algorithm isO(mlogm), where m is the number of edges in the graph, so the algorithm is suitable for finding the MST of a sparse graph [11]. The computational complexity of the Prim algorithm is O(n2), which is independent of the number of edges in a graph. Therefore, the Prim algorithm is suitable for finding the MST of a dense graph [12].The most commonly used method to find the MST of a sparse graph is the Kruskal algorithm, which can be also called the edge addition method. Based on the idea of the Kruskal algorithm, this paper proposes a new method to find the MST of a sparse graph. This method first sorts all edges of a sparse graph from large to small according to their weight and then deletes the edge with the largest weight on the premise, ensuring the connectivity of the sparse graph, until the number of edges is equal to the number of vertexes minus 1. The idea of the proposed method is similar to that of the Kruskal algorithm, which can be called the edge reduction method, and its computational complexity isO(mlogm), which is the same as that of the Kruskal algorithm. For finding the MST of a sparse graph with very few edges, the proposed method is faster than the Kruskal algorithm. As an extreme example, for a connected graph, which has n vertexes and n edges, the MST of the graph can be found after only one-step edge reducing operation using the proposed edge reduction method. Using the Kruskal algorithm, the MST of the graph can be found after n − 1 step edge adding operation. Therefore, for sparse graphs with very few edges, the edge reduction method proposed in this paper is more efficient in finding the MST than the classical Kruskal algorithm.The rest of the paper is arranged as follows: the prepared knowledge of the MST of a sparse graph is described in Section 2. The new method to find the MST is proposed in Section 3. The numerical simulation is carried out to demonstrate the proposed method in Section 4. Finally, a conclusion is given in Section 5.


## 2. Minimum Spanning Tree of Sparse Graph

In a given connected graphG = (V, E), where V is the vertex set and E is the edge set, m and n, respectively, represent the number of edges and nodes in the graph G, (u, v) represents the edge connecting the vertexes u and v, and wu,v represents the weight of the edge. Suppose that there is a tree T that is a subgraph of G and contains all vertexes of G, and wT is the sum of the weights of all edges of T. If wT is the smallest, T is the MST of G [13]. The expression of wT is given as follows [14]:(1)wT=∑u,v∈Twu,v.There are many algorithms to construct the MST [15–17], but they all use the same properties of the MST in the following: suppose G = (V, E) is a connected graph and U is a nonempty subset of the vertex set V. If u,v is an edge with minimum weight, where u belongs to U and v belongs to V-U, there must be an MST containing the edge u,v.The Kruskal algorithm is an algorithm used to find the MST and was proposed by Joseph Kruskal in 1956. The Prim algorithm and the Boruvka algorithm are used to solve the same problem [18]. These algorithms are applications of greedy algorithms. Different from the Boruvka algorithm, the Kruskal algorithm is also effective when there are edges with the same weight in the graph.The Kruskal algorithm can be called the edge addition method. The number of edges of the initial MST is 0. Each loop selects a minimum weight edge and adds it to the edge set of the MST on the premise that there is no circuit in the MST. The specific steps of the Kruskal algorithm are as follows:Step 1. Initialize the minimum spanning tree, which is denoted asT; the vertexes of T are the vertexes of G, and the number of edges of T is 0.Step 2. All edges in graphG are sorted by their weights from small to large.Step 3. Loop: traverse each edge from the least weighted edge. If the two vertexes connected by this edge are not in the same connected branch in the graphT, add this edge to T, until T has n − 1 edges.From the implementation process of the Kruskal algorithm, it can be seen that it mainly consists of two steps. The first step is sorting, which sorts all edges of the graph from small to large according to their weight. The second step is to select the edges according to the previous order. It is to be noted that there is no circuit in the process of selecting the edges. Whenn − 1 edges are selected, the algorithm ends. The Kruskal algorithm will gradually merge the trees in the forest. It involves a large number of operations for selecting edges, and its computational complexity is O(mlogm), where m is the number of edges in the graph G. Obviously, when the graph contains fewer edges, the efficiency of the Kruskal algorithm is higher. So this algorithm is suitable for finding the MST of a sparse graph.


## 3. New Method for Minimum Spanning Tree

Before introducing the new method, the property of MST is given in the following:Theory 1.
LetG = (V, E) be a connected graph and U be a nonempty true subset of the vertex set V. If the edge u,v∈E satisfying u∈U and v∈V−U is not unique, and wu∗,v∗=u∈U,v∈V−Umaxwu,v, then the MST of G must not contain the edge u∗,v∗.Proof.
The property of MST is proved by counter evidence in the following:
Assume thatT is an MST of G and T, containing the edge u∗,v∗.
Because the edges connecting the vertex setU and the vertex set V-U in G are not unique, there is an edge u′,v′∈E different from u∗,v∗ in G, where u′∈U, v′∈V−U.
Let us proveu′,v′∉T in the following: according to the connectivity of the tree, it is obvious that there is a path P1 from the vertex u′ to the vertex u∗, and a path P2 from the vertex v∗ to the vertex v′ in T. If u′,v′∈T, P1, P2, u′,v′ and u∗,v∗ constitute a circuit, that is, there is a circuit in T, which is inconsistent with the definition of the tree. Therefore, u′,v′∉T.
By replacing the edgeu∗,v∗ in T with the edge u′,v′, a new graph T′ can be obtained. Clearly, T′ is connected, and the number of edges in T′ is equal to the number of edges in T. Therefore, T′ is also a spanning tree of G.
The only difference betweenT′ and T is that T′ replaces the bigger weighted edge u∗,v∗ in T with the edge u′,v′. Because wu′,v′<wu∗,v∗, so(2)wT′=wT+wu′,v′−wu∗,v∗<wT.
It contradicts the hypothesis that MST is the smallest weight sum in the spanning tree ofG, so T is not the MST of G, which is contrary to the hypothesis.
Therefore, the given property of MST holds.
According to the property of MST, for the maximum weight edge connecting the nonempty subsetU of V and the vertex set V-U in the graph G, if G is still connected after deleting the edge, it indicates that the edge is not the only edge connecting the nonempty subset U and the vertex set V-U, so the maximum weight edge must not belong to MST. Therefore, we carry out the following operations in the order of the weight of the edge in G, from large to small. If the edge with the largest weight is deleted and the remaining graph is still connected, the edge can be deleted. If the remaining graph is not connected after deleting the edge with the largest weight, the edge cannot be deleted. The edge deletion operation continues until the number of the remaining edges of graph G is equal to the vertex number of G minus 1. We delete the edges that do not belong to the MST, and finally, and what is left is the MST we are looking for. This is the new method to find the MST proposed in this paper. The specific steps of the method are as follows:Step 1. Sort the edges in graphG according to their weight, from large to small.Step 2. Delete the edge with the largest weight on the premise of ensuring the connectivity of the remaining graph, until the number of the remaining edges of graphG is equal to the number of the vertexes minus 1.
Pseudo code is given in the following: Algorithm1.
Algorithm 1: The pseudo code of the proposed method for MST.
Input: the connected graphG = (V, E)//The number of the vertexes of G is n, and the number of the edges of G is m.
Output:T//T is the MST of G.
Sort the edges ofG according to their weights from large to small.
T ← G
repeat
e ← longest edge in E
ifT − {e} is connected
then,T ← T − {e}
E ← E − {e}
UntilT contains n − 1 edges
Through the process of finding the MST proposed in this paper, it can be seen that the method can also be called the edge reduction method. Similar to the Kruskal method, the proposed method also traverses the edges of graphG, and its computational complexity is mlogm. Therefore, the proposed method is also suitable for finding the MST of a sparse graph. When m < 2(n − 1), using the proposed method to find the MST needs less than n-1 edge reduction operations, while the Kruskal algorithm needs n − 1 edge addition operations. It can be seen that for connected graphs with very few edges, the proposed method is more efficient than the Kruskal algorithm.


## 4. Experiment and Analysis

In order to verify the effectiveness of the proposed method, we use the Kruskal algorithm and the method proposed in this paper to find the MST of the graphsG1 and G2, where G1 is a dense graph and G2 is a sparse graph.Figures1 and 2 show the process of finding the MST of G1 by using the Kruskal algorithm and the method proposed in this paper, respectively. It can be seen that the Kruskal algorithm obtains the MST of G1 through a 5-step edge addition operation, and the proposed method also obtains the MST of G1 through a 5-step edge reduction operation. The proposed method obtains the same results as the Kruskal algorithm, which proves its correctness. Moreover, the proposed method can be used to find the MST of dense graphs.Figure 1
The process of finding the MST ofG1 using the Kruskal algorithm.Figure 2
The process of finding the MST ofG1 by the proposed method.Figures3 and 4 show the process of finding the MST of G2 by using the Kruskal algorithm and the method proposed in this paper, respectively. Here, G2 is a sparse graph. It can be seen that the MST of the sparse graph found by the proposed method and the Kruskal algorithm are the same. However, the Kruskal algorithm still needs a 5-step edge addition operation, while the proposed method only needs a 1-step edge reduction operation. The proposed method finds the MST of the sparse graph faster than the Kruskal algorithm. For finding the MST of a sparse graph with less than 2(n − 1) edges, the edge reduction operation of the proposed method is less than the edge addition operation of the Kruskal algorithm. Therefore, for sparse graphs with very few edges, the method proposed in this paper is more efficient.Figure 3
The process of finding the MST ofG2 by the Kruskal algorithm.Figure 4
The process of finding the MST ofG2 by the proposed method.


## 5. Conclusion

There are many application scenarios for the MST, ranging from how to plan the path to minimize the transportation cost when we travel to ten countries in Europe to how to plan the path to minimize the construction cost when we build the national power network, highway network, and communication network. Using the algorithm for finding the MST, we can calculate the best path. Not only that, all optimal path problems involving all vertexes in the network can be handled by the MST. At present, the common algorithms are the Prim algorithm and the Kruskal algorithm, which are mainly used to find the MST of dense graphs and sparse graphs, respectively.In this work, based on the derivation of the property of MST, a new method is proposed to find the MST of a sparse graph. Firstly, all edges in the connected graph are sorted according to the weight from large to small, and then on the premise of ensuring the connectivity of the graph, the edges with the largest weight are deleted successively until the number of the remaining edges isn − 1. The proposed method is equivalent to the reverse Kruskal algorithm. The Kruskal algorithm is the edge addition operation, and the proposed method is the edge reduction operation. When m < 2(n − 1), that is, a sparse graph with few edges, the number of the edge reduction operations required by the proposed algorithm is less than that of the edge addition operations required by the Kruskal algorithm, and the proposed method is more efficient. Therefore, the proposed method is a good choice for finding the MST of a sparse graph with few edges. Of course, the scope of application of the proposed method is limited. Once the number of edges of the graph is not less than 2(n − 1), the efficiency of the proposed method will be lower than that of the Kruskal algorithm. In future work, we will further optimize the proposed method. The main idea is to reduce multiple edges each time. If the remaining graph is connected, it means that there is no problem with the edge reduction operation. On the contrary, we need to find the edge that causes the disconnection in the last edge reduction operation. This can effectively improve the efficiency of the proposed method.



---

*Source: 8591115-2023-02-21.xml*