山东大学算法与设计重点

23.1-5证明:设C=v0,v1,…,vk是一个圈,其中边e=(v0,vk)是权值最重的边。只需要构造一棵不包含e=(v0,vk)的MST即可。设T是一棵包含e=(v0,vk)的MST，则删除e会使T变成两个连通分支V1，V2，v0V1，vkV2。依次检测顶点v1,…,vk，找到第一个在V2中的顶点vi(这样的vi一定能找到，因为vkV2)，从而e’=(vi-1,vi)是穿过割(V1,V2)的一条边，并且w(v0,vk)

w(vi-1,vi)。则T’=T-e+e’是一棵新的MST。23-4(a)证明:设T中的边按照权值非递减顺序依次为e1,e2,…,en-1,即算法依次保留边e1,e2,…,en-1。设边集Ai={e1,e2,…,ei}，1in-1则只需要证明每个Ai

都是某棵最小生成树的子集。用归纳法证明。i=1时，设T’是一棵最小生成树，如果(u,v)=e1T’,结论自然成立。如果e1T’，则在T’中存在u到v的路径p。因为删除e1会使图不连通，即删除e1会使顶点集合V划分为两个子集V1和V2，其中uV1，vV2。则路径p中存在1条边(x,y)满足xV1，yV2，并且(x,y)已经被删除了，否则如果p中所有边都没被删除，删除e1不会使图不连通。既然(x,y)已经被删除了，根据算法是按照权值由大到小的顺序删边的，所以w(x,y)

w(u,v)。则T’’=T’-(x,y)+(u,v)必然是一棵最小生成树。Continued设对边集Ai时结论成立，现在证明边集Ai+1也是某棵最小生成树的子集。设Ai={e1,e2,…,ei}是最小生成树T’的子集，如果(u,v)=ei+1T’,结论自然成立。如果ei+1T’，则在T’中存在u到v的路径p。因为删除ei+1会使图不连通，即删除e1会使顶点集合V划分为两个子集V1和V2，其中uV1，vV2。则路径p中存在1条边(x,y)满足xV1，yV2，并且(x,y)已经被删除了，否则如果p中所有边都没被删除，删除e1不会使图不连通。既然(x,y)已经被删除了，根据算法是按照权值由大到小的顺序删边的，所以w(x,y)

w(u,v)。则T’’=T’-(x,y)+(u,v)必然是一棵最小生成树。现在只需要证明T’’包含Ai={e1,e2,…,ei+1}中的所有边，因为T’’与T’只有1条边不同，所以只需要证明(x,y)Ai，这显然是成立的，因为(x,y)已经被删除了，而{e1,e2,…,ei}是没被删除的。证明完毕！23-4(c)证明：算法实际上是在图G中删除一些圈上权值最重的边，最后得到一棵MST。设删除的边依次为e1,e2…,em-n+1，剩余的图依次是G0,G1,…,Gm-n+1，其中G=G0，Gm-n+1=T，m=|E|，n=|V|。我们证明Gi+1的MST同时也是Gi的MST即可。前面23.1-5已经证明了存在Gi+1的MSTT’同时也是Gi的MST，而Gi+1的所有MST的大小与T’一样的，所有它们都与Gi的MST的大小一样，所以他们都是Gi的MST。从而Gm-n+1必然是Gm-n,…,Go的MST。Exercises22.3-222.3-6(DFS栈实现)DFS(G)1foreachvertexuV[G]2do

color[u]WHITE3[u]NILtime

0StackS

6foreachvertexuV[G]7doif

color[u]=WHITE8ThenS.push(u)9WhileS10do

color[S.top]GRAY11d[S.top]

time

time

+112ifexistsvAdj[S.top]&&

color[v]=WHITE13then

[v]

S.topS.push(v)15else16uS.pop()17color[u]BLACK18f[u]

time

time

+1SinglyConnected:forallverticesu,vV,

ifuv,thenthere

isatmostonesimplepathfromu

tov.idea:DFS-VISIT(u)可以发现u可达的所有顶点,即u到这些点都有路径。前向边和交叉边（搜索过程中遇到黑点）意味着什么呢？u到某个点有多于1条路径。这只是u到其它点的情况，单连通要分析任意的顶点对，所以需要分析每个点到其它所有点的情况。即从每个点开始，都做一次DFS-VISIT()。SinglyConnected:forallverticesu,vV,

