武汉软件工程职业学院《数据结构讲义》第18讲 图的最小生成树

第五章 图 第十八讲 图的最小生成树

1．理解并掌握生成树的概念，网络生成树的概念。 2．掌握构造最小生成树的prim算法和kruskal方法。

? 教学重点：

构造最小生成树的prim算法和kruskal方法 ? 教学难点：

生成树的概念及其最小生成树的构造。 ? 授课内容

5.4. 最小生成树

问题背景：

假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢? 分析问题（建立模型）：

可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选择这样一棵生成树，也就是使总的耗费最少。这个问题就是构造连通网的最小代价生成树(MinimumCostSpanningTree)(简称为最小生成树)的问题。一棵生成树的代价就是树上各边的代价之和。

5.4.1 生成树的概念

在一个无向连通图G中，如果取它的全部顶点和一部分边构成一个子图G’，若边集E(G’)中的边刚好将图的所有顶点连通但又不形成环路，我们就称子图G’是原图G的生成树（Spanning tree）。

生成树有如下特点：任意两个顶点之间有且仅有一条路径；如果再增加一条边就会出现环路；如果去掉一条边此子图就会变成非连通图。一个连通图的生成树不一定是唯一的。一个有n 个顶点的完全图，一共存在n(n-2)种不同的生成树。

【例如】对于图5-3-1中的图G，当按深度和广度优先搜索发进行遍历就可以得

到图5-4-1所示的两种不同的生成树，并分别称为深度优先生成树和广度优先生成树。

第五章 图

v0 V2 V5 V6 v0 V1 V1 V2 V3 V4 V3 V4 V5 V6 V7 V7 图5-4-1 生成树示例

5.4.2 网络的最小生成树

如果连通图是一个网络，我们把生成树各边的权值总和称为该生成树的权。并且将权最小的生成树称为最小生成树（Minimum Spanning Tree）。具有n个顶点的连通图的生成树具有n-1条边（少于此边数不可能将各顶点连通，多于此边数则必然要出现环路） 。 【例如】对于图5-4-2（a）所示的网络，可以得到图5-4-2（b）、（c）和（d）三棵生成树，其中（d）就是一棵最小生成树。

V1 V1 V1 6 V2 5 6 V3 5 4 V4 V2 1 6 V3 V4 V2 1 5 V4 3 4 2 V6 3 V5 V3 4 2 V6 V5 V6 V5 网络

（b）权值26 （c）权值16 （d）权值15

图5-4-2 网络及生成树

求网络的最小生成树是一个具有重大实际意义的问题。前面提到，例如要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。可以把n个城市看作图的n个顶点，各个城市之间的通信线路看作边，相应的建设费用作为变得权值，这样就构成了一个网络。由于在n个城市之间，可行路线有（n（n-1））/2条，那么，如何选择其中的n-1条线路（边），使总的建设费用为最小？这就是求该网络的最小生成树问题。 背景知识（突破点）：

构造最小生成树可以有多种算法。其中多数算法利用了最小生成树的下列一种简称为MST的性质：

MST性质： 假设G=(V，{E})是一个连通网，T=(U，{TE})是正在构造的最小生成树。 若边(u，v)是G中一条具有最小权值(代价)的边，其中u ∈U，v∈V-U，则必存在一棵包含 边 (u，v)的最小生成树。 解决方案：

普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法是两个利用MST性质构造最小生成树的算法。下面先介绍普里姆算法。

（1）普里姆（Prim）算法

第五章 图

普里姆算法的基本思想如下：假设G=(V，{E})是连通网，T=(U，{TE})为欲构造的最小生成树。初始时，U={u0}，TE={φ}。重复下述操作：在所有u∈U，v∈V-U的边中，选择一条权值最小的边(u，v)并入TE，同时将v并入U，直到U=V为止。这时产生的TE中具有n-1条边。上述过程中求得的T=(U，{TE})便是G的一棵最小生成树。

[例如]，图5-4-3所示为按普里姆算法构造网的一棵最小生成树的过程，在构造

过程中辅助数组中各分量值的变化如图5-4-4所示。初始状态时，由于U={v1}，则到V—U中各顶点的最小边，即为从依附于顶点1的各条边中，找到一条代价最小的边(u0 ，v0)=(1，3)为生成树上的第一条边，同时将v0 (=v3)并入集合U。然后修改辅助数组中的值。首先将closedge[2].lowcost改为，‘0’，以示顶点u，已并入U。然后，由于边(v3，v2)上的权值小于closedge[1].1owcost，则需修改closedge[1]为边(v3，v2)及其权值。同理修改closedge[4]和closedge[5]依次类推，直到U=V。

