본문 바로가기
  • Home

An Efficient Implementation of Kruskal's Algorithm for A Minimum Spanning Tree

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2014, 19(7), pp.131-140
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Ju-Young Lee 1

1덕성여자대학교

Accredited

ABSTRACT

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.

Citation status

* References for papers published after 2022 are currently being built.