Minimum Spanning Tree Method for Sparse Graphs

Xianchao Wang, Shaoyi Li, Changhui Hou, Guoming Zhang and Ganesh Ghorai

Mathematical Problems in Engineering, 2023, vol. 2023, 1-6

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.

Date: 2023
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://downloads.hindawi.com/journals/mpe/2023/8591115.pdf (application/pdf)
http://downloads.hindawi.com/journals/mpe/2023/8591115.xml (application/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:8591115

DOI: 10.1155/2023/8591115

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().