[1]ZHOU Rongmin,Buy Wen Ning,Lei Yanfeng.Minimal spanning tree algorithm based on genetic algorithm[J].Journal of Zhengzhou University (Engineering Science),2002,23(01):45-48.[doi:10.3969/j.issn.1671-6833.2002.01.013]
Copy
Journal of Zhengzhou University (Engineering Science)[ISSN
1671-6833/CN
41-1339/T] Volume:
23卷
Number of periods:
2002年01期
Page number:
45-48
Column:
Public date:
1900-01-01
- Title:
-
Minimal spanning tree algorithm based on genetic algorithm
- Author(s):
-
ZHOU Rongmin; Buy Wen Ning; Lei Yanfeng
-
-
- Keywords:
-
- CLC:
-
-
- DOI:
-
10.3969/j.issn.1671-6833.2002.01.013
- Abstract:
-
Based on graph theory and genetic algorithm, an improved genetic algorithm for finding the minimum spanning tree is proposed. The algorithm uses binary coding to represent the minimum tree problem, uses the depth-first search algorithm to judge the connectivity of the graph, and designs the corresponding fitness function, one-parent transposition operator and single-parent reversal operator, as well as four control evolution strategies to improve the execution speed and evolutionary efficiency of the algorithm. Compared with the Kruskal algorithm, the algorithm can obtain a batch of minimum spanning trees in a single genetic evolution process, which is suitable for solving different types of minimum tree problems.