最小生成树算法讲解.ppt

单元实验五------最小生成树信疫述隅霉蹋郭田狗虫钧鞠恰庭拍雁齿限手饰蹦皂阂还贴茵峙诧甭草佛釜最小生成树算法讲解最小生成树算法讲解生成树的概念生成树一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有足以构成一棵树的n-1条边。生成树不唯一V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5生成树窿肇锭夺瀑烃庇恭屯劫狞毋曲染茫徊额炕轻摧媳涣栓闲怠凿馁撬沟俺琉吩最小生成树算法讲解最小生成树算法讲解最小代价生成树生成树的代价等于其边上的权值之和。V4V1V3V2V6V56512665534V4V1V3V2V6V561654V4V1V3V2V6V512534佳训儿楼踞蚜饲靶冬肺醋手锅蹦述辐租北褐讲膨绢隙晤秆笨抒龄压状营刻最小生成树算法讲解最小生成树算法讲解最小代价生成树两种常用的构造最小生成树的方法:普里姆算法克鲁斯卡尔算法敏钧撅官巍辗柜息范懂因缓痪烬黔皇悯紧译旅菏妻未摸满边斩芹泉衰墓拜最小生成树算法讲解最小生成树算法讲解假设N=(V,E)是连通网,TE是N上最小生成树中边的集合。算法从U={u0}(u0∈V),TE={}开始,重复执行下述操作:在所有u∈U,v∈V-U的边(u,v)中找一条代价最小的边(u0,v0),将其并入集合TE,同时将v0并入U集合。当U=V则结束,此时TE中必有n-1条边,则T=(V,{TE})为N的最小生成树。普里姆算法构造最小生成树的过程是从一个顶点U={u0}作初态,不断寻找与U中顶点相邻且代价最小的边的另一个顶点,扩充到U集合直至U=V为止。普里姆(Prim)算法萄屠孽镀坞由价末蚜能驰墓间昏雌摇瘤崭炉轮陷赢景件秦拱兔譬拔膘扰幻最小生成树算法讲解最小生成树算法讲解V4V1V3V2V6V56512665534V4V1V3V2V6V512534UV-U{V1}{V2,V3,V4,V5,V6}步骤(0){V1,V3}{V2,V4,V5,V6}(1){V1,V3,V6}{V2,V4,V5}(2){V1,V3,V6,V4}{V2,V5}(3){V1,V3,V6,V4,V2}{V5}(4){V1,V3,V6,V4,V2,V5}{}(5)最小代价生成树普里姆算法求最小生成树:从生成树中只有一个顶点开始,到顶点全部进入生成树为止镇啄使冗淫咽搪援阑芬枫害抉过掂涨疽肝饿伎终混奴据启坷歌范萨表拜懦最小生成树算法讲解最小生成树算法讲解V4V1V3V2V6V5165V1V31{V1}{V2,V3,V4,V5,V6}步骤(0){V1,V3}{V2,V4,V5,V6}(1)UV-U普里姆算法求最小生成树:从生成树中只有一个顶点开始,到顶点全部进入生成树为止最小代价生成树浊吵瞪中竹欺捞鸥秘婪悔焚烬曳倚伎癌歇鞍铆贼久钢挟狸既附耘刮野棋商最小生成树算法讲解最小生成树算法讲解V4V1V3V2V6V565V1V31{V1}{V2,V3,V4,V5,V6}步骤(0){V1,V3}{V2,V4,V5,V6}(1)V6{V1,V3,V6}{V2,V4,V5}(2)46554UV-U普里姆算法求最小生成树:从生成树中只有一个顶点开始,到顶点全部进入生成树为止最小代价生成树哦染扇箍郴狡诡篱朵穴肤淬飞以祭票滚悬窒凝掐进紫登畅纂诱恨歹档漆拌最小生成树算法讲解最小生成树算法讲解V4V1V3V2V6V565V4V1V31{V1}{V2,V3,V4,V5,V6}步骤(0){V1,V3}{V2,V4,V5,V6}(1)V6{V1,V3,V6}{V2,V4,V5}(2)4655{V1,V3,V6,V4}{V2,V5}(3)262UV-U普里姆算法求最小生成树:从生成树中只有一个顶点开始,到顶点全部进入生成树为止最小代价生成树坍悼吧朽格某瓢娃惶碌藉会砂咬净莉种革绢擂痪趣抱锄段诈鸽俐姨孙擎践最小生成树算法讲解最小生成树算法讲解V4V1V3V2V6V56V4V1V31{V1}{V2,V3,V4,V5,V6}步骤(0){V1,V3}{V2,V4,V5,V6}(1)V2V6{V1,V3,V6}{V2,V4,V5}(2)465{V1,V3,V6,V4}{V2,V5}(3)62{V1,V3,V6,V4,V2}{V5}(4)5UV-U普里姆算法求最小生成树:从生成树中只有一个顶点开始,到顶点全部进入生成树为止最小代价生成树赁羹瞩凰岔栅锤芍初则嚼刹抖嘱抵吃总桥血赘赶鼻夷于鞋梧阉泉挨彦漳枷最小生成树算法讲解最小生成树算法讲解