@article{ART001898127},
author={Ju-Young Lee},
title={An Efficient Implementation of Kruskal's Algorithm for A Minimum Spanning Tree},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2014},
volume={19},
number={7},
pages={131-140}
TY - JOUR
AU - Ju-Young Lee
TI - An Efficient Implementation of Kruskal's Algorithm for A Minimum Spanning Tree
JO - Journal of The Korea Society of Computer and Information
PY - 2014
VL - 19
IS - 7
PB - The Korean Society Of Computer And Information
SP - 131
EP - 140
SN - 1598-849X
AB - In this paper, we present an efficient implementation of Kruskal's algorithm to obtain aminimum spanning tree. The proposed method utilizes the union-find data structure, reducing thedepth of the tree of the node set by making the nodes in the path to root be the child node of theroot of combined tree. This method can reduce the depth of the tree by shortening the path to theroot and lowering the level of the node. This is an efficient method because if the tree's depthreduces, it could shorten the time of finding the root of the tree to which the node belongs. Theperformance of the proposed method is evaluated through the graphs generated randomly. Theresults showed that the proposed method outperformed the conventional method in terms of thedepth of the tree.
KW - minimum spanning tree;weighted graph;cycle;Kruskal's algorithm
DO -
UR -
ER -
Ju-Young Lee. (2014). An Efficient Implementation of Kruskal's Algorithm for A Minimum Spanning Tree. Journal of The Korea Society of Computer and Information, 19(7), 131-140.
Ju-Young Lee. 2014, "An Efficient Implementation of Kruskal's Algorithm for A Minimum Spanning Tree", Journal of The Korea Society of Computer and Information, vol.19, no.7 pp.131-140.
Ju-Young Lee "An Efficient Implementation of Kruskal's Algorithm for A Minimum Spanning Tree" Journal of The Korea Society of Computer and Information 19.7 pp.131-140 (2014) : 131.
Ju-Young Lee. An Efficient Implementation of Kruskal's Algorithm for A Minimum Spanning Tree. 2014; 19(7), 131-140.
Ju-Young Lee. "An Efficient Implementation of Kruskal's Algorithm for A Minimum Spanning Tree" Journal of The Korea Society of Computer and Information 19, no.7 (2014) : 131-140.
Ju-Young Lee. An Efficient Implementation of Kruskal's Algorithm for A Minimum Spanning Tree. Journal of The Korea Society of Computer and Information, 19(7), 131-140.
Ju-Young Lee. An Efficient Implementation of Kruskal's Algorithm for A Minimum Spanning Tree. Journal of The Korea Society of Computer and Information. 2014; 19(7) 131-140.
Ju-Young Lee. An Efficient Implementation of Kruskal's Algorithm for A Minimum Spanning Tree. 2014; 19(7), 131-140.
Ju-Young Lee. "An Efficient Implementation of Kruskal's Algorithm for A Minimum Spanning Tree" Journal of The Korea Society of Computer and Information 19, no.7 (2014) : 131-140.
