欢迎来到天天文库
浏览记录
ID:50726053
大小:366.50 KB
页数:37页
时间:2020-03-16
《【精品数据结构】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<=i7、ct.Acycleisapathoflength3ormorethatconnectsvitoitself.Acycleissimpleifthepathissimple,exceptthefirstandlastverticesarethesame.ConnectedComponentsAnundirectedgraphisconnectedifthereisatleastonepathfromanyvertextoanyother.Themaximumconnectedsubgraphsofanundirectedgrapharecall8、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;};GraphTraversalsSom10、eapplicationsrequirevisitingeveryvertexinthegraphexactlyonce.Theapplicationmayrequirethatverticesbevisitedinsomespecialorderbasedongraphtopology.Examples:ArtificialIntelligenceSearchShortestpathsproblemsGraphTraversals(2)Toinsurevisitingallvertices:voidgraphTraverse(constGr11、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->ne12、xt(v,w))if(G->getMark(w)==UNVISITED)DFS(G,w);PostVisit(G,v);//Takeaction}DepthFirs
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
此文档下载收益归作者所有