数据结构第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讲_最小生成树与拓扑排序