Back to Search
Start Over
Minimum Spanning Tree Method for Sparse Graphs.
- Source :
- Mathematical Problems in Engineering; 2/21/2023, p1-6, 6p
- Publication Year :
- 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- SPANNING trees
SPARSE graphs
GRAPH connectivity
ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 1024123X
- Database :
- Complementary Index
- Journal :
- Mathematical Problems in Engineering
- Publication Type :
- Academic Journal
- Accession number :
- 162008185
- Full Text :
- https://doi.org/10.1155/2023/8591115