摘要
本文提出了一个利用集合运算生成最小生成树的算法,研究了实现集合运算的数据结构及施加在这个结构上的算法,该算法利用公式分组排序(公式分组排序n个元素序列的期望时间是O(n)),利用路径压缩的方法进行查找、并运算,该算法将有n个顶点e条边的无向连通网络生成最小生成树的期望时间是O(eG(n))(当n≤2^(16)时,G(n)≤3)。
This paper provides a method for producing minimum cost spanning tree (MCST) using set operation,and studys its data structure and algorithm.This algorithm uses FDEG(Formula to Divide Elements into Groups) to sort(FDEG sorts n elements sequence in expected time O(n)) and uses path compression to find and to unite.Therefore,it produces MCST of an undirected network with n nodes and e edges in expected time O(eG(n)) ,when n≤216 G(n)≤3.
出处
《计算机学报》
EI
CSCD
北大核心
1993年第11期873-876,共4页
Chinese Journal of Computers
关键词
最小生成树
算法
数据结构
Algorithm of minimum cost spanning tree,sort,path compres sion,algorithm analysis.
