数据结构6图.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第6章 图,*,第6章 图,图的基本概念及基本术语,图的存储结构,图的遍历,图的应用,图属于非线性数据结构的一种。,树结构中数据元素之间的关系：,一对多,的关系。,图结构中数据元素之间的关系：,多对多,的关系。,1/12/2026,1,第6章 图,6.1,、图的基本概念,图是由结点集合,(vertex),及结点间的关系,集合组成的一种数据结构,：,Graph,(,V,E,),其中,V,=,x,|,x,某个数据对象,是结点的有穷非空集合；,E,=(,x,y,)|,x,y,V,是结点之间关系的有穷集合，也叫做边,(edge),集合。,1.,图：,1/12/2026,2,第6章 图,有向图,Graph,(,V,E,),V,:,是结点的有穷非空集合；,E,:,有向,边,(,弧,),集合。,弧是结点的有序对,.,例,:,表示,Vi,Vj,无向图,Graph,(,V,E,),V,:,是结点的有穷非空集合；,E,:,是结点的,无向,边,(,无序对,),的集合,例,:,(,Vi,Vj,),Vi,与,Vj,相邻,;,(,Vi,Vj,)=(,Vj,Vi,),Vj,:,弧头,Vi:,弧尾,Vi,Vj,1/12/2026,3,第6章 图,ADT Graph,数据对象,V:,一个集合，集合中所有元素具有相同的特性。,数据关系,R,：,R=VR,VR=|P,（,x,，,y,）（,x,，,yV,）,基本操作：,（,1,）,CreateGraph,（,G,）：,创建图,G,。,（,2,）,DestoryGraph,（,G,）：,销毁图,G,。,（,3,）,LocateVertex,（,G,，,v,）：,确定顶点,v,在图,G,中的位置。若图,G,中没有顶点,v,，,则函数,值为“空”。,（,4,）,GetVertex,（,G,，,i,）：取出图,G,中的第,i,个顶点的值。若,i,大于图,G,中顶点数，则函数值为,“,空,”,。,1/12/2026,4,第6章 图,（,5,）,FirstAdjVertex,（,G,，,v,）：,求图,G,中顶点,v,的第一个邻接点。若,v,无邻接点或图,G,中无顶点,v,，,则函数值为,“,空,”,。（,6,）,NextAdjVertex,（,G,，,v,，,w,）：,已知,w,是图,G,中顶点,v,的某个邻接点，求顶点,v,的下一个邻接点（紧跟在,w,后面）。若,w,是,v,的最后一个邻接点，则函数值为,“,空,”,。,（,7,）,InsertVertex,（,G,，,u,）：,在图,G,中增加一个顶点,u,。,（,8,）,DeleteVertex,（,G,，,v,）：删除图,G,的顶点,v,及与顶点,v,相关联的弧。,（,9,）,InsertArc,（,G,，,v,，,w,）：在图,G,中增加一条从顶点,v,到顶点,w,的弧。,（,10,）,DeleteArc,（,G,，,v,，,w,）：删除图,G,中从顶点,v,到顶点,w,的弧。,（,11,）,TraverseGraph,（,G,）：按照某种次序，对图,G,的每个结点访问一次且仅访问一次。,1/12/2026,5,第6章 图,完全图,:,对有,n,个结点的图，,无向图,:,任意两结点都有一条边，即边数为,:,n(n-1)/2,，,则称其为无向完全图；,邻接结点,:,无向图,:,若（,v,i,v,j,）,E,，,则称结点,v,i,和,v,j,互为邻接点；或称,v,i,和,v,j,相邻接；或称边（,v,i,v,j,）,关联于结点,v,i,和,v,j,；或,称边（,v,i,v,j,）,与结点,v,i,和,v,j,相关联。,有向图：,若,E,则称结点,v,j,是,v,i,的,邻接点。,2.,基本概念,1/12/2026,6,第6章 图,结点的度：,一个结点,v,的度是与它相关联的边的条数 记作,TD(,v,),。,无向图：,即为该结点相连的边的个数。,有向图：,依附在某结点的弧的数目。,结点的入度,：,以该结点为弧头的弧的数目。,是以,v,为终点的有向边的条数,记作,ID(,v,),;,结点的出度：,以该结点为弧尾的弧的数目。,是以,v,为始点的有向边的条数,记作,OD(,v,),。,有向图：,任意两结点都有两条方向相反的弧，,即弧数为,n(n-1),，,则称其为有向完全图。,1/12/2026,7,第6章 图,TD(,v,)=ID(v)+OD(v),1,6,2,5,4,3,a,b,c,d,e,f,TD(1)=3 TD(2)=3,TD(3)=3 TD(4)=2,TD(5)=2 TD(6)=1,ID(a)=1 OD(a)=2 TD(a)=3 ID(b)=1 OD(b)=2 TD(b)=3,ID(c)=2 OD(c)=0 TD(c)=2 ID(d)=1 OD(d)=1 TD(d)=2,ID(e)=0 OD(e)=1 TD(e)=1 ID(f)=1 OD(f)=0 TD(f)=1,1/12/2026,8,第6章 图,子图：,设有两个图,G,(,V,E,),和,G,(,V,E,),。,若,V,V,且,E,E,则称 图,G,是 图,G,的子图。,0,1,2,3,(a)G1,0,1,2,3,G1,的子图,0,1,2,G1,的子图,0,1,2,3,G1,的子图,0,1,2,0,1,2,0,1,2,1,2,(b)G2,G2,的子图,G2,的子图,G2,的子图,1/12/2026,9,第6章 图,路径,:,在图,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,可以相同外，其余结点均不相同，则称此路径为一条,简单路径,。起点和终点相同的路径称为,简单回路,或简单环。,1/12/2026,10,第6章 图,图的连通,在,无向图,G,中，若两个结点,v,i,和,v,j,之间有路径存在，则称,v,i,和,v,j,是连通的。若,G,中任意两个结点都是连通的，则称,G,为,连通图,。,非连通图的极大连通子图叫做,连通分量,。,强连通图与强连通分量,在,有向图,中,若对于每一 对结点,v,i,和,v,j,都存在一条从,v,i,到,v,j,和从,v,j,到,v,i,的路径,则称此图是强连通图。非强连通图的极大强连通 子图叫做,强连通分量。,权,某些图的边具有与它相关的数,称之为权。,网络,这种带权图叫做。,1/12/2026,11,第6章 图,1,3,4,5,2,1,3,4,5,2,V=1,2,3,4,5,E=(1,2),(1,3),(1,4),(2,4),(4,5),V=1,2,3,4,5,E=,无向图,有向图,连通图,非连通图,1,3,4,5,2,6,7,H1,连通分量,H2,连通分量,1/12/2026,12,第6章 图,1,3,2,强连通图,非强连通图,5,1,3,4,2,1,3,4,2,5,强连通分量,H1,强连通分量,H2,1/12/2026,13,第6章 图,1,2,3,5,6,8,7,4,10,7,9,6,6,7,12,3,15,16,30,45,A,B,D,C,E,60,35,80,40,75,网络,1/12/2026,14,第6章 图,生成树,一个连通图的生成树是它的极小连通子图，在,n,个结点的情形下，有,n,-1,条边。,不予讨论的图,包含结点到其自身的边；一条边在图中重复出现,1/12/2026,15,第6章 图,6.2,、图的存储结构,在图的邻接矩阵表示中，有一个,记录各个结点信息,的,结点表；,还有一个,表示各个结点之间关系,的,邻接矩阵,。,设图,A=(,V,E,),是一个有,n,个结点的图，则图的邻接矩阵是一个二维数组,A,.Edge,n,n,，,定义：,邻接矩阵,(Adjacency Matrix),1.,顺序存储,1/12/2026,16,第6章 图,0,1,2,3,A.Edge=,0,1,3,2,4,5,6,7,A.Edge=,V=0,1,2,3,V=0,1,2,3,4,5,6,7,1/12/2026,17,第6章 图,网络的邻接矩阵,1/12/2026,18,第6章 图,无向图的邻接矩阵是对称的，,有向图的邻接矩阵可能是不对称的。,在无向图中,统计第,i,行(列)1的个数可得结点,i,的度。,在有向图中,统计第,i,行,1,的个数可得结点,i,的出度，统计第,j,列,1,的个数可得结点,j,的入度。,属于静态存储方法。不易扩充。,与结点个数有关，与边（弧）无关。会出现稀疏矩阵。,邻接矩阵的特点：,1/12/2026,19,第6章 图,2.,链接存储,邻接表,(Adjacency List):,顺序存储结构和链接存储结构结合,顺序存储每个结点。,把与某个结点邻接的所有结点都链接在一个单链表上。,结点数据,指针,结点号,指针,1/12/2026,20,第6章 图,无向图的邻接表,A,B,C,D,1/12/2026,21,第6章 图,把同一个结点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做,边结点,，结点中保存有与该边相关联的另一结点的结点下标,dest,和指向同一链表中下一个边结点的指针,link,。,有向图的邻接表,A,B,C,D,E,1/12/2026,22,第6章 图,带权图的边结点中保存该边上的权值,cost,。,结点,i,的边链表的表头指针,adj,在结点表的下标为,i,的结点记录中，该记录还可保存该结点的其它信息。,在邻接表的边链表中，,各个边结点的链入顺序任意，视边结点输入次序而定。,设图中有,n,个结点，,e,条边，则,用邻接表表示无向图时,，需要,n,个结点，,2,e,个边结点；用,邻接表表示有向图时,，若不考虑逆邻接表，只需,n,个结点，,e,个边结点。,1/12/2026,23,第6章 图,邻接表,特点：,仍为结点之间邻接关系,节省空间,结点的度：,无向图：,为该结点的单链表中结点数目。,有向图：,出度：,为该结点的单链表中结点数目。,入度：,扫描整个邻接表的单链表，为该结点出现的次数。,1/12/2026,24,第6章 图,网络,(,带权图,),的邻接表,此外,十字链表和邻接多重表存储法,.(,自学,),1/12/2026,25,第6章 图,6.3,、图的遍历,从已给的,连通图,中某一结点出发，沿着一些边访遍图中所有的结点，且使每个结点仅被访问一次，就叫做图的,遍历,(Graph Traversal,),。,图中可能存在,回路,，且图的任一结点都可能与其它结点相通，在访问完某个结点之后可能会沿着某些边又回到了曾经访问过的结点。,为了避免重复访问，可设置一个标志结点是否被访问过的辅助数组,visited,，,它的初始状态为,0,，在图的遍历过程中，一旦某一个结点,i,被访问，就立即让,visited,i,为,1,，防止它被多次访问。,1/12/2026,26,第6章 图,1.,深度优先搜索,DFS,(Depth First Search),DFS,在访问图中某一起始顶点,v,后，由,v,出发，访问它的任一邻接顶点,w,1,；再从,w,1,出发，访问与,w,1,邻接的还没有访问过的顶点,w,2,；然后再从,w,2,出发，进行类似的访问，,如此进行下去，直至到达结点,u,的所有邻接结点都被访问过为止。接着，退回一步，退到前一次刚访问过的结点，看是否还有其它没有被访问的邻接结点。如果有，则访问此结点，之后再从此结点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有结点都被访问过为止。,1/12/2026,27,第6章 图,深度优先搜索的示例,A,B,C,D,F,E,G,H,I,1,2,3,4,5,6,7,8,9,搜索,回退,A,B,C,D,F,E,G,H,I,1,2,3,4,5,6,7,8,9,连通图的深度优先搜索递归算法,:,(1),访问结点,v,，做标记,;,(2),查找结点,v,的任一邻接结点,w,；,(3),若结点,v,邻接结点,w,存在,则继续执行,否则结束,;,(4),若结点,w,尚未被访问,则递归访问结点,w.,(5),查找结点,w,的下一邻接结点；转到,(3),1/12/2026,28,第6章 图,例子,遍历结果：,A,、,C,、,B,、,D,遍历过程有回退操作，用栈或递归实现,1/12/2026,29,第6章 图,2.,广度优先搜索,BFS,(Breadth First Search,),使用广度优先搜索在访问了起始结点,v,之后，由,v,出发，依次访问,v,的各个未曾被访问过的邻接结点,w,1,w,2,w,t,，,然后再顺序访问,w,1,w,2,w,t,的所有还未被访问过的邻接结点。再从这些访问过的结点出发，再访问它们的所有还未被访问过的邻接结点，,如此做下去，,直到图中所有结点都被访问到为止。,1/12/2026,30,第6章 图,广度优先搜索的示例,广度优先搜索过程,A,B,C,D,F,E,G,H,I,3,1,2,5,4,6,8,9,7,广度优先生成树,A,B,C,D,F,E,G,H,I,1,2,4,3,5,7,6,8,9,1/12/2026,31,第6章 图,广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批结点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的结点，以便于向下一层访问。,与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组,visited,，,给被访问过的结点加标记。,1/12/2026,32,第6章 图,最小生成树,在一个连通网的所有生成树中，各边的代价之和最小的那棵生成树称为该连通网的,最小代价生成树,（,Minimum Cost Spanning Tree,），,简称为,最小生成树,(MST),。,最小生成树有如下重要性质：,设,N=(V,E),是一连通网，,U,是顶点集,V,的一个非空子集。若（,u,v,）,是一条具有最,小权值的边，其中,uU,，,vV-U,，,则存在一棵包含边（,u,v,）,的最小生成树。,6.4,、图的应用,1/12/2026,33,第6章 图,反证法证明：,假设不存在这样一棵包含边（,u,v,）,的最小生成树。任取一棵最小生成树,T,，,将（,u,v,）,加入,T,中。根据树的性质，此时,T,中必形成一个包含（,u,v,）,的回路，且回路中必有一条边（,u,v,）,的权值大于或等于（,u,v,）,的权值。删除（,u,v,），,则得到一棵代价小于等于,T,的生成树,T,，且,T,为一棵包含边（,u,v,）,的最小生成树。这与假设矛盾，故该性质得证。,利用,MST,性质来生成一个连通网的最小生成树。,普里姆,（,Prim,）,算法,和,克鲁斯卡尔（,Kruskal,）,算法,便是利用了这个性质。,1/12/2026,34,第6章 图,1.,普里姆算法,假设,N=(V,E),是连通网，,TE,为最小生成树中边的集合。,（,1,）初始,U=u,0,(u,0,V),TE=,；,（,2,）,在所有,uU,vV-U,的边中选一条代价最小的边（,u,0,，,v,0,）,并入集合,TE,，,同时将,v,0,并入,U,；,（,3,）,重复（,2,），直到,U=V,为止。,此时，,TE,中必含有,n-1,条边，则,T=,（,V,，,TE,）为,N,的最小生成树。,可以看出，普利姆算法逐步增加,U,中的顶点，可称为“加点法”。,1/12/2026,35,第6章 图,【,普里姆算法,构造最小生成树的过程,】,(a),连通网,V1,V2,V4,V6,V5,V3,1,V1,V2,V4,V6,V5,V3,1,4,V1,V2,V4,V6,V5,V3,1,4,2,V1,V2,V4,V6,V5,V3,1,4,2,5,3,V1,V2,V4,V6,V5,V3,1,4,2,5,V1,V2,V4,V6,V5,V3,5,6,1,5,5,6,6,2,4,3,(b)V3,入网,(c)V6,入网,(d),V4,入,网,(e),V2,入,网,(f),V5,入,网,1/12/2026,36,第6章 图,2.,克鲁斯卡尔算法,假设,N=(V,E),是连通网，将,N,中的边按权值从小到大的顺序排列,:,(1),将,n,个顶点看成,n,个集合；,(2),按权值由小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中。同时将该边的两个顶点所在的顶点集合合并；,(3),重复,(2),直到所有的顶点都在同一个顶点集合内。,可以看出，克鲁斯卡尔算法逐步增加生成树的边，与普里姆算法相比，可称为,”,加边,法”。,1/12/2026,37,第6章 图,例如，对于上例图所示的连通网，将所有的边按权值从小到大的顺序排列为：,权值,1 2 3 4 5,边,(v,1,v,3,)(v,4,v,6,)(v,2,v,5,)(v,3,v,6,)(v,1,v,4,),5 5 6 6 6,(v,2,v,3,)(v,3,v,4,)(v,1,v,2,)(v,3,v,5,),(v,5,v,6,),V1,V2,V4,V6,V5,V3,5,6,1,5,5,6,6,2,4,3,V1,V2,V4,V6,V5,V3,1,(a)(v1,v3),V1,V2,V4,V6,V5,V3,1,2,3,V1,V2,V4,V6,V5,V3,1,2,(b)(v1,v3)(v4,v6),(c)(v1,v3)(v4,v6)(v2,v5),1/12/2026,38,第6章 图,3,V1,V2,V4,V6,V5,V3,1,4,2,(d)(v1,v3)(v4,v6)(v2,v5)(v3,v6),(e)(v1,v3)(v4,v6)(v2,v5)(v3,v6)(v2,v3),3,V1,V2,V4,V6,V5,V3,1,4,2,5,(v,1,v,3,)(v,4,v,6,)(v,2,v,5,)(v,3,v,6,)(v,2,v,3,),经过筛选所得到边的顺序为：,在选择第五条边时，因为,v,1,、,v,4,已经在同一集合内，如果选（,v,1,，,v,4,），,则会形成回路，所以选（,v2,，,v3,）。,1/12/2026,39,第6章 图,设,N=(V,E),最小生成树的初态为,T=,（,V,）。,（,1,）,待选的边：,(2,3)-5,(2,4)-6,(3,4)-6,(2,6)-11,(4,6)-14,(1,2)-16,(4,5)-18,(1,5)-19,(1,6)-21,(5,6)-33,。,顶点集合状态：,1,，,2,，,3,，,4,，,5,，,6,。,最小生成树的边的集合：,。,3,1,2,4,5,6,5,6,16,21,11,18,33,6,14,19,3,1,2,4,5,6,1/12/2026,40,第6章 图,（,2),从待选边中选一条权值最小的边为,:(2,3)-5,。,待选的边变为：,(2,4)-6,(3,4)-6,(2,6)-11,(4,6)-14,(1,2)-16,(4,5)-18,(1,5)-19,(1,6)-21,(5,6)-33,。,顶点集合状态变为：,1,，,2,，,3,，,4,，,5,，,6,。,最小生成树的边的集合：,(2,3),。,3,1,2,4,5,6,5,1/12/2026,41,第6章 图,（,3,）从待选边中选一条权值最小的边为,:(2,4)-6,。,待选的边变为：,(3,4)-6,(2,6)-11,(4,6)-14,(1,2)-16,(4,5)-18,(1,5)-19,(1,6)-21,(5,6)-33,。,顶点集合状态变为：,1,，,2,，,3,，,4,，,5,，,6,。,最小生成树的边的集合：,(2,3),(2,4),。,3,1,2,4,5,6,5,6,1/12/2026,42,第6章 图,（,4,）从待选边中选一条权值最小的边为,:(3,4)-6,，由于,3,、,4,在同一个顶点集合,2,，,3,，,4,内，故放弃。重新从待选边中选一条权值最小的边为,:(2,6)-11,。,待选的边变为：,(4,6)-14,(1,2)-16,(4,5)-18,(1,5)-19,(1,6)-21,(5,6)-33,。,顶点集合状态变为：,1,，,2,，,3,，,4,，,6,，,5,。,最小生成树的边的集合：,(2,3),，,(2,4),(2,6),。,3,1,2,4,5,6,5,6,11,1/12/2026,43,第6章 图,（,5,）从待选边中选一条权值最小的边为,:(4,6)-14,，由于,4,、,6,在同一个顶点集合,2,，,3,，,4,，,6,内，故放弃。重新从待选边中选一条权值最小的边为,:(1,2)-16,。,待选的边变为：,(4,5)-18,(1,5)-19,(1,6)-21,(5,6)-33,。,顶点集合状态变为：,1,，,2,，,3,，,4,，,6,，,5,。,最小生成树的边的集合：,(2,3),，,(2,4),(2,6),，,(1,2),。,3,1,4,5,6,5,6,11,16,2,1/12/2026,44,第6章 图,（,6,）从待选边中选一条权值最小的边为,:(4,5)-18,。,待选的边变为：,(1,5)-19,(1,6)-21,(5,6)-33,。,顶点集合状态变为：,1,，,2,，,3,，,4,，,6,，,5,。,最小生成树的边的集合：,(2,3),，,(2,4),(2,6),，,(1,2),(4,，,5),。,3,1,2,4,5,6,5,6,11,16,18,至此，所有的顶点都在同一个顶点集合,1,，,2,，,3,，,4,，,6,，,5,里，算法结束。所得最小生成树如图所示，其代价为：,5+6+11+16+18=56,。,1/12/2026,45,第6章 图,总结：,1,。,基本概念,：图，无向图，有向图，邻接点，完全图，结点的度，路径，回路，连通图，强连通图，权，网络，生成树,2,。,存储结构,：邻接矩阵，邻接表,3,。,遍历,：深度优先搜索，广度优先搜索,4.,应用：,最小生成树,作业：,P244,1(1,2,3,4,6),2,13,（,A,B,C,）,14,1/12/2026,46,第6章 图,