최소신장트리를 위한 크루스칼 알고리즘의 효율적인 구현 (An Efficient Implementation of Kruskal's Algorithm for A Minimum Spanning Tree)

서지정보

· 발행기관 : 한국컴퓨터정보학회
· 수록지 정보 : 한국컴퓨터정보학회논문지 / 19권 / 7호 / 131 ~ 140페이지
· 저자명 : 이주영

초록

본 논문에서는 최소신장트리를 구하는 크루스칼 알고리즘의 효율적인 구현 방법을 제시한다. 제시하는 방법은union-find 자료구조를 이용하며, 노드 집합을 나타내는 각 트리의 깊이를 줄이기 위해 union 연산시 루트까지의경로에있는노드들의위치를최종루트의자식노드로 직접이동하여 깊이를 줄이도록하는 방법이다. 이방법은루트까지의 경로를 축소하고 노드의 레벨을 축소시킴으로써 트리의 깊이도 줄일 수 있다. 트리의 깊이가 줄어든다면노드가 속하는 트리의 루트를 찾는 시간을 줄일 수 있게 되어 효율적인 방법이라 할 수 있다. 본 장에서 제안하는방법을 그래프로 평가해보고 분석해 본 결과, 기존의 union() 방법이나 경로축소방법인 union2() 보다 트리의 깊이를 작게 유지함을 알 수 있다.

영어초록

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.

참고자료

· 없음