摘要
ＴＨＥＤＥＳＩＧＮＡＮＤＡＮＡＬＹＳＩＳＯＦＡＬＧＯＲＩＴＨＭＯＦＭＩＮＩＭＵＭＣＯＳＴＳＰＡＮＮＩＮＧＴＲＥＥ￥（徐绪松，刘大成，吴丽华）ＸｕＸｕｓｏｎｇ；ＬｉｕＤａｃｈｅｎｇ；ＷｕＬｉｈｕａ（ＳｃｈｏｏｌｏｆＭａｎａｇｅｍｅｎｔ，ＷｕｈａｎＵｎｉ...
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 the 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 tir O(n)) and uses the method of path compression to find and to unite. Therefore. n produces an MCST of an undirected network having n vertices and e edges in expected time O(eG(n)).
