最小生成树算法讲解

单元实验五------最小生成树生成树的概念生成树一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的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普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止最小代价生成树V4V1V3V2V6V5V4V1V31｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)V2V6V5｛V1,V3,V6｝｛V2,V4,V5

｝(2)46｛V1,V3,V6,V4

｝｛V2,V5

｝(3)62｛V1,V3,V6,V4,V2

｝｛V5

｝(4)5｛V1,V3,V6,V4,V2,V5

｝｛｝(5)33UV-U普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止最小代价生成树普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止V4V1V3V2V6V5V4V1V31｛V1

｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)V2V6V5｛V1,V3,V6｝｛V2,V4,V5

｝(2)4｛V1,V3,V6,V4

｝｛V2,V5

｝(3)2｛V1,V3,V6,V4,V2

｝｛V5

｝(4)5｛V1,V3,V6,V4,V2,V5

｝｛｝(5)3UV-U最小代价生成树普里姆(Prim)算法生成树中只放置一个顶点在关联生成树顶点的边中（即边的一个顶点在生成树中，另一个顶点不在）取权值最小者将选中的边加入生成树，同时将该边的关联顶点加入生成树中生成树中顶点数小于n?是否结束开始基本要求从键盘（或数据文件）输入图的信息，用普里姆算法求解给定无向连通图的最小生成树，最后输出最小生成树中的权值和所有的边，图的存储结构自行设定。例如下图的输出为weight：15(v1,v3)(v3,v6)(v6,v4)(v3,v2)(v2,v5)或者(1,3)(3,6)(6,4)(3,2)(2,5)顶点集合如何表示？最小边如何选择？一个顶点加入U集合（生成树中）如何表示？struct{intadjvex;doublelowcost;}closedge[MAX_VERTEX_NUM];closedge[i].adjvex=kclosedge[i].lowcost顶点i与顶点k邻接顶点k已经在U集合中顶点i加入U集合时普里姆算法的实现=0adjvexlowcostv16v11v15

{v1}{v2,v3,v4,v5,v6}3v2v3v4v5v6UV-Uk顶点iclosedgecl惕os填ed哲ge甚[2哲].详ad下jv忙ex纱=1.lo智wc诱os惹t=6cl袋os脑ed番ge持[3犹].殖ad蜻jv申ex叉=1.lo摆wc茂os滚t=1cl碎os枪ed摊ge桑[4庆].勾ad拨jv坛ex冒=1.lo成wc嗽os搭t=5V4V1V3V2V6V5165当U集合驻中加差入一流个新误顶点胳时，V-珍U集合巧中的鹿顶点贸到U的最瓜小代镜价边雀可能佣会更衬新V4V1V3V2V6V56512665534U集合拐的成率员：V-亿U集合供的成晕员：cl迈os格ed既ge缺[5].京ad谈jv片ex疤=1.lo屈wc粮os楚t=∞cl悠os慎ed伟ge坏[6].船ad就jv枣ex巨=1.lo们wc衣os亩t=∞adjvexlowcostv16v11v15

{v1}{v2,v3,v4,v5,v6}3adjvexlowcostv350v15v36v34{v1,v3}{v2,v4,v5,v6}6v2v3v4v5v6UV-Uk顶点iclosedgeV4V1V3V2V6V55564U集合铅的成秩员：V-拐U集合挖的成县员：当U集合属中加故入一幼个新焰顶点副时，V-顾U集合柄中的唇顶点骑到U的最帽小代挑价边恐可能免会更次新V4V1V3V2V6V56512665534cl前os丙ed券ge礼[2].弦ad危jv抽ex哀=3.lo左wc芝os告t=5cl要os邮ed贩ge换[4落].久ad偿jv茎ex辫=1.lo觉wc阀os纱t=5cl不os仓ed烛ge首[5].症ad啄jv姨ex疾=3.lo舞wc梢os贞t=6cl答os滨ed撇ge制[6].埋ad所jv奥ex削=3.lo亦wc普os岁t=4adjvexlowcostv16v11v15

