數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)31-graph

數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)(31)

Chapter12Graphs王麗蘋lipingwang@4/21/20231.Graphsexample:NorthwestAirlineFlightShenYangJiNanShanHaiBeiJingWuHanXianLanZhouWuLUMuQi4/21/20232.Graphsexample:ComputerNetworkOrInternetECNURegionalNetworkIntelUNTFuDanUniversity4/21/20233.ApplicationTravelingSalemanFindtheshortestpaththatconnectsallcitieswithoutaloop.Start4/21/20234.ConceptsofGraphsedges(weight)nodeorvertex4/21/20235.GraphDefinitionAgraphG=(V,E)iscomposedof: V:setofvertices(nodes節(jié)點(diǎn)) E:setofedges(arcs邊)connectingtheverticesinVAnedgee=(u,v)isapairofverticesExample:abcdeV={a,b,c,d,e}E={(a,b),(a,c),(a,d),(b,e),(c,d),(c,e),(d,e)}4/21/20236.Undirectedvs.DirectedGraphUndirectedGraphedgehasnoorientedDirectedGraphedgehasorientedvertex4/21/20237.Thedegree（度）

ofavertexisthenumberofedgestothatvertexFordirectedgraph,thein-degree(入度)ofavertexvisthenumberofedges

thathavevastheheadtheout-degree(出度)

ofavertexvisthenumberofedges

thathavevasthetailifdiisthedegreeofavertexiinagraphGwithnverticesandeedges,thenumberofedgesisDegreeofaVertexHint:Adjacentverticesarecountedtwice.4/21/20238.SimplePath（簡(jiǎn)單路徑）Asimplepathisapathsuchthatallverticesaredistinct,exceptthatthefirstandthelastcouldbethesame.ABCDisasimplepathBCDApath4/21/20239.Cycle（環(huán)）Acycleisapaththatstartsandendsatthesamepoint.Forundirectedgraph,theedgesaredistinct.CBDCisacycleBCDA4/21/202310.Connectedvs.UnconnectedGraph：ConnectedGraph連通圖UnconnectedGraph非連通圖Agraphiscalledconnectedifthereisapathfromanyvertextoanyothervertex.4/21/202311.WeightedGraph（帶權(quán)圖）Weightedgraph:agraphwithnumbersassignedtoitsedgesWeight:cost,distance,traveltime,hop,etc.013220101544/21/202312.stronglyconnectedVs.Weaklyconnected(強(qiáng)連通和弱連通)Adirectedgraphiscalledstronglyconnectedifthereisadirectedpathfromanyvertextoanyothervertex.Ifwesuppressthedirectionoftheedgesandtheresultingundirectedgraphisconnected,wecallthedirectedgraphweaklyconnected.4/21/202313.RepresentationOfGraphTworepresentationsAdjacencyMatrix/Table12.2.1P572AdjacencyList12.2.2P5744/21/202314.AdjacencyMatrix/TableAssumeNnodesingraphUseMatrixA[0…N-1][0…N-1]ifvertexiandvertexjareadjacentingraph,A[i][j]=1,otherwiseA[i][j]=0ifvertexihasaloop,A[i][i]=1ifvertexihasnoloop,A[i][i]=04/21/202315.ImplementationofSetsDeclaration:(1)P573Digraphasabit-stringset:template<intmax_set>structSet{boolis_element[max_set];};template<intmax_size>classDigraph{intcount;//numberofvertices,atmostmaxsizeSet<max_size>neighbors[max_size];};4/21/202316.AdjacencyMatrix/TableDeclaration(2)P574Digraphasanadjacencytable:template<intmax_size>classDigraph{intcount;//numberofvertices,atmostmaxsizebooladjacency[max_size][max_size];};4/21/202317.AdjacencyMatrix/TableDeclaration(2)4/21/202318.ExampleofAdjacencyMatrix/Table鄰接矩陣0132A[i][j]012300110110112110130110So,MatrixA=01101011110101104/21/202319.Undirectedvs.DirectedUndirectedgraphadjacencymatrixissymmetricA[i][j]=A[j][i]DirectedgraphadjacencymatrixmaynotbesymmetricA[i][j]A[j][i]4/21/202320.DirectedGraphA[i][j]0123001111000120001300000132So,MatrixA=01110001000100004/21/202321.WeightedGraphA[i][j]012300201011200052100043154001322010154So,MatrixA=020101200051000415404/21/202322.AdjacencyList鄰接表Anarrayoflisttheithelementofthearrayisalistofverticesthatconnecttovertexi0132012312333vertex0connecttovertex1,2and3vertex1connectsto3vertex2connectsto34/21/202323.WeightedGraphWeightedgraph:extendeachnodewithanadditionfield:weight0132201015401231102203101034020350114254/21/202324.AdjacencyListimplementationtypedefintVertex;template<intmax_size>classDigraph{ intcount;//numberofvertices,atmostmax_size

List<Vertex>neighbors[max_size];};4/21/202325.AdjacencyList4/21/202326.LinkedImplementation

