毕业论文初稿

最小生成树

太原师范学院毕业论文 ——

系别：数学系 最小生成树算法的改进与应用

最小生成树

班级：1106班

专业：信息与计算科学 学号：2011104201 指导老师：冯源 姓名：高坤城

目录

一.摘要…………………………………

最小生成树

二.提出问题……………………………

三.分析问题……………………………

四.解决问题……………………………

五.得出结论及总结……………………

六.参考文献……………………………

最小生成树

摘要

首先，我们知道最小生成树的定义。最小生成树，一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的边。即在一给定的无向图G=（V,E）中，（u，v）代表连接顶点u与顶点v的边，而w（u，v）代表此边的权重，若存在T为E的子集且为无循环图，使得w（T）最小，则此T为G的最小生成树 。构造最小生成树可以有多种算法，它在我们日常生活中的应用也有很多， 所以我们研究并且改进最小生成树就显得很有必要，也很值得期待。

关键字：最小生成树 算法 应用 改进

以下是求解最小生成树的一般算法流程：GENERIC-MST(G,W) 1，A->P

2，while A没有形成一棵生成树

3，do 找出A的一条安全边（u，v）

4，A->A并{（u,v）}

最小生成树

5,return A

一开始A为P，显然满足最小生成树子集的条件。之后，每一次循环把一条A的安全边加入A中，A依然是最小生成树。确认安全边的规则由下列定理得到，设图G(V,E)是一无向连通图，且在E上定义了相应的实数值加权函数w，设A是E的一个子集，且包含于G的某个最小生成树中，割（S,V-S）是G的不妨碍A的任意割且边（u,v）是穿过割（S,V-S）的一条轻边，则边(u,v)对集合A是安全的。其中有一个推论也很有用，设G=（V,E）是一无向连通图，且在E上定义了相应的实数值加权函数w，设A是E的子集且包含于G的某个生成树中，C是森林Ga=(V,A)中的连通支。若边（u,v）是连接C和Ga中其他某连通支的一轻边，则边(u,v)对集合A是安全的。那么如何很好地实现最小生成树的算法和应用就显得尤为重要。

最小生成树的应用相当广泛，比如在电路设计中，常常需要把一些电子元件的插脚用电线连接起来。如果每根电线连接两个插脚，把所有n个插脚连接起来，只用n-1根电线就可以了把问题转化为图论模型就是：一个无向连通图G=（V,E）,V是插脚的集合，E是插脚两两之间所有可能的连接的集合。给每条边（u，v）一个权值w（u，v），表示连接它们所需要的电线长度。我们的目标就是找到一个无环的边集T，连接其中所有的点且使总权值最小。总权值w（T）=w（u，v），既然T是连接所有点的无环边集，它一定是一棵树。因为这棵树是生成出来的，便被称为生成树，如果一棵树中总权值最小，它就是最小生成树。其中一个典型应用就是基于最小生成树算法的网架规划

最小生成树

目前，求最小生成树的算法已经非常成熟。平时用的算法有Kruskal算法（也叫避圈法）、Prim算法（也称边割法）、破圈法，但这三种算法需要判断圈或者构造边割。这些算法的优点是简单明了，通俗易懂；缺点是通常用来直接在图上作业；此外，还有基于Dijkstra算法的矩阵法、基于破圈法的完全关联矩阵法等；这些算法的优点是可用于求取大规模网络的最小生成树，缺点是计算过程复杂，效率低。根据最小生成树的定义及性质，想出了一种基于权矩阵的最小生成树算法。将它用来求配电网架规划中的最小生成树会使整个算法的计算效率显著提高。

1.1算法思想

设图G是一个连通的无向带权图。如果Go是一个包含G中所有顶点且无回路的连通子图，则Go是G的一棵生成树。若G有n个顶点，那么它的生成树有n个顶点，n-1条边。一个图可以有很多不同的生成树。其中，各条边权值之和最小的生成树即为最小生成树。根据最小生成树的定义及性质可以得到如下几个结论（1）G1中的各条边权值之和最小。（2）G1中有n个顶点n-1条边。（3）G1必须是连通的且无回路。

因此，只要在一个连通带权图里找到一个同时满足上述三个条件的图，也就找到了该图的最小生成树。

图G中各条边的权值已知，由此可以形成一个n×n的权矩阵A。元素Aij表示第i个顶点到第j个顶点的边的权值。规定：若顶点i与

最小生成树

顶点j不直接相连，则Aij=0。对角线元素Aii=0。

从理论上来讲，由与各顶点相连的最短边构成的生成树，其每条边的权值和一定最小。所以，首先找出与各个顶点相连的权值最小的边。即在权矩阵A中按行找出非零最小元。若一行中同时出现两个非零最小元，说明离该点有两个最近点，即与该点相连的所有边里有两条权值最小的边，可随便选一个。如果找出的所有非零最小元中同时出现Aij与Aji，表示离顶点i最近的是点j，而离点j最近的是点i。则任意去掉Aij、Aji中的一个。然后统计非零最小元的个数k。至此可以得到这样几个结论：①这k个非零最小元的脚标的并集必然包括了1，2，3……n，即由这k个非零最小元分别对应的边构成的图有n个顶点；②k≦n-1；③构成的图没有回路。

