Minimum Spanning Tree Algorithms Based on Genetic Algorithms

Based on the graphic theory and genetic algorithm ,an improved genetic algorithm is introduced to search the minimum spanning trees. This algorithm uses binary code to represent the problem of minimum spanning trees and uses the depth first searching method to determine the connectivity of the graph.The corresponding fitness function, single parent transposition operator, single parent reverse operators and four kinds of controlling evolutionary strategies are designed to improve its speed and efficiency.In comparison with kruskal algorithm, it can acquire a set of minimum spanning trees during one genetic evolutionary process and is applicable to solving different kinds of minimum spanning tree problems.