十字鏈表的實(shí)現(xiàn)classEdge;//forwarddeclarationclassVertex{ Edge*first_edge;//startoftheadjacencylist Vertex*next_vertex;//nextvertexonthelinkedlist};classEdge{ Vertex*end_point;//vertextowhichtheedgepoints Edge*next_edge;//nextedgeontheadjacencylist};classDigraph{ Vertex*first_vertex;//headerforthelistofvertices};P576figure12.5(a)4/21/202327.AdjacencyListimplementation4/21/202328.ComparisonOfRepresentationsCostAdjacencyMatrixAdjacencyListGiventwoverticesuandv:findoutwhetheruandvareadjacentO(1)degreeofnodeO(N)Givenavertexu:enumerateallneighborsofuO(N)degreeofnodeO(N)Forallvertices:enumerateallneighborsofeachvertexO(N2)SummationsofallnodedegreeO(E)4/21/202329.GraphTraversalAlgorithmsDepth-firsttraversal

ofagraphisroughlyanalogoustopreordertraversalofanorderedtree.Supposethatthetraversalhasjustvisitedavertexv,andletw1;w2;:::;wkbetheverticesadjacenttov.Thenweshallnextvisitw1andkeepw2;:::;wkwaiting.Aftervisitingw1,wetraversealltheverticestowhichitisadjacentbeforereturningtotraversew2;:::;wk.Breadth-firsttraversal

ofagraphisroughlyanalogoustolevel-by-leveltraversalofanorderedtree.Ifthetraversalhasjustvisitedavertexv,thenitnextvisitsalltheverticesadjacenttov,puttingtheverticesadjacenttotheseinawaitinglisttobetraversedafterallverticesadjacenttovhavebeenvisited.4/21/202330.GraphTraversalAlgorithms4/21/202331.GraphTraversalp577F12.6

Depth-FirstAlgorithmtemplate<intmax_size>voidDigraph<max_size>::depth_first(void(*visit)(Vertex&))const/*Post:Thefunction*visithasbeenperformedateachvertexoftheDigraphindepth-firstorder.Uses:Methodtraversetoproducetherecursivedepth-firstorder.*/{ boolvisited[max_size]; Vertexv; for(allvinG)visited[v]=false; for(allvinG)if(!visited[v])traverse(v,visited,visit);}4/21/202332.GraphTraversalp577F12.6

