论文导读：：这就需要找到带权的最小生成树。在求带权无向连通图的最小生成树时。本文试图用二进制编码的方式来解决这个问题。则称该二进制字符串是对应该生成树的染色体。最经典的算法就是Prim算法和Kruskal算法[3]。

　　论文关键词：最小生成树，连通图，二进制编码，染色体，算法

　　0 引言

　　许多应用问题都是一个求带权无向连通图[1]的最小生成树[2]问题。例如：要在n个城市之间铺设光缆，主要目标是要使这n个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

　　在求带权无向连通图的最小生成树时，最经典的算法就是Prim算法和Kruskal算法[3]。这两个算法都是通过求解局部最优达到求解全局最优，即我们通常所说的贪心算法。一般来讲，局部最优解往往不是整体最优解，而是近似最优解。由于最小生成树的特殊性，用贪心算法[4]能够准确地计算出它的全局最优解。然而，无论Prim算法还是Kruskal算法，都只能找到带权无向连通图的一个最小生成树。如果一个带权无向连通图有多个最小生成树，要想找出所有的最小生成树连通图，用Prim算法或Kruskal算法都是无能为力的。至于所谓用遗传算法求最小生成树，由于该算法是一种近似算法，可能连一个最小生成树都找不到，最好的情形也是只能找到一个最小生成树。因此，能否找到一种在全局范围内寻找所有最小生成树的算法？到目前为止，还没有相关文献作这方面的工作。本文试图用二进制编码的方式来解决这个问题。

　　1 理论基础

　　定义1 我们用深度优先法或广度优先法遍历一个无向图，如果所有顶点都能被访问到，则称该图是连通图；否则，称该图是不连通图论文参考文献格式。

　　定义2 设一个带权无向连通图[5]有n个顶点和m条边，如果删除m-n+1条边后，该剩余图仍然是连通的，则称该剩余图为生成树。

　　定义3 在一个带权无向连通图的所有生成树中，所有边的权值之和最小的生成树是最小生成树。

　　性质1 如果一个带权无向连通图有n个顶点，那么它的生成树只有n-1条边。

　　证明：如果它有n条边，那么它一定有回路，因此它就不是生成树。另一方面，如果它只有n-2条边，那么这n-2条边最多只能连接n-1个顶点，还有一个顶点没有被连接。

　　定义4 对于一个无向图，如果用字符‘1’表示图中的两个顶点之间存在边，用字符‘0’表示两个顶点间不存在边，则我们称这种用二进制字符串表示的图为对图的二进制编码。

　　定义5 设一个无向连通图有m条边，如果我们用长度为m的二进制字符串表示它的生成树，则称该二进制字符串是对应该生成树的染色体连通图，其中染色体的每一位对应无向图的一条边。

　　性质2 设G是一个含有n个顶点m条边的无向连通图，如果用染色体表示该无向图的生成树，则染色体是长度为m的含有n-m+1个‘1’字符和2m-n-1个‘0’字符的字符串。

　　定义6 如果一个染色体对应带权无向连通图的最小生成树，则称该染色体是最优染色体。

　　性质2 如果找打一个带权无向连通图的最优染色体，则它所对应的最小生成树确定。

　　2 算法设计

　　2.1 带权无向连通图的矩阵表示法

　　设G是一个含有n个顶点m条边的带权无向连通图，则可以用一个阶矩阵表示。其中连通图，。

　　2.2 连通的判断

　　算法的中心思想就是从带权无向连通图的生成树中找出最小生成树。虽然生成树是从图的条边中去掉条边形成的，但仅仅删除边还是不够的，还必须保证删除的剩余图还是连通的，否则就不是生成树。

　　可以通过使用深度优先法或广度优先法对剩余图进行遍历，如果图的所有结点经过一次遍历都可以搜索到，则该剩余图就是生成树。否则，剩余图一定不是生成树。

　　因此，通过深度优先法或广度优先法对剩余图进行遍历，可以将带权无向连通图的所有生成树找出来。然后，从生成树集中找出最小生成树就比较自然了。

　　2.3 对生成树进行二进制编码

　　由于带权无向连通图有条边，因此需要用长度为的二进制字符串即染色体表示该图。当染色体的每一位都是字符‘1’时，该染色体就是表示该带权无向连通图。一方面，带权无向连通图的生成树只有条边，故它所对应的染色体只有个字符‘1’和个字符‘0’；另一方面，由个字符‘1’和个字符‘0’组成的染色体不一定对应一棵生成树，故需要判断该染色体所对应的剩余图是否连通。

　　因此，判断一根染色体是否对应一棵生成树，执行步骤：（1）从“”（该染色体由左边的个‘0’字符和右边的个‘1’字符组成）到“”（该染色体由左边的个‘1’字符和右边的个‘0’字符组成）的染色体中筛选出只含有个字符‘1’的染色体；（2）从（1）筛选出的染色体中进一步筛选出生成树连通的染色体。

　　3 算法描述

　　设G是一个含有n个顶点m条边的带权无向连通图连通图，则生成图G的算法过程如下：

　　Step1：初始化，最优值shortpath=-1，长度为m的二进制字符串str=“”（m个‘0’字符组成），以及建立染色体每一位与带权无向连通图的某一边的对应关系；

　　Step2：将i转化为长度为m的二进制字符串，具体转换过程为：

　　（1）执行语句itoa（i,str1,2），可以将整数i转换为二进制字符串；

　　（2）求出二进制字符串str1的长度，只需执行l=strlen（str1）；

　　（3）执行strcpy（str+m-l,str1），就可以得到i所对应的染色体str。

　　Step3：统计染色体str中所含字符‘1’的个数c。如果，则转向step6；

　　Step4：判断染色体str所对应的图是否连通。如果不连通，则转向step6；

　　Step5：求str所对应的生成树的边权之和curpath论文参考文献格式。如果curpath<shortpath，则执行shortpath=curpath，同时保存该染色体；否则，只保存该染色体。