资源描述：
《数据结构与算法分析课后题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、课后答案网，用心为你服务！大学答案---中学答案---考研答案---考试答案最全最多的课后习题参考答案，尽在课后答案网（www.khdaw.com）！Khdaw团队一直秉承用心为大家服务的宗旨，以关注学生的学习生活为出发点，旨在为广大学生朋友的自主学习提供一个分享和交流的平台。爱校园（www.aixiaoyuan.com）课后答案网（www.khdaw.com）淘答案（www.taodaan.com）Chapter9:GraphAlgorithms9.1Thefollowingorderingisarrivedatbyusingaque
2、ueandassumesthatverticesappearonanadjacencylistalphabetically.Thetopologicalorderthatresultsisthens,G,D,H,A,B,E,I,F,C,t9.2Assumingthesameadjacencylist,thetopologicalorderproducedwhenastackisusediss,G,H,D,A,E,I,F,B,C,tBecauseatopologicalsortprocessesverticesinthesamemanne
3、rasabreadth-®rstsearch,ittendstoproduceamorenaturalordering.9.4TheideaisthesameasinExercise5.10.9.5(a)(Unweightedpaths)A->B,A->C,A->B->G,A->B->E,A->C->D,A->B->E->F.(b)(Weightedpaths)A->C,A->B,A->B->G,A->B->G->E,A->B->G->E->F,A->B->G->E->D.9.6We'llassumethatDijkstra'salgo
4、rithmisimplementedwithapriorityqueueofverticesthatusestheDecreaseKeyOoperation.Dijkstra'salgorithmusesO
5、OEO
6、ODecreaseKeyOoperations,whichcostOO(logdOO
7、OVO
8、O)each,andO
9、OVO
10、ODeleteMinOoperations,whichcostOO(dOlogdOO
11、OVO
12、O)each.TherunningtimeisthusOO(O
13、OEO
14、OlogdOO
15、OVO
16、O+O
17、O
18、VO
19、OdOlogdOO
20、OVO
21、O).ThecostoftheDecreaseKeyOoperationsbalancestheInsertOoperationswhendO=O
22、OEO
23、O/O
24、OVO
25、O.Forasparsegraph,thismightgiveavalueofdOthatislessthan2;wecan'tallowthis,sodOischosentobemax(2,OIO
26、OEO
27、O/O
28、OVO
29、OOK).ThisgivesarunningtimeofOO(O
30、OEO
31、Olog2+O
32、OEO
33、O/O
34、OVO
35、
36、OO
37、OVO
38、O),whichisaslighttheoreticalimprovement.MoretandShapiroreport(indirectly)thatdO-heapsdonotimprovetherunningtimeinpractice.9.7(a)Thegraphshownhereisanexample.Dijkstra'salgorithmgivesapathfromAOtoCOofcost2,whenthepathfromAOtoBOtoCOhascost1.C2A-23B(b)Wede®neapassoft
39、healgorithmasfollows:Pass0consistsofmarkingthestartvertexasknownandplacingitsadjacentverticesonthequeue.ForPjO>0,passPjOconsistsofmark-ingasknownallverticesonthequeueattheendofpassPjO-1.Eachpassrequireslineartime,sinceduringapass,avertexisplacedonthequeueatmostonce.Itise
40、asytoshowbyinductionthatifthereisashortestpathfromsOtovOcontainingkOedges,thendvOwillequalthelengthofth
