摘要
利用最小生成树的性质,先找出一些在生成树中应保留的边,再去掉一些无用的边的思想方法,最后得到一个求最小生成树的算法。其时间复杂度与 kruskal 算法接近,对于稀疏图,其性能更优越。
In this paper,an algorithm for finding minimum spanning trees of connected graph is provided. First,we search for some edges which must belong to the spanning trees by using the characters of the spanning tree.Second,deleting some useless edges,then we can get an algorithm.Its time complexity is as much as kruskal algorithm's,but its efficiency is better in sparse graph.
出处
《重庆电力高等专科学校学报》
2003年第2期49-52,共4页
Journal of Chongqing Electric Power College
