最小生成树Prim算法PPT学习教案.pptx

会计学
1
最小生成树Prim算法
用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。
按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。
构造最小生成树的准则：
必须只使用该网络中的边来构造最小生成树；
必须使用且仅使用 n-1 条边来联结网络中的 n 个顶点；
不能使用产生回路的边。
第1页/共12页
最小生成树（MST minimal spanning tree ）的重要性质：
设 G =（V，E）是一个连通网络，U 是顶点集 V 的一个非空子集。若（u，v）是一条具有最小权值（代价）的边，其中u∈U,v∈V-U,则一定存在 G 的一棵包括（u，v）的最小生成树。
u
v
U
V—U
第2页/共12页
证明（反证法）：
假设 G 中任何一棵最小生成树中都不包含(u，v)。设T是一棵最小生成树但不包含(u，v)。由于T是最小生成树，所以 T 是连通的，因此有一条从u到v的路径，且该路径上必有一条连接两个顶点集 U、V 的边(u，v)，其中u∈U，v∈V-U。当把边(u，v)加入到 T 中后，得到一个含有边(u，v)的回路。删除边(u，v)，上述回路即被消除。由此得到另一棵生成树 T， T 和 T 的区别仅在于用边(u，v)代替了(u，v)。由于(u，v)的权<=(u，v)的全权，所以， T的权<=T的权，与假设矛盾。
第3页/共12页
u
v
U
V—U
u
v
第4页/共12页
普里姆(Prim)算法
普里姆算法的基本思想：
从连通网络 N = { V, E }中的某一顶点 u0 出
发，选择与它关联的具有最小权值的边(u0, v)，
将其顶点加入到生成树的顶点集合U中。以后每
一步从一个顶点在U中，而另一个顶点不在U中
的各条边中选择权值最小的边(u, v),把它的顶点
加入到集合U中。如此继续下去，直到网络中的
所有顶点都加入到生成树顶点集合U中为止。
第5页/共12页
用普里姆(Prim)算法构造最小生成树的过程
1
2
3
4
6
5
5
6
5
1
7
3
2
5
4
6
1
2
3
4
6
5
5
1
3
2
4
从节点①开始，选最小权值的边1，节点（①，③）入U;
从U中选最小权值边5，且对应节点不在U中，②入U;
从U中选最小权值边3，且对应节点不在U中， ⑤入U;
从U中选最小权值边4，且对应节点不在U中， ⑥入U;
从U中选最小权值边2，且对应节点不在U中， ④入U;
第6页/共12页
普里姆算法构造的基本思想
为直观解释方便，设想在构造过程中，T的
顶点集U和边集均被涂成红色，U之外的顶点涂
成蓝色，连接红点和蓝点的边被涂成紫色。因
此，最短紫边就是连接U和V-U的最短边。
设当前生成的T有k个顶点，则当前紫边数目
是k(n-k)，紫边集过大。为了构造一个较小的
侯选紫边集，可以这样处理：对每一个蓝点，
从该蓝点到红点的紫边中，必有一条是最短的
，我们只要将所有n-k个蓝点所关联的最短紫边
作为侯选集，就必定能保证所有紫边中最短的
紫边属于该侯选集。
第7页/共12页
侯选集的调整方法：
当最短紫边(u,v)被涂成红色被加入T中后，v由蓝点变为红点，对每一个剩余的蓝点j，边(v,j)就由非紫边变成了紫边，这就使得我们必须对侯选集做如下调整：若侯选集中蓝点j所关联的原最短紫边长度大于新紫边(v,j)的长度，则以(v,j)作为j所关联的新的最短紫边来代替j的原最短紫边，否则j的原最短紫边不变。
第8页/共12页
Prim 算法的结构如下：
(1) 置T为任意一个顶点，置初始侯选紫边集；
(2) while ( T中顶点数目<n)
(3) { 从侯选紫边集中选取最短紫边(u,v);
(4) 将 (u,v) 及蓝点 v 涂成红色，扩充到 T 中；
(5) 调整侯选紫边集；
(6) }
第9页/共12页