假设与各个顶点相连的最短边互不重合，即在形成的权矩阵中按行寻找到的非零最小元个数为4。假设与点1相连的所有边中a13最小；与点2相连的所有边中a23最小；与点3相连的所有边中a34最小；与点4相连的所有边中a41最小。从而有

，a13＜a14（1B）23＜a21（2A），a23＜a24a13＜a12（1A）

（2B）；

a34＜a32（3A），a34＜a31（3B）；a41＜a42（4A），a41＜a43（4B）。

根据aij=aji以及上述关系式中的（1B）（4B）（3B），可以得出a13＜a14＜a34＜a31。因为a13=a31，所以上式不成立。即在形成的权矩阵中按行寻找到的非零元个数不可能为4（更不可能比4大，

最小生成树

因为矩阵是4行4列的），只能小于等于3。

同理，在有n个顶点的带权无向连通图中，它所对应的权矩阵按行搜索到的非零最小元个数k必然小于等于n-1。

已知非零最小元的个数k，接下来判断k是否等于n-1。若k=n-1，则这k条边一定可以构成一个含有n个顶点的无回路连通图。而且这k个元素分别是权矩阵每行中值最小的，所以它们的和也最小。因此，由这k个非零最小元对应的k条边构成的图满足了n个顶点、n-1条边、权值和最小、连通且无回路的条件，此即为图G的最小生成树。

如果k﹤n-1，说明由这k条边构成的图没有连通。在图中，如果边aij（顶点i与顶点j之间的边）与amn（顶点m与顶点n之间的边）相连，那它们必然共用一个顶点，即脚标ij、mn必然有交集，否则这两条边就不连通。因此，要判断一条边或一个边的集合（这里把连通的几条边称为边的集合，一个边的集合至少包含两条边，如{a12，a13，a34}与图中其他边是否相连，只需看这条边的脚标或这个边集合中所有边的脚标的并集与图中其他边的脚标是否有交集。有交集，则说明连通；否则就没有连通。n-1条边可将n个顶点连通，所以根据n-1-k的值，可以判断还需几条边才能将k条边构成的图连通。由此也限定了我们应该找到与图中其他边未连通的边（或边的集合）的数目为n-1-k。找到未连通的边aij（或边的集合）后，下一步就应设法找到能将边aij（或边的集合）与图中其他边连接起来并且权值最小的边。也就是在权矩阵里分别找出未连通边aij的脚标i和j对应的行的次非零最小元（前面已经找过每行的非零最小元了），然

最小生成树

后进行比较，选取值较小的元素。该元素所对应的边就是我们要寻找的边。如果是边的集合没有连通，则先将这些边的脚标取并集，然后在权矩阵分别找出该并集中每个脚标所对应行的次非零最小元，比较，取值最小的元素。这样，找到的边与前面k个非零最小元对应的k条边构成的图就是所求的最小生成树。

1.2 算法步骤

Step1：根据图的顶点数n及相应顶点间边的权值形成权矩阵A。其中主对角线元素Aii=0；若顶点i与顶点j不直接相连，Aij=0。若原图未对节点编号，则应先编号。

Step2：在权矩阵A中，按行搜索非零最小元。若某行中有几个非零最小元，则任取其一。记录各行的非零最小元及其脚标，并将权矩阵中对应的该元素赋值为0，其关于对角线对称的元素也应为0，得到新的权矩阵B（这样后面寻找行的次非零最小元就转换成寻找该行的非零最小元了）。比较找到的所有非零最小元，如果同时存在Aij、Aji，则去掉其中一个。统计此时非零最小元的个数k。

Step3：比较k与n-1的大小。若k=n-1，则由这k个元素对应的k条边构成的图即为所求最小生成树。结束。若k﹤n-1，说明这k条边构成的图没有连通，转Step4。

Step4：在剩下的边中寻找权值最小的（n-1-k）条边使k个非零

最小生成树

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

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

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

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

最小生成树

结点的图的一棵生成树。其中：第i个位置的数不能使i+1，且这个数不能与前i-1个数的任意一个相同。

解码方法：排列p中的第i个位置的数为j，则表示的一条边为：从结点j到结点i+1的一条边。如：排列p=（4，5，1，6，2，3）表示的6条边为：4—>2,5—>3,1—>4,6—>5,2—>6,3—>7,也即有7个结点的图的一棵生成树为1—>4—>2—>6—>5—>3—>7。

这种编码策略的优点是：编码长度为问题结点数的线性函数，且可以充分的利用了边之间的信息，编码简单，方便进行插入，删除等操作。

参考文献：

本文来源：https://www.bwwdw.com/article/cu3j.html