数据结构图

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,顶点数,n,与边数关系,:,非连通图,最小连通图,树或表,非连通图,具有回路的图,当达到最大边数时,为完全图,边数,第六章 图,图的基本概念,图的存储结构,图的遍历,生成树和最小生成树,最短路径,拓扑排序,6.1,图的基本概念,图是一种复杂的非线性结构。图中结点之间的关系是,任意,的,即任意两个结点之间都可能有关系（“,多对多,”关系）。,一、图定义,图,G,是由两个集合,V,，,R,组成，记作：,G,(,V,E,),，,其中：,V,= x | x,某个数据对象,，是顶点的非空有限集合；,E,= (x, y) | x, y,V ,，是顶点之间关系的有穷集合，也叫做,边,(,edge),集合。,分为：,有向图与无向图,若图,G,中的每条边都是,有方向,的，则称,G,为有向图。有向边也称为弧，是顶点的有序对，记：, v,wV,表示：,v,w.,称,v,为弧尾或始点，,w,为弧头或终点。,若图,G,中的每条边都是没有方向的，则称,G,为无向图。边是顶点的无序对。记（,v,w,）,v,wV,表示,v,w.,二、术语,邻接顶点,若（,u,v,）是一条无向边，则称顶点,u,和,v,互为邻接点，或称,u,和,v,相邻接。对于有向边,称顶点,u,邻接到顶点,v,，顶点,v,邻接自顶点,u,。,顶点的度,一个顶点,v,的度是与它相关联的边的条数。,对有向图,有出、入度,之分,。,顶点,v,的,入度,是以,v,为终点的有向边的条数,;,顶点,v,的,出度,是以,v,为始点的有向边的条数。顶点,v,的,度,等于其,出、入度之和。,路径,在图,G,（,V,E,） 中,若存在一个顶点序列,v,p,1,v,p,2, ,v,pm,，,使得,(,v,i,v,p,1,),、,(,v,p,1,v,p,2,),、,.,、,(,v,pm,v,j,),均属于,E,，,则称顶点,v,i,到,v,j,存在一 条路径。若一条路径上除了,v,i,和,v,j,可以相同外， 其余顶点均不相同，则称此路径为一条简单路径。起点和终点相同的路径称为简单回路或简单环。,路径长度：路径上边的数目。,子图,设有两个图,G,(,V,E,),和,G,(,V,E,),。若,V,V,且,E,E,则称 图,G,是 图,G,的子图,。,完全图,对有,n,个顶点的图，若为无向图且边数为,n(n-1)/2,，则称其为无向完全图；若为有向图且边数为,n(n-1),，则称其为有向完全图。,图的连通,在无向图,G,中，若两个顶点,v,i,和,v,j,之间有,路径存在，则称,v,i,和,v,j,是连通的。若,G,中,任意,两,个顶点都是连通的，则称,G,为连通图。,无向图中的,极大连通子图,叫做连通分量。,强连通图与强连通分量,在有向图中,若对于每一,对顶点,v,i,和,v,j,都存在一条从,v,i,到,v,j,和从,v,j,到,v,i,的路径,则称此图是强连通图。有向图中的,极大强连通子图,叫做强连通分量。,权,某些图的边具有与它相关的数,称之为权。这种带权图叫做网络,。,1,2,3,5,6,8,7,4,A,B,D,C,E,10,7,9,6,6,7,12,3,15,16,60,30,45,35,80,40,75,三、图的基本操作,建立图；,图的遍历,；插入新顶点；删除图中顶点；查找；等。,权,某些图的边具有与它相关的数,称之为权。这种带权图叫做网络,。,6.2,图的存储结构,用两个数组存储，一个记录各个,顶点信息,的顶点表，还有一个表示各个顶点之间相邻关系的二维数组，称邻接矩阵。,设图,A = (V, E),是一个有,n,个顶点的图，则图的邻接矩阵是一个二维数组,A,.Edgenn,，,定义：,一、邻接矩阵,(Adjacency),无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。,在有向图中,统计第,i,行,1,的个数可得顶点,i,的出度，统计第,j,列,1,的个数可得顶点,j,的入度。,在无向图中,统计第,i,行 (列) 1 的个数可得顶点,i,的度,。,网络的邻接矩阵,邻接矩阵表示法中图的描述,#,define,MaxVexNum,100,/*,图的顶点数*,/,typedef,char,vextype,;,/*,顶点的数据类型*,/,typedef,float,adjtype,;,/*,权值类型*,/,typedef struct,vextype,vexsMaxVexNum;,/*,顶点表*,/,adjtype,arcsMaxVexNumMaxVexNum;,/*,边表*,/,MGraph,;,仅为顶点数据映像而不包含关系映像,2,1,4,3,5,B,A,D,C,E,2,1,5,3,4,6,20,30,50,40,70,80,二、邻接表,(,Adjacency List),类似于树的孩子链表示法。,方法：,把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做边结点，结点中保存有与该边相,关联的另一,顶点的顶点下标,dest,和指向同一链表中下一个边结点的指针,link,。另外，每个链表设一表头结点：存放顶点的值和指向第一个结点的指针。并将所有表头结点存放在数组中。,/*,边表结点定义*,/,typedef struct node, int adjvex;,struct node *next;, edgenode;,/*,顶点表结点*,/,typedef struct, vextype vertex;,edgenode *firstedge;, vexnode;,vexnode gaMaxVexNum;,图的邻接表描述：,1,、无向图的邻接表,分析,求顶点,vi,的度：第,i,个链表中结点个数。,2,、有向图的邻接表和逆邻接表,在有向图的邻接表中，第,i,个边链表链接的边都是,顶点,i,发出的边,。也叫做,出边表,。,在有向图的逆邻接表中，第,i,个边链表链接的边都是,进入顶点,i,的边,。也叫做,入边表,。,在邻接表中求顶点,vi,的出度：第,i,个链表中结点个数；,入度：扫描邻接表，邻接点域值为,i,的结点个数。,带权图的边结点中保存该边上的权值,cost,。,在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。,设图中有,n,个顶点，,e,条边，则,用邻接表表示无向图时,，需要,n,个顶点结点，,2,e,个边结点；用,邻接表表示有向图时,，若不考虑逆邻接表，只需,n,个顶点结点，,e,个边结点。,网络,(,带权图,),的邻接表,6.3,图的遍历,从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历,(,Graph Traversal ),。,图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。,为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组,visited, ,，,它的初始状态为,0,，在图的遍历过程中，一旦某一个顶点,i,被访问，就立即让,visited,i,为,1,，防止它被多次访问。,遍历方法,：深度优先遍历、广度优先遍历,一、深度优先搜索,DFS,( Depth First Search ),深度优先搜索的示例,得到,DFS,序列：,A,，,B,，,E,，,G,，,C,，,F,，,D,，,H,，,I,深度优先搜索过程,深度优先生成树,V,1,V,2,V,3,V,4,V,5,V,6,V,7,V,8,深度优先搜索,(DFS),V,1,V,1,V,2,V,2,V,4,V,4,V,8,V,5,V,8,V,5,V,3,V,3,V,6,V,6,V,7,V,7,DFS,方法：在访问图中某一起始顶点,v,后，由,v,出发，访问它的任一邻接顶点,w1,；,再从,w1,出发，访问与,w1,邻接但还没有访问过的顶点,w2,；,然后再从,w2,出发，进行类似的访问，,如此进行下去，直至到达所有的邻接顶点都被访问过的顶点,u,为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点（设置,访问标志,数组,visiti,）。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问,(,递归过程,),；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。,例子,遍历结果：,A,、,C,、,B,、,D,二、广度优先搜索,BFS,( Breadth First Search,),广度优先搜索的示例,广度优先搜索过程,广度优先生成树,得到的,BFS,序列：,A,，,B,，,C,，,D,，,E,，,F,，,G,，,H,，,I,V,1,V,2,V,3,V,4,V,5,V,6,V,7,V,8,广度优先搜索,(BFS),V,1,V,1,V,2,V,2,V,3,V,3,V,4,V,4,V,5,V,5,V,6,V,6,V,7,V,7,V,8,V,8,使用广度优先搜索在访问了起始顶点,v,之后，由,v,出发，依次访问,v,的各个未曾被访问过的邻接顶点,w1, w2, , wt,，,然后再顺序访问,w1, w2, , wt,的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，,如此做下去，直到图中所有顶点都被访问到为止。,广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。,与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组,visited, ,，,给被访问过的顶点加标记,。,例子,遍历结果：,A,、,C,、,B,、,D,6.4,生成树与最小生成树,一、概念：,1,、连通、连通图：,在无向图,G,中，若从顶点,v,i,到顶点,v,j,有路径，则称,v,i,到,v,j,是连通的若中任意不同的顶点间都连通，则称为连通图,2,、生成树：一个连通图的包含其所有顶点的极小连通子图。,特点：含有图中,所有顶点,，但只有足以构成一棵树的,n-1,条边。即所有顶点连通，但不形成回路。生成树不唯一。,3,、最小生成树：若图有权，则该图的具有权最小的生成树称图的最小生成树。,若从图的某顶点出发，可以系统地访问到图中所有顶点，则遍历时,经过的边,和图的,所有顶点,构成的子图，称为该图的生成树。,用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。如：深度优先生成树与广度优先生成树。,最小生成树应用举例,:n,个城市间架设通讯线路,至少需要,n-1,条线路,.,如何选择,n-1,条线路使得总造价,(,长度,),最小,.,二、求最小生成树：,有两种算法：,Prim,算法和,Kruskal,算法,两种算法都利用了,MST,性质。,最小生成树的重要性质,（,MST,性质）：,最小生成树的重要性质（,MST,性质,）：,设,G,=,（,V,，,E,）,是一个连通网络，,U,是顶点集,V,的,一个非空子集。若,（,u, v,）,是,G,中所有的一个顶点,在,U(u,U),另一个顶点不在,U(v,V-U),的边中，具有最小权值的一条边，则一定存在,G,的一棵最小生成树包括此边,（,u, v,）。,u,v,U,VU,u,v,证明（反证法）：,假设,G,中任何一棵最小生成树中都不包含,(,u,，,v),。设,T,是一棵最小生成树但不包含,(,u,，,v),。,由于,T,是最小生成树，所以,T,是连通的，必存在从,u,到,v,的路径，且该路径上必有一条连接两个顶点集,U,、,V,的边,(u,，,v,),，,其中,u,U,，,v,V-U,。,当把边,(,u,，,v),加入到,T,中后，得到一个含有边,(,u,，,v),的回路。删除边,(u,，,v,),，上述回路即被消除。由此得到另一棵生成树,T,，,T,和,T,的区别仅在于用边,(,u,，,v),代替了,(u,，,v,),。由于,(,u,，,v),的权,= (u,，,v,),的权，,T,的权,=,T,的权，故,T,也是,G,的,MST,，且包含,(u,，,v),，与假设矛盾。,普里姆,(,Prim),算法,普里姆算法的基本思想：,连通网络,N,= ,V,E,，,TE,是,N,上最小生成树中边的集合。算法从,U=u0,(u0V),TE= ,开始。重复执行下述操作：在所有,uU,vV-U,的边（,u,v) E,中找一条,权值最小的边,(u0, v0),并入到集合,TE,中,同时把,v0,并入到,U,中，如此直到,U=V,为止。此时,TE,中必有,n-1,条边，则,T=,（,V,，,TE,）为,N,的最小生成树。,用普里姆算法构造最小生成树的过程,1,2,3,4,6,5,5,6,5,1,7,3,2,5,4,6,1,2,3,4,6,5,5,1,3,2,4,U=1,TE= ,U=1,3,TE=(1,3) ,U=1,3,6,TE=(1,3),(3,6) ,U=1,3,6,4,TE=(1,3),(3,6) ,(6,4),U=1,3,6,4,2,5,TE=(1,3),(3,6) ,(6,4),(3,2),(2,5 ),克鲁斯卡尔,(,Kruskal,),算法,克鲁斯卡尔算法的基本思想：,设有一个有,n,个顶点的连通网络,N,= ,V,E,最初先构造一个只有,n,个顶点，没有边的非连通,图,T,= ,V,图中每个顶点自成一个连通分量。,当在,E,中选到一条具有最小权值的边时,若该边的,两个顶点落在不同的连通分量,(,不同的树,),上，则将此边加入到,T,中；否则将此边舍去,(,因为形成了回路,),，重新选择一条权值最小的边。,如此重复下去，直到所有顶点在同一个连通分量上,(,同一棵树,),为止。,用克鲁斯卡尔算法构造最小生成树的过程,1,2,3,4,6,5,5,6,5,1,7,3,2,5,4,6,1,2,3,4,6,5,5,1,3,2,4,6.5,最短路径,(,Shortest Path),最短路径问题：如果从图中某一顶点,(,称为,源点,),到达另一顶点,(,称为,终点,),的路径可能不止一条，如何找到一条路径，使得沿此路径各边上的权值总和达到最小。,单源最短路径问题 ：从有向图的的源点到其余各终点有否路径？其最短路径及其长度是多少？,解法：,Dijkstra,算法,单源最短路径问题,问题的提出：,给定一个,带权有向图,G,与,源点,v,，,求从,v,到,G,中其它顶点的最短路径。限定各边上的权值大于或等于,0,。,为求得这些最短路径，,Dijkstra,提出按,路径长度的递增,次序，逐步产生最短路径的算法,.,则当前正在产生的最短路径上,除终点外,其余顶点的最段路径均已生成,.,思路,:,设置并逐步扩充集合,S,存放已求出最短路径的顶点,则尚未确定最短路径的顶点集合为,:V-S.,步骤,:,首先求出,长度最短,的一条最短路径；并将其终点并入集合,S;,再求出长度次短的一条最短路径：它或者是,两顶点的弧,，或者是,经过已找到的一条最短路径，,再到达目标顶点的路径,(,修改原值,),；,每求出一个顶点,使之并入集合,S,并修改到其他顶点的最短路径,(,经过当前已求出最短路径的顶点,未必真正最短,),再从中选出路径长度最短的顶点,;,依次类推，直到从顶点,v,到其它各顶点的最短路径全部求出为止。,Dijkstra,逐步求解的过程,循环,集合,S,k+1,D0D4,PP4,初始化,0,0,1,0,1,3,0,1,3,2,0,1,3,2,4,-,1,3,2,4,0,10,max 30,100,0,10,60,30,100,0,10,50,30,90,0,10,50,30,60,0,10,50,30 60,0 0 0 0 0,0 1 3 3 3,0 1 3 3 3,0 1 2 3 2,0 1 2 3 4,0,1,4,2,3,50,10,30,10,20,60,100,Dj,表示当前所找到的从始点到各终点的最短路径长度,;,