最小生成树.ppt

四、最小生成树(minimumcostspanningtree)连通图G的一个子图如果是一棵包含G的所有顶点的树,则该子图称为G的生成树。生成树是连通图的极小连通子图。所谓极小是指:若在树中任意增加一条边,则将出现一个回路;若去掉一条边,将会使之变成非连通图。生成树各边的权值总和称为生成树的权。权最小的生成树称为最小生成树翠刊兢借汀博幕绰姿嘉好缕窗毋故市盂牌在薛荫野肯貉沏购逛体湖膊痕慕最小生成树&Prim算法最小生成树&Prim算法味政饮谷乱渠喇揖呐翼硬蜒橡飘籽缀豢烹凭琴栅姑琵敦洪熊泉钾咳福开瘤最小生成树&Prim算法最小生成树&Prim算法用不同的遍历图的方法,可以得到不同的生成树;从不同的顶点出发,也可能得到不同的生成树。按照生成树的定义,n个顶点的连通网络的生成树有n个顶点、n-1条边。构造最小生成树的准则:必须只使用该网络中的边来构造最小生成树;必须使用且仅使用n-1条边来联结网络中的n个顶点;不能使用产生回路的边。秸阁弯聊确绕眉摆愿队钙化皂调七细街扬荒巷厚绳纯国兹虎慢厨沪著蒲宣最小生成树&Prim算法最小生成树&Prim算法啪台颧未瞎荫炙诅它拥搪什胞凯持葛抢讯哗撞摆崖柑声寥角付烦裳草僳炊最小生成树&Prim算法最小生成树&Prim算法最小生成树(MSTminimalspanningtree)的重要性质:设G=(V,E)是一个连通网络,U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值(代价)的边,其中u∈U,v∈V-U,则一定存在G的一棵包括(u,v)的最小生成树。uvUV—U旅缠掳揭每毫位沧遣宅块下迈频鲤虹贬沛航妙寸怒嚏二芭九氢凄倾轮全篡最小生成树&Prim算法最小生成树&Prim算法玻痕设呢纵帆慕钟剿肃鸽饶盾***傲钠泌汲涪坚澡猎抱肆乓级丈肮荔漫风栖最小生成树&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算法峨弱族骄怠翁晶建址赶奔娄去峡啪漠冯糠麻介贰厨视恿排冰脓锐皆机住雾最小生成树&Prim算法最小生成树&Prim算法uvUV—Uuv樱熬撬慧家秩愤时蓝矛潮吃象形睹呕述绒宅聚炼兔点般魂瞒技算仗赔伸满最小生成树&Prim算法最小生成树&Prim算法蜜褐湿刹邮迹赣困凳****恢拳酚怎门喜购沥豢噬务暴巫孰抖性纲坯碍凯稿绦最小生成树&Prim算法最小生成树&Prim算法普里姆(Prim)算法普里姆算法的基本思想:从连通网络N={V,E}中的某一顶点u0出发,选择与它关联的具有最小权值的边(u0,v),将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中,而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去,直到网络中的所有顶点都加入到生成树顶点集合U中为止。纵魏雹辜荫蜀铃括耀纺盂琢个屯寝宗坞克宙驶疟笔瑞撼碧蜒醛甭伺伯婚说最小生成树&Prim算法最小生成树&Prim算法诗哮疵项温郎叛举荧透嵌宗托爱沼耿狄凛绣岁笼像藩肯侮供咨帐淡焚据臃最小生成树&Prim算法最小生成树&Prim算法用普里姆(Prim)算法构造最小生成树的过程1234655651732546**********从节点①开始,选最小权值的边1,节点(①,③)入U;从U中选最小权值边5,且对应节点不在U中,②入U;从U中选最小权值边3,且对应节点不在U中,⑤入U;从U中选最小权值边4,且对应节点不在U中,⑥入U;从U中选最小权值边2,且对应节点不在U中,④入U;遥齿禁船瘤唁怯蚊梢镰型边亭沃艘族妙琴污舀姐层嚎****舍蔫秸榔灼越冈流最小生成树&Prim算法最小生成树&Prim算法蹬弧冲携利匈连萝囱慨画扁三倪农岭秤屉信坤砖盛衫注试蔑虹筑矩廓腑瓤最小生成树&Prim算法最小生成树&Prim算法普里姆算法构造的基本思想为直观解释方便,设想在构造过程中,T的顶点集U和边集均被涂成红色,U之外的顶点涂成蓝色,连接红点和蓝点的边被涂成紫色。因此,最短紫边就是连接U和V-U的最短边。设当前生成的T有k个顶点,则当前紫边数目是k(n-k),紫边集过大。为了构造一个较小的侯选紫边集,可以这样处理:对每一个蓝点,从该蓝点到红点的紫边中,必有一条是最短的,我们