毕业论文初稿(10)

最小生成树

最小元对应的k条边构成的图连通。

首先，判断第一个非零最小元的脚标与其余非零最小元的脚标是否有交集。若没有交集，则说明第一个非零最小元所对应的边与其他边没有连通。若有交集，则将与之有交集的所有元素的脚标和第一个非零最小元的脚标取并集，然后再判断此并集与剩余元素的脚标是否有交集。直到发现没有交集，从而找出未连通的边（或边的集合）。每找到一条未连通的边或一个未连通的边的集合，z+1（z的初值为0）。若z﹤n-1-k，在剩下的非零最小元里继续寻找未连通的边（或边的集合），直到z=n-1-k停止寻找。找到未连通的边（或边的集合）后，在权矩阵里分别找出该边的横、纵脚标所对应的行的非零最小元（如果是边的集合，可将所有边的脚标取并集，然后找出并集中每个元素对应的行的非零最小元），然后进行比较，选取值最小的元素（若出现两个及以上最小值，则任取其一）。此元素所对应的边即为要寻找的边。由寻找到的边与之前k个非零最小元对应的k条边构成的图即为所求的最小生成树。

许多应用问题都是一个求带权无向连通图的最小生成树问题。最经典的算法就是Prim算法和Kruskal算法。这两个算法都是求解局部最优达到求解全局最优。它们都只能找到带权无向连通图的一个最小生成树。如果一个带权无向连通图有多个最小生成树，要想找出所有的最小生成树，用Prim算法和Kruskal算法都是无能为力的。求解最小生成树问题的一种新的遗传算法。

树的编码策略：用一个{1，2,……n}的一个排列p来表示有n个