{v1}{v2,v3,v4,v5,v6}3adjvexlowcostv350v15v36v34{v1,v3}{v2,v4,v5,v6}6adjvexlowcostv350v62v360{v1,v3,v6}{v2,v4,v5}4v2v3v4v5v6UV-Uk顶点iclosedgeV4V1V3V2V6V5562V4V1V3V2V6V56512665534当U集合勒中加沿入一炒个新台顶点记时，V-街U集合椅中的说顶点爆到U的最场小代锋价边荣可能灾会更抓新U集合越的成老员：V-扶U集合插的成切员：cl沸os且ed辱ge毒[2].棉ad乏jv帅ex围=3.lo学wc抗os轰t=5cl写os捏ed妨ge源[4].摔ad翻jv肤ex惯=6.lo描wc谅os逼t=2cl它os柜ed沸ge叮[5].载ad鹊jv至ex芬=3.lo末wc您os瘦t=6adjvexlowcostv16v11v15

{v1}{v2,v3,v4,v5,v6}3adjvexlowcostv350v15v36v34{v1,v3}{v2,v4,v5,v6}6adjvexlowcostv350v62v360{v1,v3,v6}{v2,v4,v5}4adjvexlowcostv3500v360{v1,v3,v6,v4}{v2,v5}v2v3v4v5v6UV-Uk顶点iclosedge2V4V1V3V2V6V556当U集合守中加厦入一舞个新屋顶点柴时，V-志U集合唉中的装顶点边到U的最侮小代芳价边馒可能般会更管新U集合池的成惧员：V-旋U集合还的成钱员：V4V1V3V2V6V56512665534cl就os脊ed慢ge携[2].赢ad沃jv植ex努=3.lo轮wc横os副t=5cl堤os在ed律ge侍[5].贫ad狗jv岩ex卫=3.lo裂wc跟os近t=6adjvexlowcostv16v11v15

{v1}{v2,v3,v4,v5,v6}3adjvexlowcostv350v15v36v34{v1,v3}{v2,v4,v5,v6}6adjvexlowcostv350v62v360{v1,v3,v6}{v2,v4,v5}4adjvexlowcostv3500v360{v1,v3,v6,v4}{v2,v5}2adjvexlowcost000v230{v1,v3,v6,v4,v2}{v5}v2v3v4v5v6UV-Uk顶点iclosedge5V4V1V3V2V6V53当U集合排中加宁入一景个新盼顶点扩时，V-捐U集合甩中的纠顶点聚到U的最授小代静价边健可能系会更于新V4V1V3V2V6V56512665534U集合终的成陈员：V-机U集合涨的成宰员：adjvexlowcostv16v11v15

{v1}{v2,v3,v4,v5,v6}3adjvexlowcostv350v15v36v34{v1,v3}{v2,v4,v5,v6}6adjvexlowcostv350v62v360{v1,v3,v6}{v2,v4,v5}4adjvexlowcostv3500v360{v1,v3,v6,v4}{v2,v5}2v2v3v4v5v6UV-Uk顶点iclosedgeV4V1V3V2V6V5adjvexlowcost00000{v1,v3,v6,v4,v2,v5}{}

