数据结构-图.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,图是复杂的非线性结构,顶点的前趋和后继个数不加限制，顶点间关系是任意的，任意两个顶点间可能相关。,应用广泛,2.6,图,定义：,图是由,顶点集,合,(vertex),及顶点间的,关系集,合组成的一种数据结构：,Graph,(V,E),其中,:,V=x|x,某个数据对象,是顶点的非空有穷集合；,E1=(x,y)|x,y,V,或,E2=|x,y,V,E1,是顶点间关系的有穷集合，也叫做边,(edge),集合，此时的图称为,无向图,。,E2,表示从,x,到,y,的一条弧，且称,x,为弧尾，,y,为弧头，这样的图称为,有向图,。,2.6.1,图的定义及基本术语,不考虑顶点到自身的边或弧。,有向图与无向图,在有向图中，,是有序顶点对；在无向图中，,(x,y),是无序顶点对。,完全图,若有,n,个顶点的无向图有,n(n-1)/2,条边,则此图为,无向完全图,。有,n,个顶点的有向图有,n(n-1),条边,则此图为,有向完全图,。,0,0,0,0,1,1,1,1,2,2,2,2,6,5,4,3,3,2.6.1,图的定义及基本术语,完全图有最多的边数、弧数。,邻接顶点,如果,(u,v),是,E(G),中的一条边，则称,u,与,v,互为邻接顶点。,子图,设有两个图,G,(V,E),和,G,(V,E),。,若,V,V,且,E,E,则称 图,G,是 图,G,的子图。,权,某些图的边具有与它相关的数,称之为权。这种带权图叫做,网络,。,0,1,2,3,子图,0,1,3,0,1,2,3,0,2,3,2.6.1,图的定义及基本术语,顶点的度,一个顶点,v,的度是与它相关联的边的条数。记作,TD(v),。,在有向图中,顶点的度等于该顶点的入度与出度之和：,TD(v,)=,ID(v)+OD(v,),。,顶点,v,的入度,是以,v,为终点的有向边的条数,记作,ID(v);,顶点,v,的出度,是以,v,为始点的有向边的条数,记作,OD(v),。,路径,在图,G=(V,E),中,若从顶点,v,i,出发,沿一些边经过一些顶点,v,p1,v,p2,v,pm,，,到达顶点,v,j,。,则称顶点序列,(v,i,v,p1,v,p2,.v,pm,v,j,),为从,顶点,v,i,到顶点,v,j,的路径,。它经过的边,(v,i,v,p1,),、,(v,p1,v,p2,),、,.,、,(v,pm,v,j,),应是属于,E,的边。,2.6.1,图的定义及基本术语,顶点的出度,:,以顶点,v,为弧尾的弧的数目,;,顶点的入度,:,以顶点,v,为弧头的弧的数目。,A,B,E,C,F,有向图,顶点的度,(,TD,)=,出度,(,OD,)+,入度,(,ID,),TD(B)=OD(B)+ID(B)=3,例如,:,路径长度,非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。,简单路径,若路径上各顶点,v,1,v,2,.,v,m,均不互相重复,则称这样的路径为简单路径。,简单回路,若路径上第一个顶点,v,1,与最后一个顶点,v,m,重合,则称这样的路径为回路或,环,。,0,1,2,3,0,1,2,3,0,1,2,3,2.6.1,图的定义及基本术语,A,B,E,C,F,如,:,从,A,到,F,长度为,3,的路径,A,B,C,F,连通图与连通分量,在无向图中,若从顶点,v,i,到顶点,v,j,有路径,则称顶点,v,i,与,v,j,是连通的。如果图中任意一对顶点都是连通的,则称此图是,连通图,。,非连通图的极大连通子图叫做连通分量。,强连通图与强连通分量,在有向图中,若对于每一对顶点,v,i,和,v,j,都存在一条从,v,i,到,v,j,和从,v,j,到,v,i,的路径,则称此图是,强连通图,。,非强连通图的极大强连通子图叫做强连通分量。,2.6.1,图的定义及基本术语,连通图的连通分量是自身。,强连通图的强连通分量是自身。,无向图,若图中任意两个顶点之间都有路径相通，则称此图为,连通图,若无向图为非连通图，则图中各个极大连通子图称作此图的,连通分量,。,B,A,C,D,F,E,B,A,C,D,F,E,有向图,若任意两个顶点之间都存在一条有向路径，则称此有向图为,强连通图,。,否则，其各个强连通子图称作它的,强连通分量,。,A,B,E,C,F,A,B,E,C,F,2.6.1,图的定义及基本术语,2.6.2,图的存储结构,在图的邻接矩阵表示中，有一个记录各个顶点信息的,顶点表,(,一维数组,),，还有一个表示各个顶点之间关系的,邻接矩阵,(,二维数组,),。,设图,A=(V,E),是一个有,n,个顶点的图,图的邻接矩阵是一个,二维数组,A.edgenn,，,定义：,邻接矩阵,(Adjacency Matrix),图的结构比较复杂，无法以数据元素在存储区的物理位置来表示元素间的关系，所以无法用顺序存储结构。,无向图的邻接矩阵是对称的,(,压缩存储,),;,有向图的邻接矩阵可能是不对称的。,0,1,2,3,0,1,2,在有向图中,统计第,i,行,1,的个数可得顶点,i,的出度，统计第,j,列,1,的个数可得顶点,j,的入度。,在无向图中,统计第,i,行(列)1 的个数可得顶点,i,的度。,2.6.2,图的存储结构,1,8,6,3,2,9,5,4,2,0,3,1,网络的邻接矩阵,2.6.2,图的存储结构,const int NumEdges=50;,/,边条数,const int NumVertices=10;,/,顶点个数,typedef char VertexData;,/,顶点数据类型,typedef int EdgeData;,/,边上权值类型,typedef struct,VertexData vexListNumVertices;,/,顶点表,EdgeData EdgeNumVerticesNumVertices;,/,邻接矩阵,可视为边之间的关系,int n,e;,/,图中当前的顶点个数与边数,MTGraph;,用邻接矩阵表示的结构定义,2.6.2,图的存储结构,邻接表,(Adjacency List),：,图的一种链式存储结构。,(,边表,),边,/,弧结点结构,adjvex,;,/,邻接域，,与顶点,vi,邻接的边,/,弧所指向的顶点的位置,nextarc;,/,链域，,指向下一条边,/,弧指针,info;,/,数据域，,该边,/,弧相关权值信息,adjvex,info,nextarc,(,顶点表,),顶点的结点结构,data,firstarc,data;,/,顶点信息,firstarc,;,/,指向第一条依附该顶点的边,/,弧,2.6.2,图的存储结构,无向图的邻接表,同一个顶点,V,i,发出的边链接在同一个边表中，每一个边结点代表一条边,结点中有与,V,i,邻接顶点的下标和指针。,A,B,C,D,data,first,A,B,C,D,0,1,2,3,adj,next,1,3,0,2,1,0,2.6.2,图的存储结构,adj,next,边表,顶点表,有向图的邻接表和逆邻接表,A,B,C,A,B,C,0,1,2,邻接表,(,出边表,),A,B,C,0,1,2,逆邻接表,(,入边表,),1,0,2,0,1,1,2.6.2,图的存储结构,data,first,adj,next,adj,next,data,first,adj,next,B,A,C,D,6,9,5,2,8,A,B,C,D,0,1,2,3,1,5,3,6,2,8,3,2,1,9,(,出边表,),(,顶点表,),2.6.2,图的存储结构,网络,(,带权图,),的邻接表,data,first,adj,info,next,带权图的边结点中保存该边上的权值,info,。,顶点,i,的边表的表头指针,adj,在顶点表的下标为,i,的顶点记录中，该记录还保存了该顶点的,data,信息。,在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。,设图中,有,n,个顶点,，,e,条边，则用邻接表表示无向图时，需要,n,个顶点结点，,2e,个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需,n,个顶点结点，,e,个边结点,。,2.6.2,图的存储结构,邻接矩阵是唯一的，但邻接表不唯一。,typedef char VertexData;,/,顶点数据类型,typedef int EdgeData;,/,边上权值类型,typedef struct node,/,边结点,int,dest,;,/,目标顶点下标,EdgeData,cost,;,/,边上的权值,Struct,node*,link,;,/,下一边链接指针,EdgeNode,;,邻接表表示的图的定义,(,为算法,),2.6.2,图的存储结构,typedef struct,/,顶点结点,VertexData data;,/,顶点数据域,EdgeNode,*,firstAdj,;,/,边链表头指针,VertexNode,;,typedef struct,/,图的邻接表,VertexNode,VexList,NumVertices;,/,邻接表,int n,e;,/,图中当前的顶点个数与边数,AdjGraph,;,2.6.2,图的存储结构,void CreateGraph(,AdjGraph,G),cin,G.n G.e;,/,输入顶点个数和边数,for(int i=0;i,G.VexListi.data,;,/,输入顶点信息,G.VexListi.firstAdj,=NULL;,for(i=0;i tail head weight;,/tail,和,head,是下标,EdgeNode,*p=new,EdgeNode,;,p-,dest,=head;p-cost=weight;,邻接表的构造算法,(,无向图,),2.6.2,图的存储结构,/,链入第,tail,号链表的前端,p,-,link,=,G.VexListtail.firstAdj,;,G.VexListtail.firstAdj,=p;,p=new,EdgeNode,;,p,-,dest,=tail;p,-,cost=weight;,/,链入第,head,号链表的前端,p,-,link,=,G.VexListhead.firstAdj,;,G.VexListhead.firstAdj,=p;,2.6.3,图的遍历,从图中某一顶点出发访遍图中所有的顶点，且使每个顶点仅被访问一次，这一过程就叫做,图的遍历,(Traversing Graph),。,图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。,为了避免重复访问，可设置一个标志顶点是否被访问过的,辅助数组,visited,。,辅助数组,visited ,的初始状态为,0,在图的遍历过程中,一旦某一个顶点,i,被访问,就立即让,visited i,为,1,防止它被多次访问。,两种图的遍历方法,:,深度优先搜索,DFS(Depth First Search),广度优先搜索,BFS(Breadth First Search),2.6.3,图的遍历,深度优先搜索,DFS(Depth First Search),深度优先搜索过程,6,7,A,C,D,E,G,B,F,I,H,A,C,D,E,G,B,F,I,H,1,2,3,4,5,8,9,1,2,3,4,5,6,7,8,9,前进,回退,深度优先生成树,2.6.3,图的遍历,DFS,在访问图中某一起始顶点,v,后,由,v,出发,访问它的任一邻接顶点,w,1,;,再从,w,1,出发,访问与,w,1,邻接但还没有访问过的顶点,w,2,;,然后再从,w,2,出发,进行类似访问,如此,直至到达所有的邻接顶点都被访问过的顶点,u,为止。,接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问,(,递归,),;,如果没有,就再退回一步进行搜索。,重复上述过程,直到连通图中所有顶点都被访问过为止,。,2.6.3,图的遍历,void Graph_Traverse(,AdjGraph,G),int*visited=new int NumVertices;,for(int i=0;i G.n;i+),visited i=0;,/,访问数组,visited,初始化,for(int i=0;i G.n;i+),if(!visitedi)DFS(G,i,visited);,/,从顶点,i,出发开始搜索,delete visited,;,/,释放,visited,图的深度优先搜索算法,2.6.3,图的遍历,DFS,被调用几次就有几个连通分量。,void DFS(,AdjGraph,G,int v,int visited ),cout,GetValue,(G,v);,/,访问顶点,v,visitedv=1;,/,顶点,v,作访问标记,int w=,GetFirstNeighbor,(G,v);,/,取,v,的第一个邻接顶点,w,while(w!=,-,1),/,若邻接顶点,w,存在,if(!visitedw)DFS(G,w,visited);,/,若,顶点,w,未访问过,递归访问顶点,w,w=,GetNextNeighbor,(G,v,w);,/,取顶点,v,排在,w,后的下一个邻接顶点,2.6.3,图的遍历,广度优先搜索,BFS(Breadth First Search),广度优先搜索过程,A,C,D,E,G,B,F,I,H,A,C,D,E,G,B,F,H,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,广度优先生成树,I,2.6.3,图的遍历,BFS,在访问了起始顶点,v,之后,由,v,出发,依次访问,v,的各个未被访问过的邻接顶点,w1,w2,wt,然后再顺序访问,w1,w2,wt,的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，,如此做下去，直到图中所有顶点都被访问到为止。,广度优先搜索是一种,分层,的搜索过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况。因此,广度优先搜索,不是一个递归的过程,。,2.6.3,图的遍历,为了实现逐层访问,算法中使用了一个,队列,以记忆正在访问的这一层和下一层的顶点,以便于向下一层访问。,为避免重复访问,需要一个辅助数组,visited ,，,给被访问过的顶点加标记。,2.6.3,图的遍历,void Graph_Traverse(,AdjGraph,G),for(int i=0;i G.n;i+),if(!visitedi)BFS(G,i,visited);,图的广度优先搜索算法,2.6.3,图的遍历,void BFS(,AdjGraph,G,int v,int visited ),cout,GetValue,(v);visitedv=1;,Queue q;,InitQueue(&q,);,EnQueue,(,/,进队列,while(!,QueueEmpty,(&q),/,队空搜索结束,DeQueue,(,int w=,GetFirstNeighbor,(G,v);,while(w!=,-,1),/,若邻接顶点,w,存在,if(!visitedw),/,未访问过,cout,GetValue,(w);,2.6.3,图的遍历,visitedw=1;,EnQueue,(,w=,GetNextNeighbor,(G,v,w);,/,重复检测,v,的所有邻接顶点,/,外层循环，判队列空否,delete visited;,DFS,和,BFS,的空间复杂度：,O(n,),辅助空间,(,栈和队列,),，每个顶点最多进一次栈或队。,DFS,和,BFS,的时间复杂度：,邻接表存储：,O(e,),；邻接矩阵存储：,O(n,2,),一个图的访问序列不是唯一的，它与算法、图的存储结构以及初始出发点有关。,因为邻接矩阵表示唯一，所以,DFS,序列唯一。,邻接表表示不唯一，所以,DFS,序列不唯一,2.6.3,图的遍历,当无向图为非连通图时,从图中某一顶点出发,利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点,只能访问到该顶点所在的最大连通子图,(,连通分量,),的所有顶点。,对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。,非连通图的遍历,2.6.3,图的遍历,A,C,D,E,I,B,F,O,G,H,J,N,M,L,K,非连通无向图的三个连通分量,应用问题：,设用有向网中,顶点,表示城市，,弧,表示城市间的交通路线，弧上的,权,表示两点之间的交通路线长度，要求求出从某个城市出发到其余各个城市之间的最短路径。,最短路径问题：,如果从图中某一顶点,(,称为,源点,),到达另一顶点,(,称为,终点,),的路径可能不只一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。,迪杰斯特拉,(,Dijkstra,),提出按,路径长度递增,的次序产生从源点到其余各顶点的最短路径的算法。,2.6.4,图的应用,最短路径,(Shortest Path),引入辅助数组,dist,。每个分量,disti,表示当前找到的从,源点,v,0,到,终点,v,i,的最短路径的长度。初始状态：,若从源点,v,0,到顶点,v,i,有边,则,disti,为该边上的权值；,若从源,点,v,0,到顶点,v,i,无边,则,disti,为,。,假设,S,是已求得的最短路径的终点的集合，可证明：,下一条最短路径必然是,从,v,0,出发，中间只经过,S,中的顶点便可到达的那些顶点,v,x,(,v,x,V,-S),的路径中的一条。,每次求得一条最短路径后,其终点,v,k,加入集合,S,，,然后,对所有,的,v,i,V,-S,，,修改其,disti,值,。,2.6.4,图的应用,迪杰斯特拉,(,Dijkstra,),算法的基本思想：,Dijkstra,算法,初始化：,S v,0,;,distj Edge0j,j=1,2,n-1,;(n,为图中顶点数,),求出最短路径的长度：,distk min disti,i,V-S;,S S,U,k,;,对于每一个,i,V,-S;,修改：,disti min disti,distk+Edgeki,判断：若,S=V,则算法结束，否则转,。,2.6.4,图的应用,v,v,k,v,i,edge,ki,disti,distk,举例：,Dijkstra,逐步求解的过程,1,0,4,3,2,10,100,30,50,20,60,10,源点,s,终点 最短路径,path,路径长度,dist,v,0,v,0,v,1,(,v,0,v,1,)10,v,0,1,v,2,(,v,0,v,1,v,2,),(,v,0,v,3,v,2,),60,50,v,0,1,3,v,3,(,v,0,v,3,)30,v,0,1,3,2,v,4,(,v,0,v,4,),(,v,0,v,3,v,4,),(,v,0,v,3,v,2,v,4,),100,90,60,v,0,1,3,2,4,void,ShortestPath,(MTGraph G,int,v),/,MTGraph,是一个有,n,个顶点的带权有向图,各边上的权值由,Edgeij,给出。,/,distj,0,jn,是当前求到的从顶点,v,到顶点,j,的最短路径长度,用数组,pathj,0,jn,存放求到的最短路径。,EdgeData,distG.n,;,/,最短路径长度数组,int,pathG.n,;,/,最短路径数组,int,SG.n,;,/,最短路径顶点集,计算从单个顶点到其它各顶点最短路径,2.6.4,图的应用,for(int i=0;i n;i+),disti=G.Edgevi;,/dist,数组初始化,Si=0;,/,集合,S,初始化,if(i!=v&disti MaxValue),pathi=v;,else pathi=-1;,/path,数组初始化,Sv=1;distv=0;,/,顶点,v,加入顶点集合,for(i=0;i n-1;i+),#,/,从顶点,v,确定,n-1,条路径,float min=MaxValue;int u=v;,2.6.4,图的应用,for(int j=0;j n;j+),/,选当前不在集合,S,中具有最,if(!Sj&distj min),短路径的顶点,u,u=j;min=distj;,Su=1;,/,将顶点,u,加入集合,S,，,表示它已在最短路径上,for(int w=0;w n;w+),/,修改,if(!Sw&G.Edgeuw MaxValue,&distu+G.Edgeuw distw),/,顶点,w,未加入,S,且经过,u,可以缩短路径,distw=distu+G.Edgeuw;,pathw,=u;,/,修改到,w,的最短路径,#,/,选定各顶点到顶点,v,的最短路径,/,打印各顶点的最短路径,:,路径是逆向输出的,for(i=0;i G.n;i+),cout,endl,;,cout,“Distance:”disti,“Path:”i;,/,输出终点的最短路径长度和终点,int pre=pathi;,/,取终点的直接前驱,while(pre!=,v,),/,沿路径上溯输出,cout,“,”pre;,pre=pathpre;,拓扑排序,计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“,活动,”的,子工程,。完成了这些活动，这个工程就可以完成了。,例：,计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。,顶点表示活动的网络,(Activity On Vertex Network/AOV,网络,),2.6.4,图的应用,C,1,高等数学,C,2,程序设计基础,C,3,离散数学,C,1,C,2,C,4,数据结构,C,3,C,2,C,5,高级语言程序设计,C,2,C,6,编译方法,C,5,C,4,C,7,操作系统,C,4,C,9,C,8,普通物理,C,1,C,9,计算机原理,C,8,课程代号 课程名称 先修课程,学生课程学习工程图,C,8,C,3,C,5,C,4,C,9,C,6,C,7,C,1,C,2,可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边,表示活动,V,i,必须先于活动,V,j,进行。这种有向图叫做,顶点表示活动,的,AOV,网络,(Activity On Vertex),。,在,AOV,网络中不能出现有向回路,即有向环。如果出现了有向环，则意味着某项活动应以自己作为先决条件。,因此，,对给定的,AOV,网络，必须先判断它是否存在有向环。,2.6.4,图的应用,检测有向环的一种方法是对,AOV,网络构造它的拓扑有序序列。即将各个顶点,(,代表各个活动,),排列成一个,线性有序的序列,，使得,AOV,网络中所有应存在的前驱和后继关系都能得到满足。,这种构造,AOV,网络全部顶点的拓扑有序序列的运算就叫做,拓扑排序。,如果通过拓扑排序能,将,AOV,网络的所有顶点都排入一个拓扑有序的序列中,则该网络中必定不会出现有向环。,2.6.4,图的应用,如果,AOV,网络中存在有向,环，此,AOV,网络所代表的工程是不可行的。,例如,对学生选课工程图进行拓扑排序,得到的拓扑有序序列为,C1,C2,C3,C4,C5,C6,C8,C9,C7,或,C1,C8,C9,C2,C5,C3,C4,C7,C6,C,8,C,3,C,5,C,4,C,9,C,6,C,7,C,1,C,2,2.6.4,图的应用,拓扑排序的方法,输入,AOV,网络,。令,n,为顶点个数。,在,AOV,网中选一个没有直接前驱的顶点,并输出之,;,从图中删去该顶点,同时删去所有它发出的有向边,;,重复以上,、,步,直到,全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或,图中还有未输出的顶点,但已跳出处理循环。说明图中还剩下一些顶点,它们都有直接前驱。这时网络中必存在有向环。,2.6.4,图的应用,C0,C1,C2,C3,C4,C5,拓扑排序的过程,(a),有向无环图,C2,C5,C1,C0,C3,(b),输出顶点,C4,C1,C2,C5,C3,(c),输出顶点,C0,C4,C0,C2,C5,C1,C3,(d),输出顶点,C3,C1,C2,C5,(e),输出顶点,C2,C5,C1,(f),输出顶点,C1,C5,(g),输出顶点,C5,拓扑有序序列为,C,4,C,0,C,3,C,2,C,1,C,5,。,它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点,(,如,C,4,和,C,2,),，也排出了先后次序。,(h),拓扑排序完成,AOV,网络及其邻接表表示,C0,C1,C2,C3,C4,C5,C0,C1,C2,C3 0,C4,C5 0,0,1,2,3,4,5,count data,adj,1,3,0,1,0,3,1,dest,link,3 0,5,1,5 0,0,1,5 0,在邻接表中增设一个,数组,count,，,记录各顶点入度。入度为零的顶点即,无前驱顶点,。,在输入数据前,顶点,表,VexList,和,入度数组,count,全部初始化,。,在输入数据时,每输入一条边,就需要建立一个边结点,并将它链入相应边链表中,统计入度信息：,EdgeNode,*p=new,EdgeNode,;,p-,dest,=k;,/,建立边结点,p-link=,G.VexListj.firstAdj,;,VexListj.firstAdj,=p;,/,链入顶点,j,的边链表的前端,countk,+;,/,顶点,k,入度加一,2.6.4,图的应用,在算法中,使用一个存放入度为零的,顶点,的链式,栈,供选择和输出无前驱的顶点。,拓扑排序算法：,建立入度为零的顶点栈,;,当入度为零的顶点栈不空时,重复执行,从顶点栈中退出一个顶点,并输出之,;,从,AOV,网络中删去这个顶点和它发出的边,边的终顶点入度减一,;,如果边的终顶点入度减至,0,则该顶点进入度为零的顶点栈,;,如果输出顶点个数少于,AOV,网络的顶点个数,则报告网络中存在有向环。,2.6.4,图的应用,void,TopologicalSort,(,AdjGraph,G),Stack S;,StackEmpty(S,);int j;,/,入度为零的顶点栈初始化,for(int i=0;i n;i+),/,入度为零顶点,if(counti=0)Push(S,i);,/,进栈,for(i=0;i n;i+),/,期望输出,n,个顶点,if(,StackEmpty(S,),/,中途栈空,转出,cout,“,网络中有回路！,endl,;,return;,拓扑排序的算法,2.6.4,图的应用,else,/,继续拓扑排序,Pop(S,j);,/,退栈,cout,j,dest,;,/,另一顶点,if(,-,countk=0),/,顶点入度减一,Push(S,k);,/,顶点的入度,减至零,进栈,p=p,-,link;,小结,熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。,熟练掌握图的两种搜索路径的遍历：深度优先搜索和广度优先搜索的算法。,理解求拓扑排序和单源最短路径算法,上机题：实现拓扑排序或单源最短路径算法,