7.4.1 普里姆算法在线视频

同学们大家好

我是云南大学信息学院教师孔兵

这节课我们讨论最小生成树的问题

最小生成树是在连通网上考虑的

也就是带权的无向连通图

先看一个引例

假设要在n个城市之间建立通信联络网

则连通n个城市只需要n-1条线路

每条线路有建设的代价

不同线路，建设的代价是不同的

那么在所有可能的n(n-1)/2条线路中

挑选那n-1条线路就是一个问题

比如说我们考虑最省钱的方案

希望这n-1条线路能保证所有顶点连通

并且总的造价最低

这就是最小生成树要解决的问题

最小生成树的定义是，连通网的最小代价生成树

所谓生成树的代价是树上各边的代价之和

求最小生成树的方法有很多

主要都是是基于最小生成树性质

也叫MST性质

MST性质是说，假设N是一个连通网

顶点集是V，边集是E，U是顶点集V的一个非空子集

若(u, v)是一条具有最小权值或者说代价的边

其中u∈U，v∈V-U

则必存在一棵包含边(u, v)的最小生成树

MST性质的含义是说

如果把连通网中的顶点

任意剖分为两个集合，其中一个集合是U

那么另一个集合就是V-U

如果有一条边(u, v)

边一端的顶点在集合U中，另一端的顶点在V-U中

并且(u, v)是一端在U一端在V-U的所有边中代价最小的

那么必存在一棵包含边(u, v)的最小生成树

下面我们结合图示来证明一下

证明的方法是反证法

假设网N的任何一棵最小生成树都不包含边(u, v)

设T是连通网上的一棵最小生成树

我们仍然把T中的顶点看作U和V-U两个集合

因为T是生成树，那么在T中

顶点u和顶点v之间必然有一条路径

这条路径从大U中的顶点u中到V-U中的顶点v

那么这条路径中，必定有一条边

其一端在U一端在V-U，设这条边为（u’，v’）

其中u’属于U，v’属于V-U，如图左边红色边所示

我们对最小生成树T做一个变换

在T中删除（u’，v’）这条边

增加(u, v)这条边，其它不变

变换后的树称为T’，如图右边所示

T’仍然是有n-1条边，删一条增一条

那么，T’是生成树吗？

我们只需要说明，T’仍然是连通的就可以了

考虑T’任意两个顶点

如果在T中它们之间的路径不经过（u’，v’）

那么在T’中它们之间仍然有路径

如果在T中它们之间的路径经过（u’，v’）

那么在T’中，可以通过u’, u, v, v’来连通

因此T’是生成树，根据(u, v)的性质

T’的代价小于等于T，所以T’是一棵最小生成树

和假设矛盾

文字的证明过程同学们参看教材

下面介绍求最小生成树的第一个算法---普里姆算法

看一下算法的描述

TE是已生成的最小生成树中边的集合

U是已生成的最小生成树中顶点的集合

普里姆算法采用的是构造法

从一个顶点开始，逐步构造出一颗最小生成树

算法分为三步

第一步，U={u0}(u0∈V), TE={ }

其中u0是构造的出发点，TE是空集，完成初始化

第二步，在所有u∈U, v∈V-U的边(u, v)∈E中

找一条代价最小的边(u0,v0)并入TE

同时v0并入U，完成一步构造

第三步， 当U≠V时，重复执行第二步

若U=V，表示构造完成，获得了一棵最小生成树

可能同学们注意到了

普里姆算法是对MST性质的直接应用

普里姆算法实现的关键问题

有这样两个，一是找出一端属于U

一端V-U的所有边

二是在这些边里确定代价最小的边

确定代价最小的边很容易

找一端属于U，一端V-U的所有边有些麻烦

难点是随着构造过程，U和V-U是变化的

假设从顶点v1开始构造，初始的时候

大U中只有一个顶点v1，TE是空

v2到v6都在V-U中

一端在U一端在V-U的边共有三条

(v1,v2), (v1,v3),(v1,v4)，按算法找出代价最小的

是(v1,v3)，把(v1,v3)加入到TE中

顶点v3加入大U。这个时候大U发生了变化

