数据结构_图论部分.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Page,*,Data Structure,*,Data Structure,第七章 图,100,865,10,5/25/2026,1,学习目标,领会,图的类型定义,。,熟悉,图的各种存储结构,及其构造算法，了解各种存储结构的特点及其,选用原则,。,熟练掌握图的两种,遍历,算法。,理解各种图的,应用问题的算法,。,重点和难点,重点：图的各种应用问题的算法都比较经典，注意,理解各种图的算法及其应用场合,。,5/25/2026,2,知识点,图的类型定义,图的存储表示,图的深度优先搜索遍历和广度优先搜索遍历,无向网的最小生成树,拓扑排序,关键路径,最短路径,5/25/2026,3,欧拉,1707,年出生在瑞士的巴塞尔城，,19,岁开始发表论文，直到,76,岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他那不倦的一生，共写下了,886,本书籍和论文，其中分析、代数、数论占,40%,，几何占,18%,，物理和力学占,28%,，天文学占,11%,，弹道学、航海学、建筑学等占,3%,。,1733,年，年仅,26,岁的欧拉担任了彼得堡科学院数学教授。,1741,年到柏林担任科学院物理数学所所长，直到,1766,年，重回彼得堡，没有多久，完全失明。欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。,图论,欧拉,5/25/2026,4,能否从某个地方出发，穿过所有的桥仅一次后再回到出发点？,哥尼斯堡七桥问题,5/25/2026,5,C,A,D,B,七桥问题的图模型,欧拉回路的判定规则：,1.,如果通奇数桥的地方多于两个，则不存在欧拉回路；,2.,如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；,3.,如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。,5/25/2026,6,图的定义,图是由,顶点,的,有穷非空,集合和顶点之间,边,的集合组成，通常表示为：,G,=(,V,，,E,),其中：,G,表示一个图，,V,是图,G,中顶点的集合，,E,是图,G,中顶点之间边的集合。,在线性表中，元素个数可以为零，称为空表；,在树中，结点个数可以为零，称为空树；,在图中，顶点个数不能为零，但可以没有边。,7.1,图的定义和术语,5/25/2026,7,线性表,每个数据元素只有一个直接前驱和一个直接后继。,树形结构,每个数据元素只有一个直接前驱，但可能有多个直接后继。,图形结构,每个数据元素可能有多个直接前驱和多个直接后继。,图是比线性表和树复杂的数据结构，广泛应用于语言学、逻辑学、物理、化学等领域。,5/25/2026,8,如果图的任意两个顶点之间的边都是,无向边，则称该图为,无向图,。,若顶点,v,i,和,v,j,之间的边没有方向，则称这条边为,无向边,，表示为,(,v,i,v,j,),。,若从顶点,v,i,到,v,j,的边有方向，则称这条边为,有向边,，表示为,。,如果图的任意两个顶点之间的边都是,有向边，则称该图为,有向图,。,V,1,V,2,V,3,V,4,V,5,V,1,V,2,V,3,V,4,图的基本术语,5/25/2026,9,简单图：,在图中，若不存在顶点到其自身的边，且同一条边不重复出现,。,V,3,V,4,V,5,V,1,V,2,V,3,V,4,V,5,V,1,V,2,非简单图 非简单图 简单图,V,1,V,2,V,3,V,4,V,5,数据结构中讨论的都是简单图。,5/25/2026,10,图的基本术语,邻接、依附,无向图,中，对于任意两个顶点,v,i,和顶点,v,j,，,若存在边,(,v,i,，,v,j,),，则称顶点,v,i,和顶点,v,j,互为邻接点，同时称边,(,v,i,，,v,j,),依附于顶点,v,i,和顶点,v,j,。,V,1,V,2,V,3,V,4,V,5,V,1,的邻接点：,V,2,、,V,4,V,2,的邻接点：,V,1,、,V,3,、,V,5,5/25/2026,11,图的基本术语,邻接、依附,有向图,中，对于任意两个顶点,v,i,和顶点,v,j,，,若存在弧,，,则称顶点,v,i,邻接到顶点,v,j,，,顶点,v,j,邻接自顶点,v,i,，,同时称弧,依附于顶点,v,i,和顶点,v,j,。,V,1,V,2,V,3,V,4,V,1,的邻接点：,V,2,、,V,3,V,3,的邻接点：,V,4,5/25/2026,12,无向完全图,：在无向图中，如果任意两个顶点之间都存在边，,则称该图为无向完全图。,有向完全图,：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，,则称该图为有向完全图。,图的基本术语,V,1,V,2,V,3,V,1,V,2,V,3,V,4,5/25/2026,13,含有,n,个顶点的无向完全图有,多少,条边？,含有,n,个顶点的有向完全图有,多少,条弧？,含有,n,个顶点的无向完全图有,n,(,n,-1)/2,条边。,含有,n,个顶点的有向完全图有,n,(,n,-1),条边。,V,1,V,2,V,3,V,1,V,2,V,3,V,4,5/25/2026,14,稀疏图：,称边数很少的图为稀疏图；,稠密图：,称边数很多的图为稠密图。,顶点的度：,在无向图中，顶点,v,的,度,是指依附于该顶点的边数，通常记为,TD(v),。,图的基本术语,顶点的入度：,在有向图中，顶点,v,的,入度,是指以该顶点为弧头的弧的数目，,记为,ID(v),；,顶点,的,出度：,在有向图中，顶点,v,的,出度,是指以该顶点为弧尾的弧的数目，记为,OD(v),。,5/25/2026,15,V,1,V,2,V,3,V,4,V,5,图的基本术语,在具有,n,个顶点、,e,条边的无向图,G,中，各顶点的度之和与边数之和的关系？,=,=,n,i,i,e,v,TD,1,2,),(,5/25/2026,16,V,1,V,2,V,3,V,4,图的基本术语,在具有,n,个顶点、,e,条边的有向图,G,中，各顶点的入度之和与各顶点的出度之和的关系？与边数之和的关系？,e,v,OD,v,ID,i,i,i,i,=,=,=,=,1,1,),(,),(,n,n,5/25/2026,17,权：,是指对边赋予的有意义的数值量。,网：,边上带权的图，也称网图。,图的基本术语,V,1,V,2,V,3,V,4,2,7,8,5,5/25/2026,18,路径：,在无向图,G,=(,V,E,),中，从顶点,v,p,到顶点,v,q,之间的,路径,是一个顶点序列,(,v,p,=,v,i,0,v,i,1,v,i,2,v,im,=,v,q,),，,其中，,(,v,ij,-1,v,ij,),E,（,1,j,m,）。若,G,是有向图，则路径也是有方向的，顶点序列满足,E,。,图的基本术语,V,1,V,2,V,3,V,4,V,5,一般情况下，图中的路径不惟一。,V,1,到,V,4,的路径：,V,1,V,4,V,1,V,2,V,3,V,4,V,1,V,2,V,5,V,3,V,4,5/25/2026,19,路径长度：,图的基本术语,非带权图,路径,上边的,个数,带权图,路径上,各边的,权之和,V,1,V,2,V,3,V,4,V,5,V,1,V,4,：长度为,1,V,1,V,2,V,3,V,4,：长度为,3,V,1,V,2,V,5,V,3,V,4,：长度为,4,5/25/2026,20,路径长度：,图的基本术语,非带权图,路径,上边的,个数,带权图,路径上,各边的,权之和,V,1,V,4,：长度为,8,V,1,V,2,V,3,V,4,：长度为,7,V,1,V,2,V,5,V,3,V,4,：长度为,15,V,1,V,2,V,3,V,4,V,5,2,5,6,3,2,8,5/25/2026,21,回路（环）,：第一个顶点和最后一个顶点相同的路径。,简单路径：,序列中顶点不重复出现的路径。,简单回路（简单环）：,除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。,图的基本术语,V,1,V,2,V,3,V,4,V,5,V,1,V,2,V,3,V,4,5/25/2026,22,子图：,若图,G,=,（,V,，,E,），,G,=,（,V,，,E,），,如果,V,V,且,E,E,，,则称图,G,是,G,的子图。,图的基本术语,V,1,V,2,V,3,V,4,V,5,V,1,V,2,V,3,V,4,V,5,V,1,V,3,V,4,5/25/2026,23,连通图：,在无向图中，如果从一个顶点,v,i,到另一个顶点,v,j,(,i,j,),有路径，则称顶点,v,i,和,v,j,是连通的。如果图中任意两个顶点都是连通的，则称该图是连通,图。,连通分量：,非连通图的极大连通子图称为连通分量。,图的基本术语,如何求得一个非连通图的连通分量,?,1.,含有极大,顶点,数；,2.,依附于这些顶点的所有,边,。,5/25/2026,24,连通分量,1,V,1,V,2,V,3,V,4,V,5,V,6,V,7,V,1,V,2,V,4,V,5,V,3,V,6,V,7,连通分量,2,图的基本术语,连通分量是对无向图的一种划分。,5/25/2026,25,强连通图：,在有向图中，对图中任意一对顶点,v,i,和,v,j,(,i,j,),，,若从顶点,v,i,到顶点,v,j,和从顶点,v,j,到顶点,v,i,均有路径，则称该有向图是强连通图。,强连通分量：,非强连通图,的极大强连通子图。,图的基本术语,如何求得一个非连通图的连通分量,?,5/25/2026,26,图的基本术语,V,1,V,2,V,3,V,4,强连通分量,1,强连通分量,2,V,1,V,3,V,4,V,2,5/25/2026,27,生成树：,n,个顶点的连通图,G,的生成树是包含,G,中,全部顶点,的一个极小连通,子图。,生成森林：,在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分,量的生成树就组成了一个非连通图的,生成森林,。,如何理解极小连通子图,?,图的基本术语,多,构成回路,少,不连通,含有,n,-1,条边,5/25/2026,28,V,1,V,2,V,3,V,4,V,5,V,6,V,7,V,1,V,2,V,3,V,4,V,5,V,6,V,7,V,1,V,2,V,3,V,4,V,5,V,1,V,2,V,3,V,4,V,5,生成树,生成森林,5/25/2026,29,图的抽象数据类型定义如下：,ADT,Graph,数据对象,V,：,V,是具有相同特性的数据元素的集合，称为顶 点集。,数据关系,R,：,R=VRVR,|v,wV,且,P(v,w),，,表示从,v,到,w,的 弧，谓词,P(v,w),定义了弧,的意义 或信息,5/25/2026,30,G1=(,V1,VR1,),V1=A,B,C,D,E,VR1=,G2=(,V2,VR2,),V2=A,B,C,D,E,F,VR2=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F),5/25/2026,31,CreateGraph(&G,V,VR);,初始条件：,V,是图的顶点集，,VR,是图中弧的集合。操作结果：按,V,和,VR,的定义,构造图,G,。,DestroyGraph(&G,);,初始条件：图,G,存在。操作结果：,销毁图,G,。,LocateVex(G,u);,初始条件：图,G,存在，,u,和,G,中顶点有相同特征。操作结果：若,G,中存在和,u,相同的顶点，则,返回该顶点 在图中位置,；否则返回其它信息。,5/25/2026,32,GetVex(G,v);,初始条件：图,G,存在，,v,是,G,中某个顶点。操作结果：返回,v,的值,。,FirstAdjVex(G,v);,初始条件：图,G,存在，,v,是,G,中某个顶点。操作结果：,返回,v,的第一个邻接点。,若该顶点在,G,中没 有邻接点，则返回“空”。,NextAdjVex(G,v,w);,初始条件：图,G,存在，,v,是,G,中某个顶点，,w,是,v,的 邻接顶点。操作结果：,返回,v,的（相对于,w,的）下一个邻接点。,若,w,是,v,的最后一个邻接点，则返回“空”。,5/25/2026,33,PutVex(&G,v,value);,初始条件：图,G,存在，,v,是,G,中某个顶点。操作结果：,对,v,赋值,value,。,InsertVex(&G,v);,初始条件：图,G,存在，,v,和图中顶点有相同特征。操作结果：在图,G,中,增添新顶点,v,。,DeleteVex(&G,v);,初始条件：图,G,存在，,v,是,G,中某个顶点。操作结果：,删除,G,中顶点,v,及其相关的弧,。,5/25/2026,34,InsertArc(&G,v,w);,初始条件：图,G,存在，,v,和,w,是,G,中两个顶点。操作结果：在,G,中,增添弧,，,若,G,是,无向的，则还 增添对称弧,。,DeleteArc(&G,v,w);,初始条件：图,G,存在，,v,和,w,是,G,中两个顶点。操作结果：在,G,中,删除弧,，,若,G,是,无向的，则还 删除对称弧,。,5/25/2026,35,DFSTraverse(G,Visit();,初始条件：图,G,存在，,Visit,是顶点的应用函数。操作结果：对图,G,进行,深度优先,遍历。遍历过程中对每 个顶点调用函数,Visit,一次且仅一次。一旦,visit(),失败，则操作失败。,FSTraverse(G,Visit();,初始条件：图,G,存在，,Visit,是顶点的应用函数。操作结果：对图,G,进行,广度优先,遍历。遍历过程中对每 个顶点调用函数,Visit,一次且仅一次。一旦,visit(),失败，则操作失败。,ADT Graph,5/25/2026,36,是否可以采用顺序存储结构存储图,?,图的特点：顶点之间的关系是,m,:,n,，即,任何两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。,如何存储图,?,考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。,7.2,图的存储结构,5/25/2026,37,7.2,图的存储结构,数组表示法,(,邻接矩阵,),将图的,顶点信息存储在一个一维数组中,，并将它的,邻接矩阵存储在一个二维数组中,即构成图的数组表示。,假设图中顶点数为,n,，,则邻接矩阵,A,定义为,网的邻接矩阵的定义为，当,v,i,到,v,j,有弧相邻接时，,a,ij,的值应为该弧上的权值，否则为。,5/25/2026,38,图的数组,(,邻接矩阵,),存储表示,#define INFINITY INT_MAX;,/,最大值,#define MAX_VERTEX_NUM 20;,/,最大顶点个数,typedef,enum,DG,DN,UDG,UDN,GraphKind,;,/,有向图,有向网,无向图,无向网,typedef,struct,ArcCell,VRType,adj,;,/,VRType,是顶点关系类型。对无权图，用,1,或,0,/,表示相邻否；对带权图，则为权值类型。,InfoType,*info;,/,该弧相关信息的指针,ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM,;,typedef,struct,VertexType,vexsMAX_VERTEX_NUM,;,/,顶点信息,AdjMatrix,arcs,;,/,邻接矩阵,int,vexnum,arcnum,;,/,图的当前顶点数和弧,(,边,),数,GraphKind,kind,;,/,图的种类标志,MGraph,;,5/25/2026,39,有向图的存储结构,G1,B,D,A,C,G1.vexs=A,B,C,D,G1.vexnum=4,G1.arcnum=4,G1.kind=DG,5/25/2026,40,有向图的邻接矩阵,V,1,V,2,V,3,V,4,V,1,V,2,V,3,V,4,vertex=,0 1 1 0,0 0 0 0,0 0 0 1,1 0 0 0,arc=,V,1,V,2,V,3,V,4,V,1,V,2,V,3,V,4,如何求顶点,i,的出度？,邻接矩阵的第,i,行元素之和。,5/25/2026,41,有向图的邻接矩阵,V,1,V,2,V,3,V,4,V,1,V,2,V,3,V,4,vertex=,0 1 1 0,0 0 0 0,0 0 0 1,1 0 0 0,arc=,V,1,V,2,V,3,V,4,V,1,V,2,V,3,V,4,如何求顶点,i,的入度？,邻接矩阵的第,i,列元素之和。,5/25/2026,42,有向图的邻接矩阵,V,1,V,2,V,3,V,4,V,1,V,2,V,3,V,4,vertex=,0 1 1 0,0 0 0 0,0 0 0 1,1 0 0 0,arc=,V,1,V,2,V,3,V,4,V,1,V,2,V,3,V,4,如何判断从顶点,i,到顶点,j,是否存在边？,测试邻接矩阵中相应位置的元素,arcij,是否为,1,。,5/25/2026,43,无向图的存储结构,A,E,C,B,D,G2,G2.vexs=A,B,C,D,E,G2.vexnum=5,G2.arcnum=6,G2.kind=UDG,5/25/2026,44,网图的存储结构,A,D,E,B,C,7,5,3,1,8,6,4,2,G3,G3.vexs=A,B,C,D,E,G3.vexnum=5,G3.arcnum=8,G3.kind=UDN,5/25/2026,45,如何求顶点,i,的度？,无向图的邻接矩阵,V,1,V,3,V,4,V,2,V,1,V,2,V,3,V,4,vertex=,0 1 0 1,1 0 1 1,0 1 0 0,1 1 0 0,arc=,V,1,V,2,V,3,V,4,V,1,V,2,V,3,V,4,邻接矩阵的第,i,行（或第,i,列）非零元素的个数。,5/25/2026,46,如何判断顶点,i,和,j,之间是否存在边？,无向图的邻接矩阵,V,1,V,3,V,4,V,2,V,1,V,2,V,3,V,4,vertex=,0 1 0 1,1 0 1 1,0 1 0 0,1 1 0 0,arc=,V,1,V,2,V,3,V,4,V,1,V,2,V,3,V,4,测试邻接矩阵中相应位置的元素,arcij,是否为,1,。,5/25/2026,47,如何求顶点,i,的所有邻接点？,无向图的邻接矩阵,V,1,V,3,V,4,V,2,V,1,V,2,V,3,V,4,vertex=,0 1 0 1,1 0 1 1,0 1 0 0,1 1 0 0,arc=,V,1,V,2,V,3,V,4,V,1,V,2,V,3,V,4,将数组中第,i,行元素扫描一遍，若,arcij,为,1,，则顶点,j,为顶点,i,的邻接点。,5/25/2026,48,特点,：,无向图,的邻接,矩阵对称,，可,压缩存储,；有,n,个顶点的无向图需存储空间为,n(n+1)/2,。,有向图,邻接,矩阵不一定对称,；有,n,个顶点的有向图需存储空间为,n,。,无向图,中顶点,Vi,的度,TD(Vi),是邻接矩阵,A,中第,i,行元素之和,。,有向图,中，,顶点,Vi,的,出度是,A,中第,i,行元素之和,。,顶点,Vi,的,入度是,A,中第,i,列元素之和,。,邻接矩阵的优缺点,优点,：容易判定顶点间有无边（弧）和计算顶点的度（出度、入度）。,缺点,：边数较少时，空间浪费较大。,5/25/2026,49,网图的邻接矩阵,网图的邻接矩阵可定义为：,arcij,w,ij,若,(,v,i,v,j,),E,（或,E,）,0,若,i,=,j,其他,V,1,V,2,V,3,V,4,2,7,8,5,0 2 5 ,0 ,0 8,7 0,arc=,5/25/2026,50,7.2.2,图的邻接表表示法,引入原因,邻接矩阵在稀疏图时空间浪费较大。,实现,为图中,每个顶点建立一个单链表,，第,i,个单链表中的结点表示依附于顶点,Vi,的边（有向图中指以,Vi,为尾的弧）。,每个链表附设一个表头结点,。,表结点,adjvex,nextarc,info,与,Vi,邻接的点在表头数组中的位置,头结点,data,firstarc,5/25/2026,51,图的邻接表存储表示,#define MAX_VERTEX_NUM 20;,typedef,struct,ArcNode,int,adjvex,;,/,该弧所指向的顶点的位置,struct,ArcNode,*,nextarc,;,/,指向下一条弧的指针,InfoType,*info;,/,该弧相关信息的指针,ArcNode,;,typedef,struct,VNode,VertexType,data;,/,顶点信息,ArcNode,*,firstarc,;,/,指向第一条依附该顶点的弧,AdjListMAX_VERTEX_NUM,;,typedef,struct,AdjList,vertices,;,/,顶点数组,int,vexnum,arcnum,;,/,图的当前顶点数和弧数,int,kind;,/,图的种类标志,ALGraph,;,5/25/2026,52,1,0,3,2,3,1,0,1,V,1,V,2,V,3,V,4,0,1,2,3,vertex,firstedge,V,1,V,3,V,4,V,2,无向图的邻接表,边表中的结点表示什么？,每个结点对应图中的一条边，,邻接表的空间复杂度为,O,(,n,+,e,),。,5/25/2026,53,1,0,3,2,3,1,0,1,V,1,V,2,V,3,V,4,0,1,2,3,vertex,firstedge,V,1,V,3,V,4,V,2,无向图的邻接表,如何求顶点,i,的度？,顶点,i,的边表中结点的个数。,5/25/2026,54,如何判断顶点,i,和顶点,j,之间是否存在边,?,测试顶点,i,的边表中是否存在终点为,j,的结点。,1,0,3,2,3,1,0,1,V,1,V,2,V,3,V,4,0,1,2,3,vertex,firstedge,V,1,V,3,V,4,V,2,无向图的邻接表,5/25/2026,55,有向图的邻接表,V,1,V,2,V,3,V,4,1,2,2,0,V,1,V,2,V,3,V,4,0,1,2,3,vertex,firstedge,如何求顶点,i,的出度？,顶点,i,的出边表中结点的个数。,5/25/2026,56,有向图的邻接表,V,1,V,2,V,3,V,4,1,2,2,0,V,1,V,2,V,3,V,4,0,1,2,3,vertex,firstedge,如何求顶点,i,的入度？,各顶点的出边表中以顶点,i,为,终点的结点个数。,5/25/2026,57,有向图的邻接表,V,1,V,2,V,3,V,4,1,2,3,0,V,1,V,2,V,3,V,4,0,1,2,3,vertex,firstedge,如何求顶点,i,的所有邻接点？,遍历顶点,i,的边表，该边表中的所有终点都是顶点,i,的邻接点。,5/25/2026,58,网图的邻接表,V,1,V,2,V,3,V,4,2,7,8,5,2,1,V,1,V,2,V,3,V,4,0,1,2,3,vertex,firstedge,5,2,8,3,7,0,5/25/2026,59,优缺点,优点,：空间较省；无向图容易求各顶点的度；有向图容易求顶点的出度；,缺点,：求有向图顶点的入度则不容易，要遍历整个表。,为了求顶点的入度，有时可设逆邻接表（指向某顶点的邻接点链接成单链表）。,b,d,a,c,0,1,2,3,a,c,d,b,data,firstarc,3,0,0,2,adjvex,next,逆邻接表,5/25/2026,60,7.2.3,图的十字链表表示法,引入原因,对于同一个,有向图需要同时用邻接表和逆邻接表,时，不方便。,实现,将在有向图的,邻接表和逆邻接表中两次出现的同一条弧用一个结点表示,，由于在邻接表和逆邻接表中的顶点,数据,是相同的，则在十字链表中,只需要出现一次,，但需,保留分别指向第一条,出弧,和第一条,入弧,的指针,。,G1,b,d,a,c,0,1,2,3,a,c,d,b,data,firstarc,2,1,3,0,adjvex,next,邻接表,5/25/2026,61,7.2.3,图的十字链表表示法,引入原因,对于同一个,有向图需要同时用邻接表和逆邻接表,时，不方便。,实现,将在有向图的,邻接表和逆邻接表中两次出现的同一条弧用一个结点表示,，由于在邻接表和逆邻接表中的顶点,数据,是相同的，则在十字链表中,只需要出现一次,，但需,保留分别指向第一条,出弧,和第一条,入弧,的指针,。,G1,b,d,a,c,逆邻接表,0,1,2,3,a,c,d,b,data,firstarc,3,0,0,2,adjvex,next,5/25/2026,62,弧结点,tailvex,headvex,hlink,tlink,info,顶点结点,data,firstin,firstout,弧尾位置,弧头位置,弧尾相同的下一条弧指针,弧相关信息的指针,弧头相同的下一条弧指针,指向该顶点第一条入弧,指向该顶点第一条出弧,5/25/2026,63,0 2,0 1,2 3,2 0,3 2,3 1,3 0,b,d,a,c,a,b,c,d,0,1,2,3,求,结点的入度和出度的方法？,5/25/2026,64,7.2.4,图的邻接多重表表示法,引入原因,无向图的邻接表中,每一条边有两个结点，,给对图的边进行访问的操作带来不便。有些时候需要同时找到表示同一条边的两个结点（如删除一条边）。,a,e,c,b,d,0,1,2,3,a,c,d,b,data,firstarc,3,1,0,1,adjvex,next,4,e,3,2,4,0,4,2,1,2,5/25/2026,65,实现,每条边用一个结点表示。,边结点,mark,ivex,ilink,jvex,jlink,info,顶点结点,mark,firstedge,访问标记,边依附的一个顶点,边依附的另一个顶点,依附这个顶点的下一条边指针,依附这个顶点的下一条边指针,访问标记,指向第一条 依附该顶点的边,5/25/2026,66,a,e,c,b,d,0,1,2,3,a,c,d,b,4,e,0 1,0 3,2 3,2 1,2 4,4 1,5/25/2026,67,7.3,图的遍历,图的遍历,从图中某一顶点出发，访问图中其余顶点，使每个顶点被访问一次且只被访问一次,。,可以从图中,任意一个顶点出发,进行遍历。,遍历中需解决的问题,确定一搜索路径,；,确保,每个顶点被访问到,；,确保每个顶点,只能被访问一次,。,解决方法,深度优先和广度优先。,设,辅助数组,visited,，,初始时，数组元素的值均为,0,或,false,，,表示未被遍历，一旦遍历，就置为,1,或,true,。,5/25/2026,68,7.3.1,深度优先搜索,方法,从图的某一顶点,V0,出发，访问此顶点；,然后依次从,V0,的未被访问的邻接点出发，深度优先遍历图，直至图中所有和,V0,相通的顶点都被访问到；,若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。,访问任意一个与,V0,邻接的顶点,W1,，,再从,W1,出发；,访问与,W1,邻接且未被访问过的任意顶点,W2,，,再从,W2,出发；,重复以上过程，直到一个所有邻接点都被访问过的顶点为止；,退回到尚有邻接点未被访问过的顶点，再从该顶点出发；,直到所有的被访问过的顶点的邻接点都已被访问过为止。,5/25/2026,69,深一层递归,递归返回,深度优先遍历序列,?,入栈序列,?,出栈序列,?,V,1,V,3,V,2,V,4,V,5,V,6,V,7,V,8,V,1,遍历序列：,V,1,V,2,V,2,V,4,V,4,V,5,V,5,5/25/2026,70,深一层递归,递归返回,深度优先遍历序列,?,入栈序列,?,出栈序列,?,V,1,V,3,V,2,V,4,V,5,V,6,V,7,V,8,V,1,遍历序列：,V,1,V,2,V,2,V,4,V,4,V,5,V,8,V,8,5/25/2026,71,深一层递归,递归返回,深度优先遍历序列,?,入栈序列,?,出栈序列,?,6.1,图的逻辑结构,V,1,V,3,V,2,V,4,V,5,V,6,V,7,V,8,V,1,遍历序列：,V,1,V,2,V,2,V,4,V,4,V,5,V,8,5/25/2026,72,深一层递归,递归返回,深度优先遍历序列,?,入栈序列,?,出栈序列,?,V,1,V,3,V,2,V,4,V,5,V,6,V,7,V,8,V,1,遍历序列：,V,1,V,7,V,2,V,4,V,5,V,8,V,3,V,3,V,6,V,6,V,7,5/25/2026,73,深度优先遍历算法,7.4,、,7.5,Boolen,visitedMAX;,/,访问标志数组,Status(*,visitFunc)(int,v);,/,函数变量,void,DFSTraverse(Graph,G,Status(*,visit)(int,v),/,对图,G,作深度优先遍历,visitFunc,=visit;,/,使用全局变量,visitFunc,，,/,使,DFS,不必设函数指针参数,for(v=0;v,G.vexnum,;+v)visitedv=FALSE;,/,访问标识数组初始化,for(v=0;v=0;w=,NextAdjVex(G,v,w,),if(!visitedw)DFS(G,w);,/,对,v,的尚未访问过的邻接,/,顶点,w,递归调用,DFS,/DFS,5/25/2026,75,V,1,V,2,V,4,V,5,V,3,V,7,V,6,V,8,深度遍历：,V1,0,1,2,3,V1,V3,V4,V2,data,firstarc,1,6,7,2,adjvex,next,4,V5,5,3,0,4,0,1,7,1,V6,V7,V8,5,6,7,6,2,5,2,4,3,V3,V7,V6,V2,V5,V8,V4,5/25/2026,76,V,1,V,2,V,4,V,5,V,3,V,7,V,6,V,8,0,1,2,3,V1,V3,V4,V2,data,firstarc,1,6,7,2,adjvex,next,4,V5,5,3,7,1,V6,V7,V8,5,6,7,6,深度遍历：,V1,V3,V7,V6,V2,V4,V8,V5,5/25/2026,77,7.3.2,广度优先搜索,方法,从图的,某一顶点,V0,出发,，,访问此顶点,后，,依次访问,V0,的各个未曾访问过的邻接点,；,然后分别,从这些邻接点出发,，广度优先遍历图，,直至图中所有已被访问的顶点的邻接点都被访问到,；,若此时,图中尚有顶点未被访问,，则,另选图中一个未被访问的顶点作起点,，重复上述过程，,直至图中所有顶点都被访问为止,。,广度优先遍历的过程是以,v,为起始点，由近至远，依次访问和,v,有路径相通且最短路径长度为,1,2,的顶点。,5/25/2026,78,广度优先遍历序列,?,入队序列,?,出队序列,?,V,1,V,3,V,2,V,4,V,5,V,6,V,7,V,8,遍历序列：,V,1,V,1,5/25/2026,79,广度优先遍历序列,?,入队序列,?,出队序列,?,V,1,V,3,V,2,V,4,V,5,V,6,V,7,V,8,遍历序列：,V,1,V,2,V,2,V,3,V,3,5/25/2026,80,广度优先遍历序列,?,入队序列,?,出队序列,?,V,1,V,3,V,2,V,4,V,5,V,6,V,7,V,8,遍历序列：,V,1,V,2,V,3,V,3,V,4,V,4,V,5,V,5,5/25/2026,81,广度优先遍历序列,?,入队序列,?,出队序列,?,V,1,V,3,V,2,V,4,V,5,V,6,V,7,V,8,遍历序列：,V,1,V,2,V,3,V,4,V,4,V,5,V,5,V,6,V,6,V,7,V,7,5/25/2026,82,广度优先遍历序列,?,入队序列,?,出队序列,?,V,1,V,3,V,2,V,4,V,5,V,6,V,7,V,8,遍历序列：,V,1,V,2,V,3,V,4,V,5,V,5,V,6,V,6,V,7,V,7,V,8,V,8,5/25/2026,83,V,1,V,2,V,4,V,5,V,3,V,7,V,6,V,8,V8,V7,V6,V5,V4,V3,V2,V1,V,1,V,2,V,4,V,5,V,3,V,7,V,6,V,8,V8,V7,V6,V5,V4,V3,V2,V1,5/25/2026,84,广度优先遍历算法,7.6,void,BFSTraverse(,Graph,G,Status(*,visit)(int,v),),/,对图,G,进行广度优先搜索遍历,for(v=0;v,G.vexnum,;+v)visitedv=FALSE;,InitQueue(Q,);,/,设置空队列,Q,for(v=0;v=0;w=,NextAjdVex(G,u,w,)if(!visitedw),visitedw=TRUE;Visit(w);,/,访问第,w,个顶点,EnQueue(Q,w);,/if,/while,/if,DestroyQueue(Q,);,/,BFSTraverse,123456789101112,5/25/2026,85,1,4,2,3,5,0,1,2,3,1,3,4,2,data,firstarc,4,4,3,2,adjvex,next,4,5,0,4,0,0,3,2,1,1,5/25/2026,86,7,4,图的连通性问题,7.4.1,无向图的连通分量和生成树,无向图的连通分量,对于,连通图,，仅需从图中,任一顶点出发,，进行,DFS,或,BFS,搜索，,即可遍历图的全部顶点,；,对于,非连通图,，则需,从多个顶点,出发进行,DFS,或,BFS,搜索，才能,遍历完图的全部顶点,。,每一次从一个新的起始点出发,进行,DFS,或,BFS,搜索过程中,所得的顶点访问序列,就是各,连通分量的顶点集,。,5/25/2026,87,A,B,L,M,C,F,D,E,G,H,K,I,J,邻接表,12,11,10,9,8,7,6,5,4,3,2,1,0,M,L,K,J,I,H,G,F,E,D,C,B,A,11,5,2,1,12,0,0,4,3,0,10,8,7,10,6,6,12,11,7,6,12,9,0,11,9,1,5/25/2026,88,深度优先遍历的结果为,(3,次,DFS,过程,),从,A,出发：,ALMJBFC,从,D,出发：,DE,从,G,出发：,GKHI,连通分量：三个顶点集,+,依附于这个顶点集中顶点的边。,D,E,G,H,K,I,A,B,L,M,C,F,J,5/25/2026,89,生成树,所有顶点均由边连接在一起，但不存在回路的图称为生成树。,一个有,n,个顶点的连通图的生成树有,n-1,条边；,一个图可以有,许多棵不同的生成树。,对于连通图，,调用,DFS,所经过的边的集合,和,图的全部顶点,构成了图的极小连通子图，即连通图的一棵,深度优先生成树,。,对于连通图，,调用,BFS,所经过的边的集合,和,图的全部顶点,构成了图的极小连通子图，即连通图的,一棵,广度优先生成树,。,对于非连通图，每个连通分量的顶点集和所经过的边一起构成若干棵生成树，这些连通图的生成树构成非连通图的,生成森林,。,5/25/2026,90,V,1,V,2,V,4,V,5,V,3,V,7,V,6,V,8,V7,V6,V3,V5,V8,V4,V2,V1,深度遍历,V,1,V,2,V,4,V,5,V,