最小生成树Kruskal算法.pdf

一、题目描述： 如图所示的赋权图表示某七个城市及预算它们之间的一些某些直接通信道路造价（单 位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小并计算其最 小值。 二、题目分析： 该题即要求赋权图的最小生成树，即可使得各城市间互相通信又使造价费用最小。 1. 1. 11..生成树及最小生成树定义 (1)生成树的定义入下： 对于有n个顶点的无向连通图G，把遍历过程中顺序访问的两个顶点之间的路径记录下 来，这样G中的n个顶点以及由出发点一次访问其余n-1个顶点所经过的n-1 条边就构成了 G的极小连通子图，也就是G的一棵生成树，出发顶点是生成树的根。 (2)下面给出最小生成树的概念： 给定一个连通网络，要求构造具有最小代价的生成树时，也即使生成树的各边的权值总 和达到最小。把生成树各边的权值总和定义为生成树的权，那么具有最小权值的生成树就构 成了连通网络的最小生成树。 2. 2. 22..最小生成树的性质 构造最小生成树的算法有很多种，其中大多数的算法都利用了最小生成树的一个性质， 简称为MST性质：假设G=（V，E）是一个连通网络，U是V 中的一个真子集，若存在顶 点u∈U和顶点v∈(V−U)的边(u，v)是一条具有最小权值的边，则必存在G 的一棵最小 生成树包括这条边(u，v)。 3. 3. 33..常用算法及思想 利用该性质构造最小生成树的常用算法主要有：Prim(普里姆)算法和Kruskal(克鲁斯卡 尔)算法。 (1)Prim算法思想： 设G=（V,E）是一个有n个顶点的连通图，用T=(U，TE)表示要构造的最小生成树，其 中U为顶点集合，TE 为边的集合。则Prim 算法的具体步骤描述入下： �初始化：令U={Ø}，TE={Ø}。从V 中取出一个顶点u 放入生成树的顶点集U中，作为 0 -1 - 第一个顶点，此时T= ({u },{φ})； 0 � * * 从 ， 的边(u，v)中找一条代价最小的边(u ,v )，将其放入TE 中，并 u∈U v∈(V−U) * 将 放入U中； v �重复步骤（2），直至U=V 为止。此时集合TE中必有n-1 条边，T即为所要构造的最小生 成树。 (2)Kruskal 算法思想： 设G=（V,E）是一个有n个顶点的连通图，则令最小生成树的初始状态为只有n个顶点 而无任何边的非连通图T={V,{Ø}},图中每个顶点自成一个连通分量。依次选择E 中的最小 代价边，若该边依附于T 中的两个不同的连通分量，则将此边加入到T 中；否则，舍去此 边而选择下一条代价最小的边。以此类推，直到 T 中所有顶点都在同一连通分量上为止。 这时的T 就是G的一棵最小生成树。 三、方案解决： 在本题中我们将采用Kruskal 算法来构造最小生成树。 从题目所给赋权图中我们可以得到该图的邻接矩阵为： ⎡ 0 20 0 0 0 23 1 ⎤ ⎢ ⎥ ⎢20 0 15 0 0 0 4 ⎥ ⎢ 0 15 0 3 0 0 9 ⎥ ⎢ ⎥ G= ⎢ 0 0 3 0 17 0 16⎥ ⎢ 0 0 0 17 0 28 25⎥ ⎢ ⎥ ⎢23 0 0 0 28 0 36⎥ ⎢ 1 4 9 16 25 36 0 ⎥ ⎣ ⎦ 我们将题中的赋权图中i,j两个城市之间的造价费用边记为 ，则从小到大排序如下： S ij 顺序 1 2 3 4 5