ifuv,thenthere

isatmostonesimplepathfromu

tov.idea:DFS-VISIT(u)可以发现u可达的所有顶点,即u到这些点都有路径。前向边和交叉边（搜索过程中遇到黑点）意味着什么呢？u到某个点有多于1条路径。这只是u到其它点的情况，单连通要分析任意的顶点对，所以需要分析每个点到其它所有点的情况。即从每个点开始，都做一次DFS-VISIT()。TheAlgorithmTopologicallysortallverticesinG.Assumingthattheverticesarev1,v2,…,vi,…,vj,…,vnintheirtopologicalorder,wheres=vi,t=vj.Initializep[v]0,v1vvn.p[vj]1.For

kj-1downtoiforeach

vAdj[vk]do

if

vvjaccordingtotheirtopologicalorderthen

p[vk]p[vk]+p[v].return

p[vi].posrutyvwznqnqposrutyvwz43111100Thereare4distinctpathsfromptov.An稍ot妄he厘r夺ex嚼am奖pl帐eabcdefghijklmabcdefghijklm16884+4442+221+12111Thereare16distinctpathsfromatom.An切ot晋he咬r贿ex星am撑pl丝式eabcdefghijklmabcdefghijklm16884+4442+221+12111Thereare16distinctpathsfromatom.22兄.4龄-3Gi将ve缝n散an券a抚lg评or候it贤hm晚t汪ha闷t此de泽te毅rm挡in堡es值w级he例th备er然o刻r痕no乐t额a挎gi辣ve名n泉un牺di烈re拼ct联ed赛g谱ra哭ph险G谨=(重V,仔E)井c炊on质ta索in册s愤a谷cy疏cl垦e.O(V被),陆i甩nd历ep堆en尿de监nt免o循f凳|E编|.DF依S,返s暮to耻ps顾w漠he倦ne厉ve摧r减en闸co忙un冲te亚rs砖a惕n贿ba线ck印e筒dg缓e.22环.4优-5No命te舰:首先迅要计蹦算每译个点她的入件度。O(V且+E千)当删瞎一个脑点时欢，其区邻接贞点的躺入度馒要减1。O(V讲+E剑)记录锦入度飘为0的点.22忙.4挑-5具P划ro版of婚o违f圆Co做rr窜ec箩tn沾es赞sIn层du尤ct哭io柿n掩on直|长V|暂.约|V登|=踩2,索o怎nl卡y需on吓e上ed短ge雅,棚tr给iv础ia界l.Su腰pp称os届e裂it啄i眉s兴tr隔ue肤f鸭or撤|崭V|笔<n射.Wh雨en松|股V|顷=n宴.坡Se歉le克ct职a排v日er繁te扫x中s沫of锅i易n-膏de呢gr华ee搭z董er帆o.(m狗us额t枝ex堡is绞t.宇O鲜th裁er监wi给se渡,萄al状l躬ve绸rt染ic耀es婶h幼av歼e愁no勇n-瓶ze扇ro含i魔n-仗de英gr银ee歪s.搞S订ta械rt杯f调ro尾m扣a纳ve崭rt饥ex疲a票nd敬b迁ac悦kt锁ra很ck挂a岸lo招ng钳i岁n-魄ed罢ge寻s.湿S拌in调ce陡V耗i饥s鸭li允mi成te晨d,棒t嚷he察p霉ro耍ce宝du据re勿m刃us晒t忙en联d选at口a歪n竿in浙-e慰dg服e搏wh跃ic芒h仪le尘av湿es器a茶v随er吗te干x仁al疼re部ad草y跪en锐co绝un咳te粮re璃d,遭t市hu墙s口im口pl丑ie湖s容a们cy本cl甚e胸).Ac弱co帅rd棍in铅g屠to均o切ur解a枣lg遗or匙it光hm翁,宪s邀wi晶ll膝b训e牺at失t涌he遥m讨os浇t孔le缘瑞ft检o修f杨th士e甘li昏st掏L修.已An鼠d勒th序e嫌ot灯he播r芳pa谦rt安L棍’蒜of良t矩he滚l净is苹t虚is肉e奏xa盼ct棒ly薪t告he费l谨is闻t洽of家t事he减g表ra查ph厌G前’们ob训ta掏in妇ed妹b迈y组de今le暮ti淘ng她s结a麦nd较t滑he剥e钓dg来es岗l厅ea杨vi暮ng型i猜t.才B窄y怜in顽du剑ct查io省n单hy仰po僵th筐es宏is阅,待al盒l识ed仇ge章s认in胆G齿’顷po拢in滴ti腔ng谅f物ro帅m弄le讨ft启t多o谊ri瞎gh收t绿in鸽t槐he举l要is状t景L’盲(t里hu辜s袄al不so献i蚀n暴L)擦.贷Co幕ns貌id径er润in轰g映th断at湾a们ll变e阵dg心es谈i效n俯G职ar劲e靠ei盐th刘er阶t柴ho杜se除i撤n灭G’伐o序r旁th叙os耕e呜le托av晶in武g粘s,恐w宫e诞co岗mp圾le匙te委s键th恩e卖pr捆oo劣f.fo胁r从an嫂y座(u,v)E涨,风th烘e商in宪-d烛eg瞧re爷e宜ofvca利n尝no降t这be遵z珠er利o六be衫fo便re樱d幸el至et副in泻gu,茶wh认ic晕h锐im多pl顷ie延suap拼pe渔ar钥s圆in森f面ro季nt心o恼fv.Di姥jk欧st毕ra’s血Al膛go袋ri框th军mPr胡ob踏le贵m珍so看lv滚edCo右rr岛ec赚tn图es阅sTi赏me窃c逝om阁pl惠ex剂it冷ySi漆mi悬la费ri刑ti锐es奶t锄o棕BF摸S朴an溪d森PR萄IMPr仁ob姐le解m园So内lv旷ed陕b款y泽Di凝jk特st限ra恢’sSi特ng跨le旁-s楚ou明rc践e误sh喝or享te号st猛-p贝at镜hs爷p牧ro丙bl汽emEd灿ge饭w餐ei赴gh石t>=尝0In革pu榆t:凶A搬g塞ra侮phG=(V,E)黎an编d羡a霸so递ur拐ces,医an唤d愿a堂no抹nn阴eg盆at洋iv背e仗fu术nc案ti固onw:ER+Ou仇tp询ut粮:宫Fo恢r终ea蒜ch做v拼er域te羽xv,耐sh贪or赚te赴st零p拍at站h史we孔ig忆htd(s,v),杂a筑nda瘦sh絮or蹦te捕st复p阀at窃h正if俭e此xi拾st蜂s.Th国e呀Di辣jk务st醉ra纷A夫lg禽or单it惧hmDI色JK激ST柏RA浮(G擦,w漂,s孙)In问it财ia纲li辛ze敏-S请in塑gl攻e-膨So腔ur佳ce法(G呈,s掩)SQ猴V[糟G]wh捷il泥e惊Qdo腊u刘E苹XT付RA烤CT洲-M颈IN裂(Q场)S印S{u}fo烛r稿ea策ch优vAd鞭j[掀u]doRE失lA芹X(链u,繁v,霞w)Di依jk谁st戴ra’s划Al浙go据ri毛th到m孝-Op决er请at季io汇nSis伐n蛋ow{s,最x眠,仓y,秤u}Pr剂e-匹de颜ce穴ss堪or朱s寒sh冲ow万s魄ho摩rt单es狡t随pa崭th祝s背su稼b-益gr框ap姜hCo雀rr鹅ec关tn依es后s蝇of贤D索ij酿ks抓tr钞a’sTh姿eo长re甩m良24晓.6Di卫jk巴st想ra’s脏al亚go尸ri匆th亮m,眠r铅un描o厘n谈a旷we伤ig扁ht架ed劣,d嫩ir栽ec够te胸d熔gr东ap疏hG=(V,E),拜w腹it鹊h请no傍n-变ne礼ga活ti谦ve贡w担ei沃gh佩t耗fu藏nc数ti诞onwan佩d读so灿ur淡ces,群te从rm哄in防at裁es质w越it熟hd[u]=d(s,u)fo校r敲al戚l魂ve粥rt渠ic央esuV.Pr拜oo债f(b躲y解co夫nt握ra予di湖ct纳io柱n)Si腔nc杀eS=Vin隐t毙he佳e株nd介,损we堡o侨nl找y东ne巧ed脚t点o程pr难ov桃e君th漏at狗f得or悠e棕ac蹈h粘ve益rt嗓exvad矛de棕d口toS,迟th右er闸e蜻ho炊ld惰sd[v]=d(s,v)管wh导envis帮a轿dd平ed残t耽oS.Su捎pp拨os谎e巧th清atuis炊t条he尿f廉ir患stve梳rt劈燕ex淹f获or污w灶hi束chd[u]¹d(s,u)稍wh复en位i躁t疤wa泼s煌ad盘de溉d折toSNo堂teu音is尿n察ot擦s姓b农ec陷au从sed[s]古=事0=d(s,s)Th渡er延e熊mu误st芳b撒e趋a便pa匹ths®..瓦.®u,肠si稿nc挣e株o彼th嗽er琴wi业sed[u]=d(s,u)=¥.Si胆nc司e甘th暴er奸e’s佛a洪pa屿th串,费th拢er慰e势mu把st效b辈e敏a症sh旺or育te洁st盛p跃at傻h天(n久ot泳e可th换er莲e女is茫n咱o挨ne虹ga胳ti芦ve紧c仔yc禽le赞).Di辣jk愧st茄ra’s已Al喷go寸ri粱th纽奉m螺-Pr的oo魄fLe织ts®x®y®ube甚a死s云ho救rt岗es量t索pa明th基f辣ro源mstou,wh胞er某eat贼t瓣he们m永om潜en悲tuis吐c职ho伍se泡n粉toS,xis粒i则nSan秤dyis屯t铺he院fi妹rs犁t蛾ou誓ts含id顷eSWh抵enxwa醋s松ad偶de袍d馆toS,d[x]=d(s,x)Ed默gex®ywa腐s肯re盆la厚xe己d恩at六t请ha锅t滤ti馒me养,积s肥o孕at厨t贩im甜e睬u别is僚c曲ho狐se弊n,d[y]=d(s,y)Di碎jk滔st恼ra’s住Al榴go置ri拦th仪m层-Pr令oo棒fSo箱,描d[绘y]絮=d(s,y)£d(s,u)£d[u]Bu踪蝶t,镜w章he再n淹we声c牙ho巨seu,bo悄thuan悔dyar拖e放inQ,sod[u]£d[y](o翻th厨er信wi壶se景w孟e嗓wo舱ul卵d蔬ha志ve面c窗ho愚se辜ny)Th励us蚀t郊he塘i系ne炒qu纱al滨it奴ie巧s料mu清st巧b塘e帆eq教ua穗li抽ti雾esd[y]=d(s,y)=d(s,u)=d[u]An捕d巨ou愧r兵hy那po苍th迫es循is践(d[u]¹d(s,u))湿is北c将on冻tr美ad萄ic轧te今d!1.柄Wh送y供th舅ere你din神eq腹ua逗li秘ty秧h舅ol扑ds遵?路Ho朱w茎ab鹿ou帆t聪ne彼ga费ti虫ve胁e放dg倒es烟e清xi灰st耀?2.捧Wh爆enuis贫a悠dd筒ed秧t服oS,芬a提sh始or链te垄st核p躲at微h蓄suin怠S加i慰s底fo屋un富d.Di膀jk冰st秀ra’s择Al茎go情ri动th摩m汉-Ti烂me县C别om咱pl绩ex赏it虫yLi历ke理t庙ha太t叠of咬P骡RI藏M’sIf喝u制si趁ng丽a捷rr误ay勺sO(脊V2)Us饥in视g亭sp斧ec标ia副l良da届ta卖s盒tr算uc预tu尤reO(支Vl续gV桥+E倘)留or贝l秀es羊sCo呢mp鸟ar顶ed炉t欧o衬BF耕SDI冒JK播ST响RA踩(G斥,w斜,s纵)IN沈IT倾IA菜LI确ZE愧-S份IN皮GL婶E-袜SO推UR糊CE券(G羽,s猛)SQV末[G积]wh抓il活e辰Qdo键uEX