计算机软件技术基础第六章

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,1,第六章 图,数据结构电子教案,郇矢宇,2,图的基本概念,图的存储表示,图的遍历与连通性,拓扑分类,第六章 图,3,图的基本概念,图定义,图是由顶点集合,(vertex),及顶点间的关系集合组成的一种数据结构：,Graph,(,V,E,),其中,V,= ,x,|,x,某个数据对象,是顶点的有穷非空集合；,E,= (,x,y,) |,x,y,V,或,E,= ,|,x,y,V,&,Path,(,x,y,),是顶点之间关系的有穷集合，也叫做边,(edge),集合。,Path,(,x,y,),表示从,x,到,y,的一条单向通路,它是有方向的。,4,有向图与无向图,在有向图中，顶点对,是有序的。在无向图中，顶点对,(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,5,邻接顶点,如果,(,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,6,顶点的度,一个顶点,v,的度是与它相关联的边的条数。记作,TD(,v,),。在有向图中,顶点的度等于该顶点的入度与出度之和。,顶点,v,的入度,是以,v,为终点的有向边的条数,记作,ID(,v,),;,顶点,v,的出度,是以,v,为始点的有向边的条数,记作,OD(,v,),。,路径,在图,G,(,V,E,),中,若从顶点,v,i,出发,沿一些边经过一些顶点,v,p,1,v,p,2, ,v,pm,，到达顶点,v,j,。则称顶点序列,(,v,i,v,p,1,v,p,2,.,v,pm,v,j,),为从顶点,v,i,到顶点,v,j,的路径。它经过的边,(,v,i,v,p,1,),、,(,v,p,1,v,p,2,),、,.,、,(,v,pm,v,j,),应是属于,E,的边。,7,路径长度,非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。,简单路径,若路径上各顶点,v,1,v,2, .,v,m,均不 互相重复,则称这样的路径为简单路径。,回路,若路径上第一个顶点,v,1,与最后一个顶点,v,m,重合,则称这样的路径为回路或环。,0,1,2,3,0,1,2,3,0,1,2,3,8,连通图与连通分量,在无向图中,若从顶点,v,1,到顶点,v,2,有路径,则称顶点,v,1,与,v,2,是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。,强连通图与强连通分量,在有向图中,若对于每一对顶点,v,i,和,v,j,都存在一条从,v,i,到,v,j,和从,v,j,到,v,i,的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。,生成树,一个连通图的生成树是其极小连通子图，在,n,个顶点的情形下，有,n,-,1,条边。,9,图的存储表示,邻接矩阵,(Adjacency Matrix),在图的邻接矩阵表示中，有一个记录各个顶点信息的,顶点表,，还有一个表示各个顶点之间关系的,邻接矩阵,。,设图,A = (V, E),是一个有,n,个顶点的图,图的邻接矩阵是一个二维数组,A,.,edge,n,n,，定义：,10,无向图的邻接矩阵是对称的,;,有向图的邻接矩阵可能是不对称的。,0,1,2,3,0,1,2,11,在有向图中,统计第,i,行,1,的个数可得顶点,i,的,出度,，统计第,j,列,1,的个数可得顶点,j,的,入度,。,在无向图中,统计第,i,行 (列) 1 的个数可得顶点,i,的,度,。,网络的邻接矩阵,12,8,6,3,1,2,9,5,4,2,0,3,1,13,邻接表是邻接矩阵的改进形式。为此需要把邻接矩阵的各行分别组织为一个单链表。,在邻接表中，同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边（边结点），结点中有另一顶点的下标,dest,和指针,link,。对于带权图，边结点中还要保存该边的权值,cost,。,顶点表的第,i,个顶点中保存该顶点的数据，以及它对应边链表的头指针,adj,。,邻接表,(Adjacency List),14,A,B,C,D,data,adj,A,B,C,D,0,1,2,3,dest,link,dest,link,1,3,0,2,1,0,无向图的邻接表,统计某顶点对应边链表中结点个数，可得该顶点的度。,某条边,(v,i,v,j,),在邻接表中有两个边结点，分别在第,i,个顶点和第,j,个顶点对应的边链表中。,15,data,adj,A,B,C,0,1,2,dest,link,dest,link,邻接表,(,出边表,),data,adj,A,B,C,0,1,2,dest,link,逆邻接表,(,入边表,),1,0,2,0,1,1,有向图的邻接表和逆邻接表,A,B,C,16,B,A,C,D,6,9,5,2,8,data,adj,A,B,C,D,0,1,2,3,dest,cost link,1,5,3,6,2,8,3,2,1,9,(,出边表,),(,顶点表,),网络,(,带权图,),的邻接表,统计出边表中结点个数，得到该顶点的出度；,统计入边表中结点个数，得到该顶点的入度。,17,在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。,设图中有,n,个顶点，,e,条边，则用邻接表表示无向图时，需要,n,个顶点结点，,2,e,个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需,n,个顶点结点，,e,个边结点。,当,e,远远小于,n,2,时，可以节省大量的存储空间。此外，把同一个顶点的所有边链接在一个单链表中，也使得图的操作更为便捷。,18,图的遍历与连通性,从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历,(Graph Traversal),。,图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。,为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组,mark ,。,19,辅助数组,mark ,的初始状态为,0,在图的遍历过程中,一旦某一个顶点,i,被访问,就立即让,marki,为,1,防止它被多次访问。,图的遍历的分类,:,深度优先搜索,DFS (Depth First Search),广度优先搜索,BFS (Breadth First Search),20,深度优先搜索,DFS,(Depth First Search),深度优先搜索的示例,A,C,D,E,G,B,F,I,H,A,C,D,E,G,B,F,I,H,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,前进,回退,深度优先搜索过程 深度优先生成树,21,DFS,在访问图中某一,起始顶点,v,后,由,v,出发,访问它的任一,邻接顶点,w,1,;,再从,w,1,出发,访问,与,w,1,邻,接,但还,没有访问过的顶点,w,2,;,然后再从,w,2,出发,进行类似的访问, ,如此进行下去,直至到达所有的邻接顶点都被访问过的顶点,u,为止。,接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。,如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问,;,如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。,22,深度优先遍历的递归算法,设以,i,为初始顶点,深度优先搜索遍历算法,(,省去输入、输出说明,),PROCEDURE DFS2 ( V, LINK, NUM, NEXT, n, i ),PROCESS (,V(i,),MARK(i,) 1,P,LINK(i,) ,取,V,i,的邻接表表头指针,i,WHILE p,0 DO ,依次搜索,V,i,的每个邻接点, j ,NUM(p,) ,取邻接点顶点号,IF,MARK(j,)=0 THEN,DFS2(V,LINK,NUM,NEXT,n,j ) ,从未访问过的,V,j,出发遍历,P,NEXT(p,) ,取,V,i,的下一邻接点,RETURN,23,例如，图：,从顶点,1,出发,(,初始顶点,),，做深度优先遍历的过程为：,访问,v,1,(,结点值,A),，标记,v,1,取,v,2,做深度优先遍历；,访问,v,2,(B),，标记,v,2,取,v,5,做深度优先遍历；,访问,v,5,(E),，标记,v,5,取,v,6,做深度优先遍历；,访问,v,6,(F),，标记,v,6,回退 ,v,5, v,2,；,A,B,C,D,E,F,G,1,2 3 4,5,6 7,24,例如，图：,访问,v,7,(G),，标记,v,7,取,v,3,做深度优先遍历,;,访问,v,3,(C),标记,v,3,回退 ,v,7,取,v,4,做深度优先遍历,;,访问,v,4,(D),，标记,v,4,回退,v,7, v,2,v,1,； 过程结束。,遍历结果：,A,B,E,F,G,C,D,A,B,C,D,E,F,G,1,2 3 4,5,6 7,25,广度优先搜索,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,26,BFS,在访问了起始顶点,v,之后,由,v,出发,依次访问,v,的各个未被访问过的邻接顶点,w,1,w,2, ,w,t,然后,再顺序访问,w,1,w,2, ,w,t,的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，,如此做下去，直到图中所有顶点都被访问到为止。,广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况。因此,广度优先搜索不是一个递归的过程。,27,为了实现逐层访问,算法中使用了一个队列,以记忆正在访问的这一层和上一层的顶点,以便于向下一层访问。,为避免重复访问,需要一个辅助数组,mark ,，给被访问过的顶点加标记。,28,思路：,与树的按层遍历类似,方法：,访问并标记初始顶点,v,i,；,访问并标记,v,i,所有未访问过的邻接点,v,i1,，,v,i2,，,，,v,iS,；,依次访问,并标记,v,i1,，,v,i2,，,，,v,iS,的所有未访问的邻接点；,依次类推，直到所有与,v,i,连通的顶点都被访问。,显然，先被访问的顶点，其邻接点也先被访问。,实现时需要设置一个队列，用于记住访问顶点的次序：,访问初始顶点，并将其顶点号入队；,重复操作：,队头顶点号出队；,依次访问它的每一个未访问的邻接点，并将其顶点号入队；直到队列空，遍历过程结束。,29,例如，图：,从顶点,1,出发,(,初始顶点,),进行广度优先搜索遍历的过程为：,设置一个队列，初始为空；,访问,v,1,(,结点值,A),，标记,v,1,，顶点号入队；,重复操作：,顶点号,1,出队，依次访问其邻接点,2,、,3,、,4,，标记它们，,并依次入队；,顶点,2,出队，依次访问其邻接点,5,、,6,、,7(,顶点,1,已访问,),，,标记它们并依次入队；,A,B,C,D,E,F,G,1,2 3 4,5,6 7,30,例如，图：,顶点,3,出队，其邻接点,1,、,7,都已访问；,顶点,4,出队，其邻接点,1,、,7,都已访问；,依次类推，到顶点,7,出队，队列空，遍历过程结束。,遍历结果为：,A,B,C,D,E,F,G,A,B,C,D,E,F,G,1,2 3 4,5,6 7,31,具体的遍历算法描述与存储方式有关。,如果以邻接矩阵存储图，且：,设：邻接矩阵为,A(1: n, 1: n ),，顶点数组为,V(1: n ),，,标志数组,MARK(1: n ),工作队列,Q(1: n),，队头指针,front,，队尾指针,rear,结点,i,的入队操作为：,ADDQ(Q, i ),，出队操作为：,DELQ(Q, i),初始队列空，,front=rear=0 ,邻接矩阵存储方式下的算法描述：,32,广度优先搜索遍历,PROCESS (,V(i,) ) ;,MARK(i,) 1 ; ADD(Q, i ),WHILE,frontrear,DO, DEL(Q, i ),FOR j=1 TO n DO, IF,A(i, j )=1 AND,MARK(j,)=0 THEN, PROCESS (,V(j,) ) ;,MARK(j,) 1,ADD(Q, j ),RETURN,33,拓扑分类,计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。,例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。,34,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,课程代号,课程名称,先修课程,35,学生课程学习工程图,C,8,C,3,C,5,C,4,C,9,C,6,C,7,C,1,C,2,36,实际工作学习中，为提高效率，必须进行科学管理，合理安排因为：一项工作的各个子项之间，一个工程的各道工序之间，一个学习阶段的各门课程之间都有密切的联系，其中： 有些工作子项的开展，必须以某些子项的完成为前提；有些工序的工作必须在某些工序完成后才能做；有些课程的学习必须在学完某些课的基础上进行。 即：工作子项之间，工程的工序之间，学习课程之间存在“前 提”关系。,拓扑分类的实际意义：,通过一定的方法，找出各工作子项，各道工序、各门课程 学习的顺序，使得一项工作、一个工程和一个阶段的学习能 顺利进行。,找出的序列,拓扑序列。,37,拓扑分类的定义,:,书,P229,若序列,A=(a,1,a,2,a,n,),是集合,M,的元素的一个序列，当,R,时，必有,ij,，则,A,是相对,R,的一个拓扑序列,(Topological Orders),。,得到拓扑序列的过程,拓扑分类,(Topological Sorting),38,7.,实现拓扑分类的步骤：,建立数据结构,定义以下数组：,F(1:n),F(j,),中存放相对于,R,的数,j,的前件个数,初始，,F(j,) = 0 ( j=1, 2, n ),。,G(1:n),G(i,),链接了,R,中数,i,的所有后件,(,存放链表的头指针,),初始,G(i,)=0 ( i=1, 2, , n ) ,空指针。,F(1:n),1,数,1,的前件个数,2,n,数,n,的前件个数,G(1:n),1,2,n,2,的所有后件,39,S(1:n),栈，用于存放算法执行过程中，当前没有前件的数。,为把,R,中的,m,个后件,(R,有,m,个元素,),分别链接到以,G(i,) (i=1,2,n),为头指针的链表中，需要,m,个结点。分别用数组,V(1:m),和,NEXT(1:m),表示,m,个结点的值域与指针域。,依次输入关系,R,中的每一个元素,( i, j ),，同时做以下操作：,每输入一个元素做,F(j)+1,F(j,),；,从数组,V,和,NEXT,中取一个结点，,j,送入,v,中，并把该结点插入到以,G(i,),为头指针的链表中；,输入结束后，将无前件的数送入栈,S,中，即把,F(k,)=0,的,k,送入,S,中。,40,按照上述原则对数组,F,和栈,S,进行连续操作，即可得到一个相 对于,R,的拓扑分类序列：,将栈,S,的栈顶元素输出，并从栈中删除,弹出栈顶元素且输出它 ；,对于,i,的每一个后件,j,做,F(j,) -1,F(j,);,检查数组,F,若有,F(j,)=0,，则将,j,送入栈,S;,重复上述操作，直到栈空，则得到一个拓扑序列。,注意：,要使这个过程正确地终止，必须保证,1,2, ,n,这些元素之间的“前提条件”之间，没有“回圈”存在。,41,算法的,C,语言描述,toposort,( n, r, m ,sq ),int,n, m, r2, sq;,int,top, i, j, k, t, *f, *g, *s;,struct,node /,定义链表结点结构,int,num; /,后件域,int,next; /,指针域,;,struct,node *p;,f=,malloc,(n*,sizeof(int,); /,定义数组,F,g=,malloc,(n*,sizeof(int,); /,定义数组,G,s=,malloc,(n*,sizeof(int,); /,定义栈空间,q=(,struct,nod*),malloc,(m*,sizeof,(,struct,node) /,定义结点空间,42,top=-1; t=0;,for ( k=0; k=n-1; k+ ) /,数组,F,、,G,初始化, f k=0;,gk,=-1; ,for ( k=0; k=m-1; k+ ) /,依次续入,R,中,m,个二元组，,并对,F,、,G,作相应的操作, i=rk0; j=rk1;,fj-1=fj-1+1;,qk.num,=j;,qk.next,=gi-1;,gi-1=k;,for ( k=0; k=n-1; k+ ) /,将没有前件的数入栈,if (f k=0), top=top+1;,stop,=k+1; ,43,while (top!=-1) /,对数组,F,和栈,S,做连续操作, i=,stop,; top=top-1; /,栈顶元素退栈，赋给,i,sqt,=i; t=t+1; /,把数送到拓扑序列中,k=gi-1,while (k!=-1) /,找到,i,的所有后件, j=,qk.num,;,fj-1=fj-1-1; / i,的后件,j,的前件个数减,1,if (fj-1=0) /,新出现的无前件数入栈, top=top+1;,stop,=j; ,k=,qk.next,; /,找到,i,的下一个后件,free(f,);,free(g,);,free(s,);,free(q,);,return;,