Depth-FirstAlgorithmtemplate<intmax_size>voidDigraph<max_size>::traverse(Vertex&v,boolvisited[],void(*visit)(Vertex&))const/*Pre:visavertexoftheDigraph.Post:Thedepth-firsttraversal,usingfunction*visit,hasbeencompletedforvandforallverticesthatcanbereachedfromv.Uses:traverserecursively.*/{ Vertexw; visited[v]=true; (*visit)(v); for(allwadjacenttov) if(!visited[w])traverse(w,visited,visit);}4/21/202333.DepthFirstTraversalExampleA’sneighbor:B,C,EB’sneighbor:A,C,FC’sneighbor:A,B,DD’sneighbor:E,C,FE’sneighbor:A,DF’sneighbor:B,DstartfromvertexAABCEFD4/21/202334.DepthFirstTraversal(Cont)InitialStateVisitedVertices{}ProbingVertices{A}UnvisitedVertices{A,B,C,D,E,F}ABCEFDA’sneighbor:BCEB’sneighbor:ACFC’sneighbor:ABDD’sneighbor:ECFE’sneighbor:ADF’sneighbor:BDAstack4/21/202335.DepthFirstTraversal(Cont)Peekavertexfromstack,itisA,markitasvisitedFindA’sfirstunvisitedneighbor,pushitintostackVisitedVertices{A}Probingvertices{A,B}UnvisitedVertices{B,C,D,E,F}ABCEFDA’sneighbor:BCEB’sneighbor:ACFC’sneighbor:ABDD’sneighbor:ECFE’sneighbor:ADF’sneighbor:BDBAstackA4/21/202336.DepthFirstTraversal(Cont)Peekavertexfromstack,itisB,markitasvisitedFindB’sfirstunvisitedneighbor,pushitinstackVisitedVertices{A,B

}ProbingVertices{A,B,C}UnvisitedVertices{C,D,E,F}A’sneighbor:BCEB’sneighbor:ACFC’sneighbor:ABDD’sneighbor:ECFE’sneighbor:ADF’sneighbor:BDCBAstackBAABCEFD4/21/202337.DepthFirstTraversal(Cont)Peekavertexfromstack,itisC,markitasvisitedFindC’sfirstunvisitedneighbor,pushitinstackVisitedVertices{A,B,C

}ProbingVertices{A,B,C,D}UnvisitedVertices{D,E,F}A’sneighbor:BCEB’sneighbor:ACFC’sneighbor:ABDD’sneighbor:ECFE’sneighbor:ADF’sneighbor:BDstackABCEFDDCBACBA4/21/202338.DepthFirstTraversal(Cont)Peekavertexfromstack,itisD,markitasvisitedFindD’sfirstunvisitedneighbor,pushitinstackVisitedVertices{A,B,C,D

}ProbingVertices{A,B,C,D,E}UnvisitedVertices{E,F}A’sneighbor:BCEB’sneighbor:ACFC’sneighbor:ABDD’sneighbor:ECFE’sneighbor:ADF’sneighbor:BDstackABCEFDDCBEADCBA4/21/202339.DepthFirstTraversal(Cont)Peekavertexfromstack,itisE,markitasvisitedFindE’sfirstunvisitedneighbor,novertexfound,PopEVisitedVertices{A,B,C,D,E

}ProbingVertices{A,B,C,D}UnvisitedVertices{F}A’sneighbor:BCEB’sneighbor:ACFC’sneighbor:ABDD’sneighbor:ECFE’sneighbor:ADF’sneighbor:BDstackABCEFDDCBADCBEA4/21/202340.DepthFirstTraversal(Cont)Peekavertexfromstack,itisD,markitasvisitedFindD’sfirstunvisitedneighbor,pushitinstackVisitedVertices{A,B,C,D,E

}ProbingVertices{A,B,C,D,F}UnvisitedVertices{F}A’sneighbor:BCEB’sneighbor:ACFC’sneighbor:ABDD’sneighbor:ECFE’sneighbor:ADF’sneighbor:BDstackABCEFDDCBFADCBA4/21/202341.DepthFirstTraversal(Cont)Peekavertexfromstack,itisF,markitasvisitedFindF’sfirstunvisitedneighbor,novertexfound,PopFVisitedVertices{A,B,C,D,E,F

}ProbingVertices{A,B,C,D}UnvisitedVertices{}A’sneighbor:BCEB’sneighbor:ACFC’sneighbor:ABDD’sneighbor:ECFE’sneighbor:ADF’sneighbor:BDstackABCEFDDCBADCBFA4/21/202342.DepthFirstTraversal(Cont)Peekavertexfromstack,itisD,markitasvisitedFindD’sfirstunvisitedneighbor,novertexfound,PopDVisitedVertices{A,B,C,D,E,F

}ProbingVertices{A,B,C}UnvisitedVertices{}A’sneighbor:BCEB’sneighbor:ACFC’sneighbor:ABDD’sneighbor:ECFE’sneighbor:ADF’sneighbor:BDstackABCEFDCBADCBA4/21/202343.DepthFirstTraversal(Cont)Peekavertexfromstack,itisC,markitasvisitedFindC’sfirstunvisitedneighbor,novertexfound,PopCVisitedVertices{A,B,C,D,E,F

}ProbingVertices{A,B}UnvisitedVertices{}A’sneighbor:BCEB’sneighbor:ACFC’sneighbor:ABDD’sneighbor:ECFE’sneighbor:ADF’sneighbor:BDstackABCEFDBACBA4/21/202344.DepthFirstTraversal(Cont)Peekavertexfromstack,itisB,markitasvisitedFindB’sfirstunvisitedneighbor,novertexfound,PopBVisitedVertices{A,B,C,D,E,F

}ProbingVertices{A}UnvisitedVertices{}A’sneighbor:BCEB’sneighbor:ACFC’sneighbor:ABDD’sneighbor:ECFE’sneighbor:ADF’sneighbor:BDstackABCEFDABA4/21/202345.DepthFirstTraversal(Cont)Peekavertexfromstack,itisA,markitasvisitedFindA’sfirstunvisitedneighbor,novertexfound,PopAVisitedVertices{A,B,C,D,E,F

}ProbingVertices{

}UnvisitedVertices{}A’sneighbor:BCEB’sneighbor:ACFC’sneighbor:ABDD’sneighbor:ECFE’sneighbor:ADF’sneighbor:BDstackABCEFD

