数据结构与算法 第六章 图

“”©©Page2„6.1„6.2„6.3„6.4„6.5„6.6©Page36.1„G=VE„Vvertex„Eedge„„„sparsegraph„densegraph„completegraph©Page46.1„undirectedgraph„„directedgraphdigraph„©Page56.1©Page66.1„labeledgraph„weightedgraph©Page76.1„degree„„(indegree)„(outdegree)„subgraph„G=(VE)G’=(V’E’)V’VE’EE’V’G’G©Page86.1„path„G=(VE)VpVi1Vi2…VinVqVpVi1(Vi1Vi2)…(VinVq)VpVi1Vi1Vi2…VinVqEVpVq„simplepath„length©Page96.1„cycle„“”3„V0V1V1V0„simplecycle„acyclicgraph„directedacyclicgraphDAG©Page106.1„„V0V0„„connected„G=VEV1V2V2V1V1V2connected„©Page116.1„connectedcomponent„„„„„freetree„|V|-1©Page126.2„„?„?©Page136.2classGraph{//ADTpublic:intVerticesNum();//intEdgesNum();////oneVertexEdgeFirstEdge(intoneVertex);//PreEdgeoneVertex//EdgeNextEdge(EdgepreEdge);©Page14//boolsetEdge(intfromVertex,inttoVertex,intweight);//booldelEdge(intfromVertex,inttoVertex);//oneEdgeTRUEFALSEboolIsEdge(EdgeoneEdge);//oneEdgeintFromVertex(EdgeoneEdge);//oneEdgeintToVertex(EdgeoneEdge);//oneEdgeintWeight(EdgeoneEdge);};©Page156.3„6.3.1adjacencymatrix„6.3.2adjacencylist„(adjacencymultilist)©Page166.3.1adjacencymatrix„„„GnGn×nA[i,j]=1ViVjViVjGA[i,j]=0ViVjViVjG„(n2)©Page176.3.1adjacencymatrixA7=0100010001010101000000010⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦©Page186.3.1adjacencymatrixA4=030153040040615060⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦©Page196.3.2adjacencylistG6G7©Page206.3.2adjacencylistG6©Page216.3.2adjacencylistG7G7©Page22(adjacencymultilist)„„„„„©Page23(adjacencymultilist)G6©Page24(adjacencymultilist)„„„„„„„©Page25(adjacencymultilist)G7©Page266.3.2adjacencylist„nm„(n+2m)„nm„(n+m)©Page276.4„graphtraversal„GV0V0G©Page286.4„„„„„„markbit„„©Page296.4//voidgraph_traverse(Graph&G){//for(inti=0;iG.VerticesNum();i++)G.Mark[i]=UNVISITED;//////do_traversefor(inti=0;iG.VerticesNum();i++)if(G.Mark[i]==UNVISITED)do_traverse(G,i);}©Page306.4„„„©Page316.4.1„depth-firstsearchDFS„VV’„V’„UW„W„„depth-firstsearchtree©Page326.4.1abcfdeg©Page336.4.1voidDFS(Graph&G,intV){//G.Mark[V]=VISITED;//VPreVisit(G,V);//Vfor(Edgee=G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e))//V//if(G.Mark[G.ToVertices(e)]==UNVISITED)DFS(G,G.ToVertices(e));PostVisit(G,V);//V}©Page346.4.1„DFS„(|V|+|E|)(|V|+2|E|)„(|V|2)(|V|+|V|2)=(|V|2)©Page356.4.2„breadth-firstsearchBFS„V0„V0V01V02…V0i„V01V02…V0i„„breadth-firstsearchtree©Page366.4.2abdefcg©Page37voidBFS(Graph&G,intV){////usingstd::queue;queueintQ;//VVG.Mark[V]=VISITED;Visit(G,V);Q.push(V);while(!Q.empty()){//intV=Q.front();Q.pop();////for(Edgee=G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e))if(G.Mark[G.ToVertex(e)]==UNVISITED){G.Mark[G.ToVertex(e)]=VISITED;Visit(G,G.ToVertex(e));Q.push(G.ToVertex(e));//}//Endofif}//Endofwhile}//EndofBFS©Page386.4.2„©Page396.4.3C1C2C3C1C2C4C2C3C5C2C6C4C5C7C4C9C8C1C9C8©Page40©Page41„„topologicalsort„©Page42„„G=VEV„GViVjViVj©Page436.4.3„DAG„10„2„31©Page44voidTopsortbyQueue(Graph&G){for(inti=0;iG.VerticesNum();i++)G.Mark[i]=UNVISITED;//usingstd::queue;queueintQ;//for(i=0;iG.VerticesNum();i++){if(G.Indegree[i]==0)Q.push(i);//0}©Page45while(!Q.empty()){//intV=Q.front();//Q.pop();//Visit(G,V);//G.Mark[V]=VISITED;//e1for(Edgee=G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e)){G.Indegree[G.ToVertex(e)]--;if(G.Indegree[G.ToVertex(e)]==0)Q.push(G.ToVertex(e));//0}}©Page46for(i=0;iG.VerticesNum();i++)if(G.Mark[i]==UNVISITED){Print(“”);//break;}}//EndofTopsortbyQueue()©Page47„„©Page48:C7,C9,C8,C6,C4,C3,C1,C5,C2,C2,C5,C1,C3,C4,C6,C8,C9,C7©Page49:C7,C4,C3,C9,C8,C1,C6,C5,C2C2,C5,C6,C1,C8,C9,C3,C4,C7©Page50int*TopsortbyDFS(Graph&G){//for(inti=0;iG.VerticesNum();i++)//G.Mark[i]=UNVISITED;int*result=newint[G.VerticesNum()];intindex=0;for(i=0;iG.VerticesNum();i++)//if(G.Mark[i]==UNVISITED)Do_topsort(G,i,result,index);//for(i=G.VerticesNum()-1;i=0;i--)//Visit(G,result[i]);returnresult;}©Page51voidDo_topsort(Graph&G,intV,int*result,int&index){G.Mark[V]=VISITED;for(Edgee=G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e)){//Vif(G.Mark[G.ToVertex(e)]==UNVISITED)Do_topsort(G,G.ToVertex(e),result,index);}//result[index++]=V;}©Page52„„„„(|V|+|E|)„(|V|2)„©Page53„„(|V|2)„(|V|+|E|)©Page546.5„6.5.1Dijstra„G=VEsVs„6.5.2Floyd„G=VEViVjVViVj©Page55V145251060∞©Page56Dijstra„„„„„s©Page57„ss„s„s©Page58Dijkstra„s„s0„sVisViViVi„Vm©Page59„Vm„VmsViVmVi„„……„©Page60V1©Page616.5.1DijkstraV1©Page62„DistClassDist{intlength;//sintpre;//};©Page63DijkstraDist*Dijkstra(Graph&G,ints){Dist*D=newDist[G.VerticesNum()];//MarkD//minVertexMarkfor(inti=0;iG.VerticesNum();i++){G.Mark[i]=UNVISITED;D[i].length=INFINITY;D[i].pre=s;}D[s].length=0;©Page64for(i=0;iG.VerticesNum();i++){intv=minVertex(G,D);//sif(D[v].length==INFINITY)break;G.Mark[v]=VISITED;//Visit(G,v);////DvDistfor(Edgee=G.FirstEdge(v);G.IsEdge(e);e=G.NextEdge(e)){if(D[G.ToVertex(e)].lengthD[v].length+G.Weight(e)){D[G.ToVertex(e)].length=D[v].length+G.Weight(e);D[G.ToVertex(e)].pre=v;}}}returnD;}©Page65Dijstra„minVertex()D„for(i=0;iG.VerticesNum();i++)|V|„minVertex()|V||V|2„D|E|(|V|+|E|)„(|V|2)©Page66minVertex()„D[i].length„„()„VISITED©Page67„(|V|)(|E|)„„((|V|+|E|)log|E|)„©Page686.5.2„|V|DijstraVoidDijkstra_P2P(Graph&G){Dist**D=newDist*[G.Vertice