第12章信息科学与技术学院

Chapter12 Terms:vertex,edge,adjacent,incident,degree,cycle,path,connectedcomponent,spanningtree;Threetypesofgraphs:undirected,directed,Commongraphrepresentations:adjacencymatrix,adjacencylists.G=VisthevertexVerticesarealsocallednodesandEistheedgeEachedgeconnectstwodifferentEdgesarealsocalledarcsandDirectededgehasanorientation Undirectededgehasnoorientation Undirectedgraph=>noorientedDirectedgraph=>everyedgehasanUndirectedDirectedThereisadirectedpathfromanyvertextoanyothervertex.2231845967Vertex=city,edge=communicationDrivingDistance/Time442381862445543956677Vertex=city,edgeweight=drivingStreet2231845967SomestreetsareoneCompleteUndirectedHasallpossiblen= n= n= n=NumberOfEdges—UndirectedEachedgeisoftheform(u,v),u!=Numberofsuchpairsinannvertexgraphisn(n-1).Sinceedge(u,v)isthesameasedge(v,u),thenumberofedgesinacompleteundirectedgraphisn(n-1)/2.Numberofedgesinanundirectedgraph<=n(n-NumberOfEdges--DirectedEachedgeisoftheform(u,v),u!=NumberofsuchpairsinannvertexgraphSinceedge(u,v)isnotthesameasedge(v,u),thenumberofedgesinacompletedirectedgraphisn(n-1).NumberofedgesinadirectedgraphisVertex2231845967Numberofedgesincidenttovertex.degree(2)=2,degree(5)=3,degree(3)=1SumOfVertex889Sumofdegrees=2e(eisnumberofIn-DegreeOfA2231845967in-degreeisnumberofincomingedgesindegree(2)=1,indegree(8)=0Out-DegreeOfA2231845967out-degreeisnumberofoutboundedgesoutdegree(2)=1,outdegree(8)=2SumOfIn-AndOut-eachedgecontributes1tothein-degreeofsomevertexand1totheout-degreeofsomeothervertexsumofin-degrees=sumofout-=e,whereeisthenumberofedgesinthedigraphComputerAdjacencyTables(orAdjacencyLinkedAdjacencyArrayAdjacencyTheSetAdjacency0/1n×nmatrix,wheren=#ofA(i,j)=1iff(i,j)isan23231 512345 1010 0001 0001 0001 1110AdjacencyMatrix231 5 231 5 DiagonalentriesareAdjacencymatrixofanundirectedgraphisA(i,j)=A(j,i)foralliand AdjacencyMatrix23145 23145 DiagonalentriesareAdjacencymatrixofadigraphneednotbeAdjacencyn2bitsofForanundirectedgraph,maystoreonlyloweroruppertriangle(excludediagonal).(n-1)n/2O(n)timetofindvertexdegreeand/orverticesadjacenttoagivenvertex.Adjacency AdjacencyAdjacencylistforvertexiisalinearlistofverticesadjacentfromvertexi.AnarrayofnadjacencyaList[1]=231 231 5aList[3]=aList[4]=aList[5]=ArrayAdjacencyEachadjacencylistisanarray231231 524243ArrayLength=#oflistelements=2e(undirectedgraph)#oflistelements=e(digraph)LinkedAdjacencyEachadjacencylistisa231231 5ArrayLength=#ofchainnodes=2e(undirected#ofchainnodes=eGraphAvertexuisreachablefromvertexviffthereisapathfromvtou.2231845967 Asearchmethodstartsatagivenvertexvandvisits/labels/markseveryvertexthatisreachablefromv.22314577ManygraphproblemssolvedusingasearchPathfromonevertextoIsthegraphFindaspanningCommonlyusedsearchDepth-firstVisitstartvertexandputintoaFIFORepeatedlyremoveavertexfromthequeue,visititsunvisitedadjacentvertices,putnewlyvisitedverticesintothequeue.2231845967Startsearchatvertex231231845967FIFOQueueVisit/mark/labelstartvertexandputinaFIFO231231845967FIFOQueue231231845967FIFOQueue24231231845967FIFOQueue24231231845967FIFOQueue4536231231845967FIFOQueue4536231231845967FIFO53231231845967FIFO53231231845967FIFOQueue3697231231845967FIFOQueue3697231231845967FIFO69231231845967FIFO69231231845967FIFO9231231845967FIFO9231231845967FIFO7231231845967FIFO7231231845967FIFOQueue231231845967FIFOQueue231231845967FIFOQueueisempty.SearchBreadth-FirstSearchAllverticesreachablefromthestartvertex(includingthestartvertex)arevisited.TimeEachvisitedvertexisputon(andsoremovedfrom)thequeueexactlyonce.Whenavertexisremovedfromthequeue,weexamineitsadjacentvertices.O(n)ifadjacencymatrixO(vertexdegree)ifadjacencylistsTotalΘ(sn),wheresisnumberofverticesinthecomponentthatissearched(adjacencymatrix)

)(adjacencyDepth-First{Labelvertexvasreached.for(eachunreachedvertexuadjacenctfromv)}2231845967Startsearchatvertex2231845967223184596722318459672231845967Labelvertex8andreturntovertexFromvertex9doa2231845967Labelvertex6anddoadepthfirstsearchfromeither4or7.Supposethatvertex4is 2231845967Labelvertex4andreturntoFromvertex6doa 2231845967Labelvertex7andreturnto22318459672231845967Doa2231845967Label3andreturntoReturntoDepth-FirstSearch23814 67Returnto231845231845967ReturntoinvokingDepth-FirstSearchSamecomplexityasSamepropertieswithrespecttopathfinding,connectedcomponents,andspanningtrees.Edgesusedtoreachunlabeledverticesdefineadepth-firstspanningtreewhenthegraphisThereareproblemsforwhichBFSisbetterthanDFSandviceversa.12.412.4Topological12.4.3Breadth-First}}12.4.3Breadth-First该方法的每一步均是输出当前无后继(即出度为0)的顶点。对于一个while(G中有出度为0的顶点)do{}12.512.5AGreedyAlgorithm:ShortestDirectedweightedPathlengthissumofweightsofedgesonThevertexatwhichthepathbeginsisthesourcevertex.Thevertexatwhichthepathendsisthedestinationvertex.11365247Apathfrom1to11365247Anotherpathfrom1toShortestPathSinglesourcesingleSinglesourceallAllpairs(everyvertexisasourceanddestination).SingleSourceSinglePossiblegreedyLeavesourcevertexusingcheapest/shortestLeavenewvertexusingcheapestedgesubjecttotheconstraintthatanewvertexisreached.ContinueuntildestinationisGreedyShortest1To711365247PathlengthisNotshortestpath.Algorithmdoesn’tSingleSourceAllNeedtogenerateupton(nisnumberofvertices)paths(includingpathfromsourcetoitself).GreedyConstructtheseuptonpathsinorderofincreasingAssumeedgecosts(lengths)are>=So,nopathhaslength<Firstshortestpathisfromthesourcevertextoitself.Thelengthofthispathis0. 4 1 113 1321351351 10131313135121213135413136

Eachpath(otherthanfirst)isaoneedgeextensionofapreviousNextshortestpathistheshortestoneedgeextensionofanalreadygeneratedshortest131367GreedySingleSourceAllLetd(i)(distanceFromSource(i))bethelengthofashortestoneedgeextensionofanalreadygeneratedshortestpath,theoneedgeextensionendsatvertexi.Thenextshortestpathistoanasyetunreachedvertexforwhichthed()valueisleast.Letp(i)(predecessor(i))bethevertexjustbeforevertexiontheshortestoneedgeextensiontoi.d062--p-111--11 11136524713d062p-111311 11136524713 13135 6 135 1 11136524713 13135 9 13512 1211365113652471313512 6295p-11533411354 4 6295 1153361 101313131351212135135406295-11533613136131367DataStructuresForDijkstra’sThegreedysinglesourcealldestinationsalgorithmisknownasDijkstra’salgorithm.Implementd()andp()as1DKeepalinearlistLofreachableverticestowhichshortestpathisyettobegenerated.SelectandremovevertexvinLthathassmallestd()value.Updated()andp()valuesofverticesadjacentto O(n)toselectnextdestinationO(out-degree)toupdated()andp()valueswhenadjacencylistsareused.O(n)toupdated()andp()valueswhenadjacencymatrixisused.Selectionandupdatedoneonceforeachvertextowhichashortestpathisfound.TotaltimeisO(n2+e)=12.612.6Minimum-CostSpanningweightedconnectedundirectedspanningcostofspanningtreeissumofedgefindspanningtreethathasminimum 9Networkhas10Spanningtreehasonlyn-1=7Needtoeitherselect7edgesordiscardStartwithann-vertex0-edgeforest.Consideredgesinascendingorderofcost.Selectedgeifitdoesnotformacycletogetherwithalreadyselectededges.Kruskal’sStartwitha1-vertextreeandgrowitintoann-vertextreebyrepeatedlyaddingavertexandanedge.Whenthereisachoice,addaleastcostedge.Prim’sStartwithann-vertexforest.Eachcomponent/treeselectsaleastcostedgetoconnecttoanothercomponent/tree.Eliminateduplicateselectionsandpossiblecycles.Repeatuntilonly1component/treeisleft.Sollin’s 9

StartwithaforestthathasnoConsideredgesinascendingorderof Edge(1,2)isconsideredfirstandaddedtotheforest.1223744566738 1223744566738 9Edge(7,8)isconsiderednextandEdge(3,4)isconsiderednextandEdge(5,6)isconsiderednextandEdge(2,3)isconsiderednextandEdge(1,3)isconsiderednextandrejecteditcreatesa 9

Edge(2,4)isconsiderednextandrejectedbecauseitcreatesacycle.Edge(3,5)isconsiderednextandEdge(3,6)isconsiderednextandEdge(5,7)isconsiderednextand183575722794466836683n-1edgeshavebeenselectedandnocycleSowemusthaveaspanningCostisMin-costspanningtreeisuniquewhenedgecostsare Prim’s 9StartwithanysinglevertexGeta2-vertextreebyaddingache