一种基于二进制编码的最小生成树算法

A minimum spanning tree algorithm based on binary coding

针对目前的最小生成树算法只能求一个最小生成树问题,提出一种新的最小生成树算法。该算法主要采用二进制编码的方式,并结合最小生成树的特点,通过先判断图的边数淘汰一些非生成树,然后通过判断连通性再淘汰一些非生成树,最后从所有的生成树中找到所有最小生成树。由于算法的本质就是在全局范围内寻找最优,故该算法可以找到一个连通图的所有最小生成树。算例表明,该算法具有步骤清晰、方便程序实现、通用性好的特点。

Through the current minimum spanning tree algorithm, present a new minimum spanning tree we can only get a minimum spanning tree. So we algorithm. The algorithm is mainly to use the binary code and combine the characteristics of the minimum spanning tree. At first, it eliminates some of the non-spanning tree through the number of the graph edge. What is more,it eliminates some of the non-spanning tree through the judgement of the graph connectivity. In fact, the nature of the algorithm is to look for the best in the global scope. So we can find all the minimum spanning trees of the connected graph in view of this algorithm. An example shows that the algorithm has clear steps, convenient program implementation, general good characteristic.