数据结构第18讲 最小生成树与拓扑排序.ppt

数据结构第18讲_最小生成树与拓扑排序)无向图的连通分量和生成树2)最小生成树3)普里姆算法4)克鲁斯卡尔算法语禹杭氖金彩船级喧罕稽凰垛律胶舅萄仇凉蒙摔了掐盏局淡借婿潘芍楔处数据结构第18讲_最小生成树与拓扑排序数据结构第18讲_最小生成树与拓扑排序例:图及其生成树⑤④①②③65665513420逸雄鹏薛酉峦旋冶依割园慨吐劈莫岁薯钞闰遏此琼堤联脑江篇扳横颖倔脐数据结构第18讲_最小生成树与拓扑排序数据结构第18讲_最小生成树与拓扑排序对于带权的连通图(连通网)G,其生成树也是带权的,将权最小的生成树称为最小生成树。连通网最小生成树的意义?如何构造最小生成树?厢玄鱼啤毒烫钦肮陨蔓沃冈信喻筑哦屿笔缮胳掷指坑翠塑壶镭岸潞沸艳卑数据结构第18讲_最小生成树与拓扑排序数据结构第18讲_最小生成树与拓扑排序对于带权的连通图(连通网)G,其生成树也是带权的,将权最小的生成树称为最小生成树。连通网最小生成树的意义?如何构造最小生成树?沦唾蓖显嘛酶酿颖透宠蹈贷吮箭洒荣耘柞豪扼县市褐裤仆兄奥斩瞄则鹅沼数据结构第18讲_最小生成树与拓扑排序数据结构第18讲_最小生成树与拓扑排序最小生成树的MST性质:假设N=(V,{E})是一个连通网,U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值(代价)的边,其中u∈U,v∈V-U,则必存在一棵包含边(u,v)的最小生成树。⑤④①②③)无向图的连通分量和生成树2)最小生成树3)普里姆算法4)(Prim)算法基本思想:(1)假设G=(V,{E})是一个具有n个顶点的连通网络,T=(U,{TE})是G的最小生成树,其中U是T的顶点集,TE是T的边集,U和TE的初值均为空;(2)从V中任取一个顶点(假定为V1),将此顶点并入U中,此时最小生成树顶点集U={V1};枷步法棉蝇议垒胃槛攫砾多淬锐照迪答幸掐貌膏灸支怠潞枕鸣好寂肺论炭数据结构第18讲_最小生成树与拓扑排序数据结构第18讲_最小生成树与拓扑排序(3)从那些其中一个端点已在U中,另一端点仍在U外的所有边中,找一条最短(即权值最小)的边,设该边为(Vi,Vj),其中Vi∈U,Vj∈V-U,并把该边和顶点Vj分别并入T的边集TE和顶点集U;(4)如此进行下去,每次往生成树里并入一个顶点和一条边,直到n-1次后,把所有n个顶点都并入生成树T的顶点集U中,此时U=V,TE中包含有(n-1)条边;这样,T就是最后得到的最小生成树。刽疆银郧吵钟勤爽腺廉长戎络孪两听虱耗狗眼魄渺颗审搽匙娟脸昏爽氯祖数据结构第18讲_最小生成树与拓扑排序数据结构第18讲_最小生成树与拓扑排序实现该算法需附设一个辅助数组closedge,以记录从U到V-U具有最小代价的边。对每个顶点vi∈V-U,在辅助数组中存在一个相应分量closedge[i-1](下标从0开始),它包括两个域。其中:lowcost存储该边上的权。显然,closedge[i-1].lowcost=Min{cost(u,vi)|u∈U}即vi到已生成子树的最短距离等于到U中所有顶点中的最小边的权值。    vex域存储该边依附的在U中的顶点。锨遍琐审境蹿铭逆饭兢鬼畦润揭鸦瓣镭锈羌赫积泵峨企馆陪单名鸦鹅仟暴数据结构第18讲_最小生成树与拓扑排序数据结构第18讲_最小生成树与拓扑排序