当然V-U肯定也发生了变化

那么一端在U一端在V-U的边需要重新寻找

为了适应这样的变化

我们关注的是V-U中的每个顶点到U中顶点的最小代价边

如果已知这些最小代价边

那么其中最小的就是一端在U一端在V-U的最小代价边

下面我们一个通过例子来看一下普里姆算法执行过程

观察图1

算法的核心是通过一个一维的closedge数组记录

每个V-U中的顶点到U中顶点的最小代价边

数组的大小和存储顶点的一维数组相同

在这里，我们设v1到v6的6个顶点存储位置是0~5

数组的每个元素是一个结构体

结构体中有两个成员，一个成员lowcost

这里简写为low

用来记录该顶点到U中顶点的最小代价边

另外一个成员adjvex，这里简写为adj

用来记录这条最小代价边

所依附的U中的顶点是哪个

观察一下图1中的closedge

0号单元对应的是顶点v1，因为v1是属于大U的

那么对应的low为0，说明这是大U当中的顶点

也是目前大U当中唯一的一个顶点

1单元对应的是顶点v2，因U中只有一个顶点v1

v2到v1的边就是目前v2到大U中顶点的最小边

代价low是6，依附的顶点adj是v1

同样地，v3的最小边是(v1,v3)，代价是1

v4的最小边是(v1,v4)，代价是5

v5,v6没有到v1的边，那么代价就是无穷

所有边依附的顶点都是v1

图1中就closedge初始的状态

记录了目前每个V-U中的顶点到U中顶点最小代价边的情况

按照普里姆算法第2步，需要找出一端属于U

一端V-U的代价最小的边，基于closedge数组

只要找low非零最小的一个就可以了

现在，我们可以找到2号单元记录的v1到v3的这一条边

代价是1

按照算法，把(v1,v3)加入TE

v3加入到大U当中

观察图2

现在U增加了顶点v3

V-U就是剩下的v2v4v5v6

大U发生了变化

因为新的一个顶点v3的加入

我们需要重新考察

V-U中的顶点到新加入的v3之间是否有边

如果有的话，这条边的代价是不是

比原来记录的最小代价边还要小

如果是的话，closedge数组中的相关单元需要更新

考察v2到v3，边是5，原来v2到U的最短边是6

比原来的小，需要更新

更新以后，v2到U的最短边长度是5

依附的U中的顶点是v3

考察v4到v3，长度是5，它原来的最短边也是5

不必更新。v5v6，他们原来的最短边都是无穷

现在更新为6和4，依附的大U中的顶点都是v3

更新后数组的情况如图2中所示

图3图4是后续步骤图示

其中红色的边是被挑选出加入TE的边

最后一条构造的边是v2到v5这一条

图6中是我们最终构造出的最小生成树

此时U=V，算法结束

顶点加入U的次序是v1，v3，v6，v4，v2，v5

数组closedge的两个成员前面做过说明，这里就不重复了

下面我们看一下普利姆算法的程序实现

涉及到的参数有两个

一个是以数组表示法存储的图G

一个是构造的出发点u

算法中首先定义了closedge数组

绿色框中是算法的初始化

k=LocateVex(G, u)，确定出发点u的存储位置

赋值给k

随后用for循环对closedge数组进行初始化

每次循环考察一个顶点j

当j不是我们出发点的时候

把j到k的代价

和u赋值给closedge数组的j号单元

完成初始化

把出发点的lowcost赋值0，表示是大U中的顶点

随后的for循环中，每次循环我们在基于closedge数组

调用minimal函数找出一条一端在U一端在V-U代价最小的边

并把该边对应的V-U中顶点的位置返回赋值给k

printf把这条边在屏幕输出，k对应的lowcost赋值0

表示顶点k加入大U集合中

k加入到大U以后

黄色框中的循环依次处理V-U中的顶点

考察该顶点到新加入的k之间边的代价

如果代价比原来的最小代价边还要小

则更新

前面结合例子详细讨论过

这里不重复了

普里姆算法的时间复杂度是O(n2)

主要是两个嵌套的for循环语句

同学们，最小生成树我们先讨论到这

下次课再见