| THE DESIGN AND ANALYSIS OF ALGORITHM OF MINIMUM COST SPANNING TREE |
| |
| 作者姓名： | 徐绪松 刘大成 吴丽华 |
| |
| 作者单位： | School of Management，Wuhan University，Wuhan 450072，China. |
| |
| 摘 要： | ＴＨＥＤＥＳＩＧＮＡＮＤＡＮＡＬＹＳＩＳＯＦＡＬＧＯＲＩＴＨＭＯＦＭＩＮＩＭＵＭＣＯＳＴＳＰＡＮＮＩＮＧＴＲＥＥ￥（徐绪松，刘大成，吴丽华）ＸｕＸｕｓｏｎｇ；ＬｉｕＤａｃｈｅｎｇ；ＷｕＬｉｈｕａ（ＳｃｈｏｏｌｏｆＭａｎａｇｅｍｅｎｔ，ＷｕｈａｎＵｎｉ...
|
THE DESIGN AND ANALYSIS OF ALGORITHM OF MINIMUM COST SPANNING TREE |
| |
| Xu Xusong, Liu Dacheng, Wu Lihua.THE DESIGN AND ANALYSIS OF ALGORITHM OF MINIMUM COST SPANNING TREE[J].Acta Mathematica Scientia,1996(3). |
| |
| Authors: | Xu Xusong Liu Dacheng Wu Lihua |
| |
| Abstract: | This paper provides a method of producing a minimum cost spannilng 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 tim 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 venices and e edges in expected time O(eG(n)). |
| |
| Keywords: | Minimum cost spanning tree A sort using the FDG Path compression Set operation of find and unite Algorithm analysis |
| 本文献已被 CNKI 等数据库收录！ |