A4/21/202346.DepthFirstTraversal(Cont)NowprobinglistisemptyEndofDepthFirstTraversalVisitedVertices{A,B,C,D,E,F

}ProbingVertices{

}UnvisitedVertices{}A’sneighbor:BCEB’sneighbor:ACFC’sneighbor:ABDD’sneighbor:ECFE’sneighbor:ADF’sneighbor:BDstackABCEFD

4/21/202347.GraphTraversalp577F12.6

Breadth-FirstAlgorithmtemplate<intmax_size>voidDigraph<max_size>::breadth_first(void(*visit)(Vertex&))const/*Post:Thefunction*visithasbeenperformedateachvertexoftheDigraphinbreadth-firstorder.Uses:MethodsofclassQueue.*/{ Queueq; boolvisited[max_size]; Vertexv,w,x; for(allvinG)visited[v]=false; for(allvinG) if(!visited[v]){ q.append(v); while(!q.empty()){ q.retrieve(w); if(!visited[w]){ visited[w]=true; (*visit)(w); for(allxadjacenttow)q.append(x); } q.serve(); } }}4/21/202348.BreadthFirstTraversalProbingListisimplementedasqueue(FIFO)ExampleA’sneighbor:BCEB’sneighbor:ACFC’sneighbor:ABDD’sneighbor:ECFE’sneighbor:ADF’sneighbor:BDstartfromvertexAABCEFD4/21/202349.BreadthFirstTraversal(Cont)InitialStateVisitedVertices{}ProbingVertices{A}UnvisitedVertices{A,B,C,D,E,F}ABCEFDA’sneighbor:BCEB’sneighbor:ACFC’sneighbor:ABDD’sneighbor:ECFE’sneighbor:ADF’sneighbor:BDAqueue4/21/202350.BreadthFirstTraversal(Cont)Deletefirstvertexfromqueue,itisA,markitasvisitedFindA’sallunvisitedneighbors,markthemasvisited,putthemintoqueueVisitedVertices{A}ProbingVertices{B,C,E}UnvisitedVertices{D,F}ABCEFDA’sneighbor:BCEB’sneighbor:ACFC’sneighbor:ABDD’sneighbor:ECFE’sneighbor:ADF’sneighbor:BDAqueueBEC4/21/202351.BreadthFirstTraversal(Cont)Deletefirstvertexfromqueue,itisB,markitasvisitedFindB’sallunvisitedneighbors,markthemasvisited,putthemintoqueueVisitedVertices{A,B,}ProbingVertices{C,E,F}UnvisitedVertices{D}ABCEFDA’sneighbor:BCEB’sneighbor:ACFC’sneighbor:ABDD’sneighbor:ECFE’sneighbor:ADF’sneighbor:BDBECqueueCFE4/21/202352.BreadthFirstTraversal(Cont)Deletefirstvertexfromqueue,itisC,markitasvisitedFindC’sallunvisitedneighbors,markthemasvisited,putthemintoqueueVisitedVertices{A,B,C,}ProbingVertices{E,F,D}UnvisitedVertices{}ABCEFDA’sneighbor:BCEB’sneighbor:ACFC’sneighbor:ABDD’sneighbor:ECFE’sneighbor:ADF’sneighbor:BDCFEqueueEDF4/21/202353.BreadthFirst