图5-4-3普里姆算法构造最小生成树的过程

为了实现普里姆算法，需附设一个辅助数组dge，以记录从U到V-U具有最小权值的边。其数据类型定义如下： typedef struct { Vextype adjvex; int lowcost;

}closedge[VEX_UNM];

dge[i].Lowcost=Min{cost（u，vi）|u∈U } ，

其中cost(u,vi)为边(u,vi)的权。一旦顶点vi并入U，则dge[i].Lowcost置为零；而dge[i].adjvex存储依附于该边的在U中的顶点。

假定连通网Gn用邻接矩阵表示，若两个顶点之间不存在边，则其权值用机内允许的最大数（MAX）表示，例如图5-4-2（a）的邻接矩阵就如图5-4-4所示。普里姆算法如算法5.5所示。算法中调用了两个函数，函数LocatVex确定起始顶点在网中的序号；函数Mininum求出集合V-U中依附于顶点u（u∈U）的权值最小的顶点的序号。图5-4-5则展示了在图5-4-3所示构造最小生成树的过程中，辅助数组dge中各分量值的变化情况。

第五章 图

图5-4-5 构造最小生成树过程中辅助数组中各分量的值 算法5.7

int LocatVex(Mgraph Gn, Vextype u0); int Mininum( closedge dge);

void PRIM(Mgraph Gn, Vextype u0){

/*从顶点u0出发构造网Gn的最小生成树T，输出T的个条边*/ closedge dge;

k=LocatVex(Gn,u0); /*确定顶点u0在网Gn中的序号*/ for(j=0;j

dge[j].adjvex=u0;

dge[j].lowcost=Gn.arcs[k][j]; }

dge[k].lowcost=0; /*初始U={u0}*/ for(i=0;i

k=Mininum(dge); /*求权值最小的顶点， vk∈V-U*/ /*输出生成树T的边及权值*/

printf(dge[k].adjvex,Gn.vexs[k], dge[k].lowcost); dge[k].lowcost=0; /*顶点vk并入U*/ for(j=0;j

第五章 图

dge[j].adjvex=Gn.vexs[k]; }/*if*/ }

}/*PRIM*/

/*返回顶点u0在网Gn中的序号*/ int i;

for(i=0;i

}/* LocatVex*/

int Mininum( closedge dge){

/* 在辅助数组dge中求出权值最小的顶点序号i，且vi∈V-U*/ for(i=0;i

if( dge[i].lowcost!=0) break; min=i;

for( i=0;i

if( dge[i].lowcost!=0 && dge[i].lowcost

return min; }/* Mininum*/

假使网中有n个顶点，则普里姆算法的时间复杂度为O(n2)，它与网的边的数目无关，因此普里姆算法适合于求边稠密的网的最小生成树。 （2）克鲁斯卡尔算法

另一种构造最小生成树的算法是按权值递增的次序来构造，由Kruskal与1956年提出的。

其基本思想：假设G =（V，E，W）是一个具有n个顶点的连通网络，最小生成树 T=(U,TE)是G 的最小生成树，U的初值等于V，即包含有G中的全部顶点，TE的初值为空集。将图G中的边（u，v）按权值从小到大的顺序依次选取，若选取的边使生成树T不形成环路，则把它并入TE中，保留作为生成树T的一条边，若选取的边使生成树T形成环路，则将其舍弃，如此进行下去，直到TE中包含n-1条边为止。此时的T即为最小生成树。 此算法可简单描述如下： T=（V，{φ}）；

while(T中所有边数e

从E中选取当前最短边（u，v）； if（（u，v）并入T之后不产生回路） 将边(u,v)并入T中； 从E中删除去边（u，v）； } [例如]，对图5-4-2（a）中的网，利用克鲁斯卡尔算法，将输出生成树上的五

条边为：{(v1,v3), (v3,v6), (v6,v4), (v3,v2), (v2,v5)}。 用Kruskal算法得到最小生成树的过程

第五章 图

图5-4-6 克鲁斯卡尔算法构造最小生成树的过程

克鲁斯卡尔算法的时间复杂度为O(eloge)(e为网中边的数目)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。

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