【精品数据结构】Graph Applications.ppt

《【精品数据结构】Graph Applications.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、GraphApplicationsModelingconnectivityincomputernetworksRepresentingmapsModelingflowcapacitiesinnetworksFindingpathsfromstarttogoal(AI)ModelingtransitionsinalgorithmsOrderingtasksModelingrelationships(families,organizations)GraphsAgraphG=(V,E)consistsofasetofverticesV,andase

2、tofedgesE,suchthateachedgeinEisaconnectionbetweenapairofverticesinV.Thenumberofverticesiswritten

3、V

4、,andthenumberedgesiswritten

5、E

6、.Graphs(2)PathsandCyclesPath:Asequenceofverticesv1,v2,…,vnoflengthn-1withanedgefromvitovi+1for1<=i

7、ct.Acycleisapathoflength3ormorethatconnectsvitoitself.Acycleissimpleifthepathissimple,exceptthefirstandlastverticesarethesame.ConnectedComponentsAnundirectedgraphisconnectedifthereisatleastonepathfromanyvertextoanyother.Themaximumconnectedsubgraphsofanundirectedgrapharecall

8、edconnectedcomponents.DirectedRepresentationUndirectedRepresentationRepresentationCostsAdjacencyMatrix:AdjacencyList:GraphADTclassGraph{//Graphabstractclasspublic:virtualintn()=0;//#ofverticesvirtualinte()=0;//#ofedges//Returnindexoffirst,nextneighborvirtualintfirst(int)=0;

9、virtualintnext(int,int)=0;//StorenewedgevirtualvoidsetEdge(int,int,int)=0;//DeleteedgedefinedbytwoverticesvirtualvoiddelEdge(int,int)=0;//Weightofedgeconnectingtwoverticesvirtualintweight(int,int)=0;virtualintgetMark(int)=0;virtualvoidsetMark(int,int)=0;};GraphTraversalsSom

10、eapplicationsrequirevisitingeveryvertexinthegraphexactlyonce.Theapplicationmayrequirethatverticesbevisitedinsomespecialorderbasedongraphtopology.Examples:ArtificialIntelligenceSearchShortestpathsproblemsGraphTraversals(2)Toinsurevisitingallvertices:voidgraphTraverse(constGr

11、aph*G){for(v=0;vn();v++)G->setMark(v,UNVISITED);//Initializefor(v=0;vn();v++)if(G->getMark(v)==UNVISITED)doTraverse(G,v);}DepthFirstSearch(1)//DepthfirstsearchvoidDFS(Graph*G,intv){PreVisit(G,v);//TakeactionG->setMark(v,VISITED);for(intw=G->first(v);wn();w=G->ne

12、xt(v,w))if(G->getMark(w)==UNVISITED)DFS(G,w);PostVisit(G,v);//Takeaction}DepthFirs