THE DESIGN AND ANALYSIS OF ALGORITHM OF MINIMUM COST SPANNING TREE

数学物理学报(英文版) ›› 1996, Vol. 16 ›› Issue (3): 296-301.

• 论文 • 上一篇

THE DESIGN AND ANALYSIS OF ALGORITHM OF MINIMUM COST SPANNING TREE

徐绪松, 刘大成, 吴丽华

School of Management, Wuhan University, Wuhan 450072, China

收稿日期:1994-06-14 修回日期:1995-02-13 出版日期:1996-09-25 发布日期:1996-09-25

THE DESIGN AND ANALYSIS OF ALGORITHM OF MINIMUM COST SPANNING TREE

Xu Xusong, Liu Dacheng, Wu Lihua

School of Management, Wuhan University, Wuhan 450072, China

Received:1994-06-14 Revised:1995-02-13 Online:1996-09-25 Published:1996-09-25

摘要/Abstract

摘要： This paper provides a method of producing a minimum cost spanning tree (MCST) using set operations. It studies the data structure for implementation of set operations and the algorithm to be applied to this structure and proves tile correctness and the complexity of the algorithm. This algorithm uses the FDG (formula to divide elements into groups) to sort (the FDG sorts a sequence of n elements in expected lim O(n)) and uses the method of path compression to find and to unite. Therefore, it produces an MCST of an undirected network having n vertices and e edges in expected time O(eG(n)).

关键词: Minimum cost spanning tree, A sort using the FDG, Path compression, Set operation of find and unite, Algorithm analysis

Abstract: This paper provides a method of producing a minimum cost spanning tree (MCST) using set operations. It studies the data structure for implementation of set operations and the algorithm to be applied to this structure and proves tile correctness and the complexity of the algorithm. This algorithm uses the FDG (formula to divide elements into groups) to sort (the FDG sorts a sequence of n elements in expected lim O(n)) and uses the method of path compression to find and to unite. Therefore, it produces an MCST of an undirected network having n vertices and e edges in expected time O(eG(n)).

Key words: Minimum cost spanning tree, A sort using the FDG, Path compression, Set operation of find and unite, Algorithm analysis

徐绪松, 刘大成, 吴丽华. THE DESIGN AND ANALYSIS OF ALGORITHM OF MINIMUM COST SPANNING TREE[J]. 数学物理学报(英文版), 1996, 16(3): 296-301.

Xu Xusong, Liu Dacheng, Wu Lihua. THE DESIGN AND ANALYSIS OF ALGORITHM OF MINIMUM COST SPANNING TREE[J]. Acta mathematica scientia,Series B, 1996, 16(3): 296-301.

THE DESIGN AND ANALYSIS OF ALGORITHM OF MINIMUM COST SPANNING TREE

THE DESIGN AND ANALYSIS OF ALGORITHM OF MINIMUM COST SPANNING TREE

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 10