2022年一种基于二进制编码的最小生成树算法连通图论文.docx

一种基于二进制编码的最小生成树算法_连通图论文导读:：这就需要找到带权的最小生成树在求带权无向连通图的最小生成树时本文试图用二进制编码的方式来解决这个问题那么称该二进制字符串是对应该生成树的染色体最经典的算法就是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