adjvexlowcost000v230{v1,v3,v6,v4,v2}{v5}514253U集合五的成增员：V-嚷U集合顿的成您员：V4V1V3V2V6V56512665534普里舌姆算症法求蹲最小汗生成镰树∞615∞∞6∞5∞3∞15∞5645∞5∞∞2∞36∞∞6∞茅∞42些6∞1234561滥2口3伍4倾5果6图采往用邻词接矩纵阵表萄示G.搬ar诵cs给[]酸[]符=#d础ef青in愧eMa舌xV谨nu肥m50ty哀pe励de车fin坝tAd睛jM烈at夺ri胶x[M锈ax禾Vn戚um斥][银Ma酿xV屠nu窑m];虫/母/d断ou早bl求ety判pe存de胡fst请ru慰ct{in胀tve朵xn视um丹,a较rc间nu铺m;存//顶点己数、义边数Ad欠jM章at底ri为xar辩cs言;垫/殃/邻接紧矩阵}G洪ra暗ph虽;Gr竞ap振h恰G;vo籍idMi碎ni辣Sp常an雁Tr麦ee累_P怀RI谋M(G咬ra阶ph辩G客,in辅tu)终{//用普钥里姆院算法黎从顶叮点u出发乳构造G的最饥小生佩成树fo烤r(贿j=挤0;纠j取<G.叹ve优xn宽um;猪++拌j)//辅助婚数组株初始本化if谎(朋j大!孤=醉u炮)cl奶os蛋ed始ge紫[j]善=洋{u目,G.利ar逼cs浊[u益][祥j]}船;st篮ru诵ct{in煮tad司jv膝ex;do拼ub拼lelo吐wc狐os吵t;}cl匙os金ed超ge掘[M纹AX庙_V左ER首TE鉴X_细NU只M];cl漆os头ed舒ge我[u棒].葵lo灿wc壤os掩t=藏0;//初始,U屠={编u}fo滋r(恋i=其1;薪i阅<G.动ve扒xn泄um;寺++烛i)怒{k侮=mi响ni奇mu巨m(帽cl针os垂ed无ge);//求生释成树块的下家一个者顶点kco戒ut<<cl轿os桑ed与ge瓣[k态].吼ad伤jv挡ex<<G.铺ve净xs果[k];cl醉os受ed浓ge娱[k焦].悔lo殊wc混os劝t=保0;fo雷r(票j=窄0;搏j盯<G.猛ve加xn恢um;牲++乒j)if怒(G.纳ar颈cs伞[k睡][敢j]价.a欠dj<cl幅os炉ed叶ge脂[j验].块lo制wc涨os厌t)cl号os建ed籍ge葬[j]枝=恨{G.型ve齿xs饲[k],G.孝ar咽cs徐[k德][榜j]绒.a杆dj};}/暖/f飞or}/微/Mi横ni茫Sp暮an健Tr异ee新_P尺RI奥Mk离=mi兰ni舱mu当m(龙cl退os妄ed洞ge);//求生蒙成树禾的下让一个畏顶点k//此时cl露os歌ed践ge掉[k抹].卵lo鹿wc切os悲t=//MI航N{资cl染os续ed稳ge巷[vi].旱lo总wc该os得t|cl梨os冠ed势ge辞[vi].码lo约wc掠os引t>0压,泼vi∈v-尚u}co膊ut<<"(格"炊<<k<<",弦"<处<cl斤os泪ed文ge耍[k近].谅ad迫jv小ex<<耽"疑)";//输出拴生成腊树的毯边cl泪os蒸ed候ge债[k].临lo帐wc允os精t=想0;//顶点k并入U集合fo圆r(均j=贺0;澡j愿<G.拖ve廉xn区um;掉++颂j)if睛(G.顺ar壤cs循[k占][唯j]良<cl指os条ed冷ge铜[j饮].巨lo淋wc减os芝t)cl晶os嚷ed慕ge幼[j知].荒ad的jv珍ex=仁k,cl灰os体ed盛ge伟[j激].促Lo惹wc魂os蛾t=G.理ar蒜cs拐[k杯][绍j];算法咳的时克间复宁杂度巾为：O(辫n2){cl丑os鹅ed怀ge糊[j朵].悼ad顶jv勺ex=缩慧u;cl朝os里ed苹ge迎[j隙].齐lo斥wc脖os绸t=G.寇ar局cs初[u丈][寨j];拌}选做街内容从键贡盘输芳入（冷或从僚文件兄读入徒）图迹的信协息，感用克呆鲁斯之卡尔尤算法干求解图给定相无向拼连通盛图的愉最小育生成茧树，君最后斗输出颤最小肌生成终树中剧的权痕值和集所有沉的边肢。克鲁谅斯卡动尔(Kr哗us无ka园l)算法假设混连通曾网N=忆(V，E)，则令横最小六生成秘树的及初始私状态托为只眼有n个顶梅点而卷无边枣的非郑连通艰图T=宿(V，{}肆)，图中宪每个蓄顶点慈自成估一个唯连通峡分量疼。在E中选务择代约价最作小的阿边，太若该宪边依裤附的悲顶点合落在T中不欢同的贯连通甩分量春上，简则将匠此边杏加入犁到T中，咬否则拔舍去寨此边膜而选半择下责一条吉代价捡最小辱的边毫。依年