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

Jiayu Chen

doi:10.54254/2755-2721/19/20231012

Research Article

Open access

Published on 23 October 2023

Download pdf

Chen,J. (2023). The analysis and application of Prim algorithm, Kruskal algorithm, Boruvka algorithm. Applied and Computational Engineering,19,84-89.

Export citation

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

Jiayu Chen *^,1,

¹ Beijing Normal University - Hong Kong Baptist University United International College

* Author to whom correspondence should be addressed.

https://doi.org/10.54254/2755-2721/19/20231012

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.

Keywords

minimum spanning tree, Prim algorithm, Kruskal algorithm, Boruvka algorithm, graph

View pdf

References

[1]. Iqbal, M., Siahaan, A. P. U., Purba, N. E., & Purwanto, D. (2017). Prim's Algorithm for Optimizing Fiber Optic Trajectory Planning. Int. J. Sci. Res. Sci. Technol, 3(6), pp. 504-509.

[2]. Medak, J. (2018). Review and Analysis of Minimum Spanning Tree Using Prim's Algorithm. International Journal of Computer Science Trends and Technology (IJCST),Volume 6.

[3]. Berger, R., Dubuisson, S., & Gonzales, C. (2012). Fast multiple histogram computation using Kruskal's algorithm. In 2012 19th IEEE International Conference on Image Processing, pp. 2373-2376. IEEE.

[4]. Greenberg, H. J. (1998). Greedy algorithms for minimum spanning tree. University of Colorado at Denver.

[5]. Mariano, A., Proenca, A., & Sousa, C. D. S. (2015). A generic and highly efficient parallel variant of boruvka's algorithm. In 2015 23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, pp. 610-617. IEEE.

[6]. Bergantiños, G., & Vidal-Puga, J. (2011). The folk solution and Boruvka’s algorithm in minimum cost spanning tree problems. Discrete applied mathematics, 159(12), pp. 1279-1283.

[7]. Jarvis, J. P., & Whited, D. E. (1983). Computational experience with minimum spanning tree algorithms. Operations Research Letters, 2(1), pp. 36-41.

[8]. Kershenbaum, A., & Van Slyke, R. (1972). Computing minimum spanning trees efficiently. In Proceedings of the ACM annual conference, 1, pp. 518-527.

[9]. Deng, J., Wang, W., Quan, S., Zhan, R., & Zhang, J. (2022). Hierarchical Superpixel Segmentation for PolSAR Images Based on the Boruvka Algorithm. Remote Sensing, 14(19), p. 4721.

[10]. Huang, F., Gao, P., & Wang, Y. (2009). Comparison of Prim and Kruskal on Shanghai and Shenzhen 300 Index hierarchical structure tree. In 2009 International Conference on Web Information Systems and Mining, pp. 237-241. IEEE.

[11]. Paryati and Salahddine Krit. (2021). The Implementation of Kruskal’s Algorithm for Minimum Spanning Tree in a Graph. MATEC Web of Conferences, 348.

Cite this article

Chen,J. (2023). The analysis and application of Prim algorithm, Kruskal algorithm, Boruvka algorithm. Applied and Computational Engineering,19,84-89.

Data availability

The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.

Disclaimer/Publisher's Note

The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

About volume

Volume title: Proceedings of the 5th International Conference on Computing and Data Science

Conference website: https://2023.confcds.org/

ISBN：978-1-83558-029-5(Print) / 978-1-83558-030-1(Online)

Conference date: 14 July 2023

Editor：Roman Bauer, Marwan Omar, Alan Wang

Series: Applied and Computational Engineering

Volume number: Vol.19

ISSN：2755-2721(Print) / 2755-273X(Online)

© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license. Authors who publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See Open access policy for details).