article · Applied and Computational Engineering · 2023

The analysis and application of Prim algorithm, Kruskal algorithm, Boruvka algorithm

Cited by 2Open access

Abstract

Minimum spanning tree has many applications in real life. For example, the government needs to build roads between many cities. Therefore, it is necessary to find the plan with the shortest path to save the cost. The problem is essentially generating a minimal spanning tree, and it require a suitable algorithm to find the minimum spanning tree. In this paper, the author analyzes the structure and time complexity of the Prim algorithm, the Kruskal algorithm and the Boruvka algorithm. Through this research, the author finds Prim algorithm is suitable for dense graphs. The Kruskal algorithm can generate the minimum spanning tree in sparse tree. And the Boruvka algorithm is suitable for graphs that have some special characters. Based on the above conclusions, the author gives some suggestions for urban highway network planning.

Cite this paper

APA 7

Chen, J. (2023). The analysis and application of Prim algorithm, Kruskal algorithm, Boruvka algorithm. Applied and Computational Engineering, 19(1), 84–89. https://doi.org/10.54254/2755-2721/19/20231012

MLA 9

Chen, Jiayu. “The analysis and application of Prim algorithm, Kruskal algorithm, Boruvka algorithm.” Applied and Computational Engineering, vol. 19, no. 1, 2023, pp. 84–89, https://doi.org/10.54254/2755-2721/19/20231012.

Chicago

Chen, Jiayu. 2023. “The analysis and application of Prim algorithm, Kruskal algorithm, Boruvka algorithm.” Applied and Computational Engineering 19 (1): 84–89. https://doi.org/10.54254/2755-2721/19/20231012.

Harvard

Chen, J. (2023) ‘The analysis and application of Prim algorithm, Kruskal algorithm, Boruvka algorithm’, Applied and Computational Engineering, 19(1), pp. 84–89. Available at: https://doi.org/10.54254/2755-2721/19/20231012.

BibTeX

@article{chen2023analysis,
  title = {{The analysis and application of Prim algorithm, Kruskal algorithm, Boruvka algorithm}},
  author = {Chen, Jiayu},
  journal = {Applied and Computational Engineering},
  volume = {19},
  number = {1},
  pages = {84--89},
  year = {2023},
  doi = {10.54254/2755-2721/19/20231012}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.