硕士算法2010_第5章_图的算法001

1算法设计与分析李洪伟博士电子科技大学计算机科学与工程学院[e-mail]=2982第5章图的算法图的概念图的搜索问题拓扑排序强连通分支最小生成树算法最短路径算法欧拉回路与中国邮递员问题网络流及其应用3GraphsDefinitionsGraphTraversalsDepthFirstSearch(DFS)BreadthFirstSearch(BFS)TopologicalSortShortestPathsProblemsMinimumSpanningTree(MST)4图4.-1哥尼斯堡七桥问题哥尼斯堡七桥问题从任一地出发，是否能在每座桥只通过一次的前提下，游历全城最后又返回到原出发地？CDAB图4.-2哥尼斯堡七桥问题所对应的图CABD5Definition:DirectedgraphDirectedGraphAdirectedgraph,ordigraph,isapairG=(V,E)whereVisasetwhoseelementsarecalledvertices,andEisasetoforderedpairsofelementsofV.Verticesareoftenalsocallednodes.ElementsofEarecallededges,ordirectededges,orarcs.Fordirectededge(v,w)inE,visitstailandwitshead;(v,w)isrepresentedinthediagramsasthearrow,v-w.Intextwesimplewritevw.Definition:UndirectedgraphUndirectedGraphAundirectedgraphisapairG=(V,E)whereVisasetwhoseelementsarecalledvertices,andEisasetofunorderedpairsofdistinctelementsofV.Verticesareoftenalsocallednodes.ElementsofEarecallededges,orundirectededges.EachedgemaybeconsideredasasubsetofVcontainingtwoelements,{v,w}denotesanundirectededgeIndiagramsthisedgeisthelinev---w.Intextwesimplewritevw,orwvvwissaidtobeincidentupontheverticesvandwDefinitions:WeightedGraphAweightedgraphisatriple(V,E,W)where(V,E)isagraph(directedorundirected)andWisafunctionfromEintoR,thereals.Foranedgee,W(e)iscalledtheweightofe.GraphRepresentationsAdjacencyMatrixRepresentationLetG=(V,E),n=|V|,m=|E|,V={v1,v2,…,vn)Gcanberepresentedbyannnmatrix9AdjacencyMatrixforweightdigraphArrayofAdjacencyListsRepresentationFromtoArrayofAdjacencyListsRepresentationfrom-to,weightMoreDefinitionsSubgraphSymmetricdigraphcompletegraphAdjacencyrelationPath,simplepath,reachableConnected,StronglyConnectedCycle,simplecycleacyclicundirectedforestfreetree,undirectedtreerootedtreeConnectedcomponent13MoreDefinitionsAsubgraphG'=(V',E')ofagraphG=(V,E)consistsofasubsetofV'V,andE'E,suchthateachedgeinE'isaconnectionbetweenapairofverticesinV'.Thenumberofverticesisdenotedby|V|,andthenumberofedgesisdenotedby|E|.Asequenceofvertices,v1,v2,...,vnformsapathoflengthn–1ifthereexistedgesfromvitovi+1for1≤in.14MoreDefinitionsAcycleisapathoflength3ormorethatconnectsvitoitself.Acycleissimpleifthepathissimple,exceptforthefirstandlastverticesbeingthesame.Anundirectedgraphisconnectedifthereisatleastonepathfromanyvertextoanyother.Themaximalconnectedsubgraphsofanundirectedgrapharecalledconnectedcomponents.34121702413(a)(b)(c)MoreDefinitionsAgraphwithoutcyclesisacyclic.AdirectedgraphwithoutcyclesisadirectedacyclicgraphorDAG.Afreetreeisaconnected,undirectedgraphwithnosimplecycles.Equivalently,afreetreeisconnectedandhas|V–1|edges.16Bi-connectedComponentsofanUndirectedGraphProblem:Ifanyonevertex(andtheedgesincidentuponit)areremovedfromaconnectedgraph,Istheremainingsubgraphstillconnected?Biconnectedgraph:AconnectedundirectedgraphGissaidtobebiconnectedifitremainsconnectedafterremovalofanyonevertexandtheedgesthatareincidentuponthatvertex.17Bi-connectedComponentsofanUndirectedGraphBiconnectedcomponent:Abiconnectedcomponentofaundirectedgraphisamaximalbiconnectedsubgraph,thatis,abiconnectedsubgraphnotcontainedinanylargerbinconnectedsubgraph.Articulationpoint:AvertexvisanarticulationpointforanundirectedgraphGiftherearedistinctverticeswandx(distinctfromvalso)suchthatvisineverypathfromwtox.Bi-connectedcomponents,e.g.Someverticesareinmorethanonecomponent(whichverticesarethese?)StronglyConnectedComponentsofaDigraphStronglyconnected:Adirectedgraphisstronglyconnectedifandonlyif,foreachpairofverticesvandw,thereisapathfromvtow.Stronglyconnectedcomponent:AstronglyconnectedcomponentofadigraphGisamaximalstronglyconnectedsubgraphofG.20StronglyConnectedComponentsandEquivalenceRelationsStronglyconnectedcomponentsmaybedefinedintermsofanequivalencerelation,S,ontheverticesvSwiffthereisapathfromvtowandapathfromwtovThen,astronglyconnectedcomponentconsistsofoneequivalenceclass,C,alongwithalledgesvwsuchthatvandwareinC.21CondensationgraphThestronglyconnectedcomponentsofadigraphcaneachbecollapsedtoasinglevertexyieldinganewdigraphthathasnocycles.Condensationgraph:LetS1,S2,...SpbethestronglyconnectedcomponentsofG.ThecondensationgraphofGdenotedasG=(V',E'),whereV'haspelementss1,s2,...spandsisjisinE'ifandonlyifijandthereisanedgeinEfromsomevertexinSitosomevertexinSj.22CondensationgraphanditsstronglyconnectedcomponentsCondensationGraphisacyclic.234.3图的搜索搜索是解决许多有关图的问题的一种基本技术，同时也是许多图论算法的基础。简单地讲，图的搜索是指从图的某个节点出发，依某种次序访问图的各个节点。典型的搜索算法有宽度优先搜索（BreadthFirstSearch，BFS）和深度优先搜索（DepthFirstSearch，DFS）两种。24Breath-firstsearchBreadth-firstsearch:Strategy(fordigraph)chooseastartingvertex,distanced=0verticesarevisitedinorderofincreasingdistancefromthestartingvertex,examinealledgesleadingfromvertices(atdistanced)toadjacentvertices(atdistanced+1)then,examinealledgesleadingfromverticesatdistanced+1todistanced+2,andsoon,untilnonewvertexisdiscoveredBreath-firstsearch,e.g.e.g.StartfromvertexA,atd=0visitB,C,F;atd=1visitD;atd=2e.g.StartfromvertexE