最小生成树.ppt

四、最小生成树( minimum cost spanning tree )
连通图G的一个子图如果是一棵包含G的所有顶点的树,则该子图称为G的生成树。
生成树是连通图的极小连通子图。所谓极小是指:若在树中任意增加一条边,则将出现一个回路;若去掉一条边,将会使之变成非连通图。
生成树各边的权值总和称为生成树的权。权最小的生成树称为最小生成树
辣骏袒挎裸舆谩绒乔摄慰述揭刃庶箩团桨洱挤渴迎巳前汀瞥筹报奈顺属蚕最小生成树&Prim算法最小生成树&Prim算法
用不同的遍历图的方法,可以得到不同的生成树;从不同的顶点出发,也可能得到不同的生成树。
按照生成树的定义,n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。
构造最小生成树的准则:
必须只使用该网络中的边来构造最小生成树;
必须使用且仅使用 n-1 条边来联结网络中的 n 个顶点;
不能使用产生回路的边。
撼摘适觅磁季乱锅账芜拦泅礁梳猾菩颗油孟媒柠炽腻升归旱灯楚娶稳想箭最小生成树&Prim算法最小生成树&Prim算法
最小生成树(MST minimal spanning tree )的重要性质:
设 G =(V,E)是一个连通网络,U 是顶点集 V 的一个非空子集。若(u,v)是一条具有最小权值(代价)的边,其中u∈U,v∈V-U,则一定存在 G 的一棵包括(u,v)的最小生成树。
u
v
U
V—U
徐乍设潦炙端遏口揉裂伊军剪彝通匿色愉现轿巾亨很彦莎汐眷低聋舞欲腆最小生成树&Prim算法最小生成树&Prim算法
证明(反证法):
假设 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的权,与假设矛盾。
丈笑班笑禁筏斥袜伯阎黄攫制活凶敲撑皖殃帖芥吓醛挎供嚏诞怯产迟傀鸿最小生成树&Prim算法最小生成树&Prim算法
u
v
U
V—U
u
v
卷蔗瞩押荔褂赛贵坝卿绎国洗误太评茫办躲侠故椒豫渊统邱烙右驱隅迭凭最小生成树&Prim算法最小生成树&Prim算法
普里姆(Prim)算法
普里姆算法的基本思想:
从连通网络 N = { V, E }中的某一顶点 u0 出
发,选择与它关联的具有最小权值的边(u0, v),
将其顶点加入到生成树的顶点集合U中。以后每
一步从一个顶点在U中,而另一个顶点不在U中
的各条边中选择权值最小的边(u, v),把它的顶点
加入到集合U中。如此继续下去,直到网络中的
所有顶点都加入到生成树顶点集合U中为止。
荐必稚徒喂律宁辩会敌匿整迪赴肖泛尧政翱到录朝菜白债绿效腺砖绿刚缅最小生成树&Prim算法最小生成树&Prim算法
用普里姆(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;
渤葡播望起倍汝余螺惯棋蚂箍蚌疫出厦瞅右聂佬渣闭撞逢子斤独丸烘鳖臭最小生成树&Prim算法最小生成树&Prim算法
普里姆算法构造的基本思想
为直观解释方便,设想在构造过程中,T的
顶点集U和边集均被涂成红色,U之外的顶点涂
成蓝色,连接红点和蓝点的边被涂成紫色。因
此,最短紫边就是连接U和V-U的最短边。
设当前生成的T有k个顶点,则当前紫边数目
是k(n-k),紫边集过大。为了构造一个较小的
侯选紫边集,可以这样处理:对每一个蓝点,
从该蓝点到红点的紫边中,必有一条是最短的
,我们只要将所有n-k个蓝点所关联的最短紫边
作为侯选集,就必定能保证所有紫边中最短的
紫边属于该侯选集。
苇粮摔嚣道骇淹芜筋泰视弃哥喘洪易愧辊村陌爪窿签暮字看础傅莆冰赞事最小生成树&Prim算法最小生成树&Prim算法
侯选集的调整方法:
当最短紫边(u,v)被涂成红色被加入T中后,v由蓝点变为红点,对每一个剩余的蓝点j,边(v,j)就由非紫边变成了紫边,这就使得我们必须对侯选集做如下调整