最小生成树问题是一类非常重要的组合优化问题,在现实中被广泛应用于各个领域,如通信网设计、道路系统设计、管道铺设等。如果在最小生成树问题中对每个顶点加以度约束即限制连接到顶点的边的数量,这时问题就成为度约束最小生成树问题。度约束最小生成树问题有很重要的现实意义,比如设计通信网时,如果不考虑度约束,某些重要节点一旦出现故障可能会导致整个网络瘫痪,因此限定连接到节点的边的数量是很有必要的。度约束最小生成树问题的求解方法有启发式算法、遗传算法等。本文讨论完全图下的度约束最小生成树问题,使用单亲遗传算法求解。该算法首先利用Prufer数对生成树进行编码,保证产生的初始种群不含有任何不可行解；设计了三种变异操作,并分析三种变异操作对图的影响而采用按比例执行变异操作,保证产生优秀的可行的子代染色体,拓展搜索空间；构造了两种局部寻优算子,增强了算法在较小区域内搜寻更加适应环境的个体的能力,使得最终能够输出更优秀的个体。