图数据结构C语言版.ppt

《图数据结构C语言版.ppt》由会员分享，可在线阅读，更多相关《图数据结构C语言版.ppt（92页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第7 7章章 图图图是另一种非线性数据结构，是一种更为复杂的数据图是另一种非线性数据结构，是一种更为复杂的数据结构。在图中，数据元素之间是多对多的关系，即一个数结构。在图中，数据元素之间是多对多的关系，即一个数据元素对应多个直接前驱元素和多个直接后继元素。图的据元素对应多个直接前驱元素和多个直接后继元素。图的应用领域十分广泛，如化学分析、工程设计、遗传学、人应用领域十分广泛，如化学分析、工程设计、遗传学、人工智能等。工智能等。7.1 7.1 图的基本概念图的基本概念7.1.1 图的定义图是由顶点集合与边的集合组成的数据结构。图图是由顶点集合与边的集合组成的数据结构。图G的的形式化定义为形式化

2、定义为G=(V,E)其中，其中，V是图中结点是图中结点(Vertices)的非空有限集合，的非空有限集合，E是是图中边图中边(Edges)的有限集合。即图的定义也可以这样表述：的有限集合。即图的定义也可以这样表述：图是由有限个结点的集合图是由有限个结点的集合(V)及结点与结点相连的边的集合及结点与结点相连的边的集合(E)组合而成。组合而成。7.1 7.1 图的基本概念图的基本概念如果如果E，则，则表示从顶点表示从顶点x到顶点到顶点y存在一存在一条弧，条弧，x称为弧尾或起始点，称为弧尾或起始点，y称为弧头或终端点。这种图称为弧头或终端点。这种图的边是有方向的，这样的图称为有向图。如果的边是有方向

3、的，这样的图称为有向图。如果E且且有有E，即，即E是对称关系，这时用无序对是对称关系，这时用无序对(x,y)代替两代替两个有序对，表示个有序对，表示x与与y之间存在一条边，这样的图称为无向之间存在一条边，这样的图称为无向图。有向图和无向图的表示如图图。有向图和无向图的表示如图7.1所示。所示。7.1 7.1 图的基本概念图的基本概念在在图图7.1中中，有有向向图图G1可可以以表表示示为为G1=(V1,E1)，其其中中，顶顶点点集集合合V1=A,B,C,D，边边的的集集合合E1=,。无无向向图图G2可可 以以 表表 示示 为为 G2=(V2,E2)，其其 中中，顶顶 点点 集集 合合V2=A,B

4、,C,D，边边的的集集合合E2=(A,B),(A,D),(B,C),(B,D),(C,D)。7.1 7.1 图的基本概念图的基本概念假假设设图图的的顶顶点点数数目目是是n，图图的的边边数数或或者者弧弧的的数数目目是是e。如如果果不不考考虑虑顶顶点点到到自自身身的的边边或或弧弧，即即如如果果存存在在弧弧，则则vivj。对对于于无无向向图图，边边数数e的的取取值值范范围围为为0n(n-1)/2。将将具具有有n(n-1)/2条条边边的的无无向向图图称称为为完完全全图图或或无无向向完完全全图图。对对于于有有向向图图，弧弧度度e的的取取值值范范围围是是0n(n-1)。将将具具有有n(n-1)条条弧弧的的

5、有有向向图图称称为为有有向向完完全全图图。当当enlogn时，称为稠密图。时，称为稠密图。7.1 7.1 图的基本概念图的基本概念7.1.2 图的相关概念1.邻接顶点在无向图在无向图G=(V,E)中，如果中，如果(u,v)是是G中的一条边，则中的一条边，则称称u和和v互为邻接顶点，并称边互为邻接顶点，并称边(u,v)依附于顶点依附于顶点u和和v。在。在图图7.1所示的无向图所示的无向图G2中，顶点中，顶点A的邻接顶点有的邻接顶点有B和和D。在。在有向图有向图G=(V,A)中，如果中，如果是是G的一条弧，则称顶点的一条弧，则称顶点u邻邻接到顶点接到顶点v，顶点，顶点v邻接自顶点邻接自顶点u，并称

6、，并称与顶点与顶点u和顶和顶点点v相关联。在图相关联。在图7.1所示的有向图所示的有向图G1中，顶点中，顶点A邻接到顶邻接到顶点点B，弧，弧与顶点与顶点A和和B相关联。相关联。7.1 7.1 图的基本概念图的基本概念2.顶点的度顶点顶点v的度是指与其相关联的边的数目，记作的度是指与其相关联的边的数目，记作TD(v)。对于有向图，顶点的度为该顶点的入度与出度之和，即对于有向图，顶点的度为该顶点的入度与出度之和，即TD(v)=ID(v)+OD(v)。其中，顶点。其中，顶点v的入度的入度ID(v)是以是以v为终为终点的有向边点的有向边(弧弧)的条数；顶点的条数；顶点v的出度的出度OD(v)是以是以v

7、为始点为始点的有向边的有向边(弧弧)的条数。在图的条数。在图7.1所示的有向图所示的有向图G1中，顶点中，顶点A的入度的入度ID(A)为为2，顶点，顶点A的出度的出度OD(A)为为3，因此，顶点，因此，顶点A的度的度TD(A)=ID(A)+OD(A)=2+3=5。7.1 7.1 图的基本概念图的基本概念3.路径在图在图G=(V,E)中，如果从顶点中，如果从顶点vi出发有一组边可到达顶出发有一组边可到达顶点点vj，则称顶点，则称顶点vi到顶点到顶点vj的顶点序列为从顶点的顶点序列为从顶点vi到顶点到顶点vj的路径。在图的路径。在图7.1所示的无向图所示的无向图G2中，从顶点中，从顶点A到顶点到顶

8、点C的的路径为路径为A，B，C或或A，D，C。7.1 7.1 图的基本概念图的基本概念4.回路在路径中，如果第一个顶点与最后一个顶点相同，则在路径中，如果第一个顶点与最后一个顶点相同，则这样的路径称为回路或环。在路径所经过的顶点序列中，这样的路径称为回路或环。在路径所经过的顶点序列中，如果顶点不重复出现，则称这样的路径为简单路径。在回如果顶点不重复出现，则称这样的路径为简单路径。在回路中，除了第一个顶点和最后一个顶点外，如果其他的顶路中，除了第一个顶点和最后一个顶点外，如果其他的顶点不重复出现，则称这样的回路为简单回路或简单环。点不重复出现，则称这样的回路为简单回路或简单环。7.1 7.1 图

9、的基本概念图的基本概念5.子图假设存在两个图假设存在两个图G=V,E和和G=V,E，如果，如果G的顶点的顶点和关系都是和关系都是V的子集，即有的子集，即有VV，EE，则，则G为为G的子图，如的子图，如图图7.2所示。所示。7.1 7.1 图的基本概念图的基本概念6.连通图和强连通图在无向图中，如果从顶点在无向图中，如果从顶点vi到顶点到顶点vj存在路径，则称存在路径，则称顶点顶点vi到到vj是连通的。如果图中的任何两个顶点之间都是连是连通的。如果图中的任何两个顶点之间都是连通的，则称图是连通图。无向图中的极大连通子图称为连通的，则称图是连通图。无向图中的极大连通子图称为连通分量。无向图通分量。

10、无向图G3与连通分量如图与连通分量如图7.3所示。所示。7.1 7.1 图的基本概念图的基本概念在在有有向向图图中中，如如果果对对于于任任意意两两个个顶顶点点vi和和vj，且且vivj，从从顶顶点点vi到到顶顶点点vj和和顶顶点点vj到到顶顶点点vi都都存存在在路路径径，则则该该图图称称为为强强连连通通图图。有有向向图图的的极极大大强强连连通通子子图图称称为为强强连连通通分分量量。有向图有向图G4的强连通分量如图的强连通分量如图7.4所示。所示。7.1 7.1 图的基本概念图的基本概念7.生成树一个连通图的生成树是一个极小连通子图，它含有图一个连通图的生成树是一个极小连通子图，它含有图中的全部

11、顶点，但只有足以构成一棵树的中的全部顶点，但只有足以构成一棵树的n-1条边。图条边。图7.3中无向图中无向图G3的最大连通分量的一棵生成树如图的最大连通分量的一棵生成树如图7.5所示。所示。7.1 7.1 图的基本概念图的基本概念8.权在实际应用中，图的边或弧往往与具有一定意义的数在实际应用中，图的边或弧往往与具有一定意义的数有关，这种与边或弧相关的数称为权，权反映了这条边或有关，这种与边或弧相关的数称为权，权反映了这条边或弧的某种特征的数据。例如，权通常表示两个顶点之间的弧的某种特征的数据。例如，权通常表示两个顶点之间的距离或者时间。距离或者时间。9.网带权的图称为网。一个网如图带权的图称为

12、网。一个网如图7.6所示。所示。7.1 7.1 图的基本概念图的基本概念7.1.3 图的抽象数据类型1.数据对象集合图的数据对象集合为图的各个元素的集合。图分为有向图和无向图，图中结点之间的关系用弧或边表示，连接弧或边的结点称为顶点。2.基本操作集合(1)CreateGraph(&G)：图的的创建。建。初始条件：初始条件：图G不存在。不存在。操作操作结果：构造一个果：构造一个图G。(2)DestroyGraph(&T)：销毁图。初始条件：初始条件：图G存在。存在。操作操作结果：果：销毁图G。7.1 7.1 图的基本概念图的基本概念(3)LocateVertex(G,v)：根据：根据顶点点值定位

13、。定位。初始条件：初始条件：图G存在，存在，顶点点v值合法。合法。操作操作结果：如果果：如果图G中存在中存在顶点点v，则返回返回顶点点v在在图G中的位置。如果中的位置。如果图G中没有中没有顶点点v，则返回返回值为空。空。(4)GetVertex(G,i)：根据序号定位。：根据序号定位。初始条件：初始条件：图G存在。存在。操作操作结果：返回果：返回图G中序号中序号i对应的的顶点点值。(5)FirstAdjVertex(G,v)：返回：返回v的第一个的第一个邻接接顶点。点。初始条件：初始条件：图G存在。存在。操作操作结果：返回果：返回图G中中顶点点v的第一个的第一个邻接接顶点。如果点。如果v没有没

14、有邻接接顶点或点或图中没有中没有顶点点v，则函数返回空。函数返回空。7.1 7.1 图的基本概念图的基本概念(6)NextAdjVertex(G,v,w)：返回：返回v的下一个的下一个邻接接顶点。点。初始条件：初始条件：图G存在，存在，w是是图G中中v的某个的某个邻接接顶点。点。操作操作结果：返回果：返回顶点点v的下一个的下一个邻接接顶点。点。(7)InsertVertex(&G,v)：插入：插入顶点。点。初始条件：初始条件：图G存在，存在，v值合法。合法。操作操作结果：在果：在图G中增加新的中增加新的顶点点v，图的的顶点数增点数增1。(8)DeleteVertex(&G,v)：删除除顶点。点

15、。初始条件：初始条件：图G存在，存在，v值合法。合法。操作操作结果：果：删除除图G的的顶点点v及与及与顶点点v相关相关联的弧。的弧。7.1 7.1 图的基本概念图的基本概念(9)InsertArc(&G,v,w)：插入弧。：插入弧。初始条件：初始条件：图G存在，存在，v和和w合法。合法。操作操作结果：在果：在图G中增加一条从中增加一条从v到到w的弧。的弧。(10)DeleteArc(&G,v,w)：删除弧。除弧。初始条件：初始条件：图G存在，存在，v和和w合法，且存在弧合法，且存在弧(v,w)。操作操作结果：果：删除除图G中从中从v到到w的弧。的弧。(11)DFSTraverseGraph(G

16、)：图的深度遍的深度遍历操作。操作。初始条件：初始条件：图G存在。存在。操作操作结果：从某个果：从某个顶点出点出发，按照深度，按照深度优先的次序，先的次序，对图G中的每个中的每个顶点点访问一次且一次且仅访问一次。一次。7.2 图的存储结构7.2.1 邻接矩阵表示法图的邻接矩阵表示法也称为数组表示法，它采用两个图的邻接矩阵表示法也称为数组表示法，它采用两个数组来表示图：一个是用于存储顶点信息的一维数组，一数组来表示图：一个是用于存储顶点信息的一维数组，一个是用于存储图中顶点之间的关联关系的二维数组。这个个是用于存储图中顶点之间的关联关系的二维数组。这个关联关系的数组被称为邻接矩阵。关联关系的数组

17、被称为邻接矩阵。如果图是一个无权图，则图的邻接矩阵是具有以下性如果图是一个无权图，则图的邻接矩阵是具有以下性质的质的nn的矩阵：的矩阵：7.2 图的存储结构在在 图图 7.1中中，有有 向向 图图 G1的的 弧弧 的的 集集 合合 为为A=,，无无 向向 图图G2的的边边的的集集合合为为E=(A,B),(A,D),(B,C),(B,D),(C,D)。它它们们的邻接矩阵表示如图的邻接矩阵表示如图7.7所示。所示。7.2 图的存储结构图的邻接矩阵存储结构用图的邻接矩阵存储结构用C语言描述如下语言描述如下#defineINFINITY32768/*定定义一个无限大的一个无限大的值*/#defineM

18、AXVERTEX50/*最大最大顶点个数点个数*/typedefenumDG,DN,UG,UNGraphKind;/*图的的类型：有向型：有向图、有向网、无向、有向网、无向图和无向网和无向网*/typedefstructVRTypeadj;/*对于无于无权图，用，用1表示相表示相邻，0表示不相表示不相邻；对于于带权图，存，存储权值*/InfoPtr*info;/*与弧或与弧或边的相关信息的相关信息*/ArcNode,AdjMatrixMAXVERTEXMAXVERTEX;typedefstruct/*图的的类型定型定义*/VertexTypevertexMAXVERTEX;/*顶点数点数组*/

19、AdjMatrixarcs;/*邻接矩接矩阵，存，存储边或弧的信息或弧的信息*/intvexnum,arcnum;/*顶点数和点数和边(弧弧)的数目的数目*/GraphKindkind;/*图的的类型型*/MGraph;7.2 图的存储结构【例例7.1】采采用用邻接接矩矩阵创建建一一个个有有向向网网N，如如图7.9所示。所示。voidCreateGraph(MGraph*N)/*采用采用邻接矩接矩阵表示法表示法创建有向网建有向网N*/inti,j,k,w;VertexTypev1,v2;printf(请输请输入有向网的入有向网的顶顶点数点数,弧数弧数:);scanf(%d,%d,&(*N).v

20、exnum,&(*N).arcnum);printf(请输请输入入%d个个顶顶点点:,N-vexnum);7.2 图的存储结构for(i=0;ivexnum;i+)/*创建一个数建一个数组，用于保存网的各个，用于保存网的各个顶点点*/scanf(%s,N-vertexi);for(i=0;ivexnum;i+)/*初始化初始化邻接矩接矩阵*/for(j=0;jvexnum;j+)N-arcsij.adj=INFINITY;N-arcsij.info=NULL;/*弧的信息初始化弧的信息初始化为空空*/printf(请输入入%d条弧的弧尾条弧的弧尾弧弧头权值(以空格分隔以空格分隔):n,N-ar

21、cnum);for(k=0;karcnum;k+)scanf(%s%s%d,v1,v2,&w);/*输入两个入两个顶点和弧的点和弧的权值*/i=LocateVertex(*N,v1);j=LocateVertex(*N,v2);N-arcsij.adj=w;N-kind=DN;/*图的的类型型为有向网有向网*/7.2 图的存储结构intLocateVertex(MGraphN,VertexTypev)/*在在顶点向量中点向量中查找找顶点点v，找到返回在向量的序号，找到返回在向量的序号，否否则返回返回-1*/inti;for(i=0;iN.vexnum;+i)if(strcmp(N.vertex

22、i,v)=0)returni;return-1;7.2 图的存储结构voidDestroyGraph(MGraph*N)/*销毁网网N*/inti,j;for(i=0;ivexnum;i+)/*释放弧的相关信息放弧的相关信息*/for(j=0;jvexnum;j+)if(N-arcsij.adj!=INFINITY)/*如果存在弧如果存在弧*/if(N-arcsij.info!=NULL)/*如果弧有相关信息，如果弧有相关信息，释放放该信息占用的空信息占用的空间*/free(N-arcsij.info);N-arcsij.info=NULL;N-vexnum=0;/*将网的将网的顶顶点数置点数

23、置为为0*/N-arcnum=0;/*将网的弧的数目置将网的弧的数目置为为0*/7.2 图的存储结构7.2.2 邻接表表示法一个图的邻接表表示由表头结点表和边表两部分构成。(1)表头结点表：表头结点采用顺序存储结构实现，这样可以随机地访问任意顶点。表头结点由两个域组成：数据域和指针域。其中，数据域用来存放顶点信息，指针域用来指向边表中的第一个结点。(2)边表：边表由三个域组成：邻接点域、数据域和指针域。其中，邻接点域表示与相应的表头顶点邻接点的位置，数据域存储与边或弧的信息，指针域用来指示下一个边或弧的结点。表头结点与边表结点的存储结构如图7.11所示。7.2 图的存储结构例例如如，图图7.1

24、中中的的两两个个图图G1和和G2用用邻邻接接表表表表示示如如图图7.12所所示示。用用表表头头结结点点存存储储图图中中的的各各个个顶顶点点，边边表表存存储储与与对应结点相关联的顶点编号。对应结点相关联的顶点编号。7.2 图的存储结构图的邻接表存储结构可以用图的邻接表存储结构可以用C语言描述如下：语言描述如下：#defineMAXVERTEX100/*最大最大顶点个数点个数*/typedefenumDG,DN,UG,UNGraphKind;/*图的的类型：有向型：有向图、有向网、无、有向网、无向向图和无向网和无向网*/typedefstructArcNode/*边表表结点的点的类型定型定义*/i

25、ntadjvex;/*弧指向的弧指向的顶点的位置点的位置*/InfoPtr*info;/*与弧相关的信息与弧相关的信息*/structArcNode*nextarc;/*指示下一个与指示下一个与该顶点相点相邻接的接的顶点点*/ArcNode;typedefstructVNode/*表表头结点的点的类型定型定义*/VertexTypedata;/*用于存用于存储顶点点*/ArcNode*firstarc;/*指示第一个与指示第一个与该顶点点邻接的接的顶点点*/VertexNode,AdjListMAXVERTEX;typedefstruct/*图的的类型定型定义*/AdjListvertex;i

26、ntvexnum,arcnum;/*图的的顶点数目与弧的数目点数目与弧的数目*/GraphKindkind;/*图的的类型型*/AdjGraph;7.2 图的存储结构有时为了方便求某个顶点的入度，需要建立一个有向有时为了方便求某个顶点的入度，需要建立一个有向图的逆邻接链表，也就是为每个顶点图的逆邻接链表，也就是为每个顶点vi建立一个以建立一个以vi为弧头为弧头的链表。图的链表。图7.1所示的有向图所示的有向图G1的逆邻接链表如图的逆邻接链表如图7.13所示。所示。7.2 图的存储结构【例【例7.2】编写算法，采用写算法，采用邻接表接表创建建图7.1中的无向中的无向图G2。voidCreateG

27、raph(AdjGraph*G)/*采用采用邻接表存接表存储结构，构，创建无向建无向图G*/inti,j,k;VertexTypev1,v2;/*定定义两个两个顶点点v1和和v2*/ArcNode*p;printf(请输入入图的的顶点数点数,边数数(逗号分隔逗号分隔):);scanf(%d,%d,&(*G).vexnum,&(*G).arcnum);printf(请输入入%d个个顶点的点的值:n,G-vexnum);for(i=0;ivexnum;i+)/*将将顶点存点存储在在头结点中点中*/scanf(%s,G-vertexi.data);G-vertexi.firstarc=NULL;/*

28、将相关将相关联的的顶点置点置为空空*/printf(请输入弧尾和弧入弧尾和弧头(以空格作以空格作为间隔隔):n);for(k=0;karcnum;k+)/*建立建立边链表表*/scanf(%s%s,v1,v2);i=LocateVertex(*G,v1);j=LocateVertex(*G,v2);/*j为入入边i为出出边创建建邻接表接表*/7.2 图的存储结构p=(ArcNode*)malloc(sizeof(ArcNode);p-adjvex=j;p-info=NULL;p-nextarc=G-vertexi.firstarc;G-vertexi.firstarc=p;/*i为入边为入边j

29、为出边创建邻接表为出边创建邻接表*/p=(ArcNode*)malloc(sizeof(ArcNode);p-adjvex=i;p-info=NULL;p-nextarc=G-vertexj.firstarc;G-vertexj.firstarc=p;(*G).kind=UG;7.2 图的存储结构intLocateVertex(AdjGraphG,VertexTypev)/*返回图中顶点对应的位置返回图中顶点对应的位置*/inti;for(i=0;iG.vexnum;i+)if(strcmp(G.vertexi.data,v)=0)returni;return-1;voidDestroyGra

30、ph(AdjGraph*G)/*销毁无向无向图G*/inti;ArcNode*p,*q;for(i=0;ivertexi.firstarc;/*p指向指向边表的第一个表的第一个结点点*/if(p!=NULL)/*如果如果边表不表不为空，空，则释放放边表的表的结点点*/q=p-nextarc;free(p);p=q;(*G).vexnum=0;/*将将顶点数置点数置为0*/(*G).arcnum=0;/*将将边的数目置的数目置为0*/7.2 图的存储结构7.2.3 十字链表表示法十字链表十字链表(OrthogonalList)是有向图的又一种链式存是有向图的又一种链式存储结构。实际上，它是将有向

31、图的邻接表与逆邻接链表结储结构。实际上，它是将有向图的邻接表与逆邻接链表结合起来得到的一种链表。在十字链表中，同样包括表头结合起来得到的一种链表。在十字链表中，同样包括表头结点和弧结点。点和弧结点。弧结点包含五个域：尾域弧结点包含五个域：尾域tailvex、头域、头域headvex、infor域和两个指针域域和两个指针域hlink、tlink。其中，尾域。其中，尾域tailvex用用于表示弧尾顶点在图中的位置，头域于表示弧尾顶点在图中的位置，头域headvex表示弧头顶表示弧头顶点在图中的位置，点在图中的位置，infor域表示弧的相关信息，指针域域表示弧的相关信息，指针域hlink指向弧头相同

32、的下一条弧，指向弧头相同的下一条弧，tlink指向弧尾相同的下一条弧。指向弧尾相同的下一条弧。7.2 图的存储结构有向图的十字链表存储表示如图有向图的十字链表存储表示如图7.15所示。所示。有向图的十字链表存储结构用有向图的十字链表存储结构用C语言描述如下：语言描述如下：#defineMAXVERTEX100/*最大最大顶点个数点个数*/typedefstructArcNode/*弧弧结点的点的类型定型定义*/intheadvex,tailvex;/*弧的弧的头顶点和尾点和尾顶点位置点位置*/InfoPtr*info;/*与弧相关的信息与弧相关的信息*/struct*hlink,*tlink;

33、/*指示弧指示弧头和弧尾相同的和弧尾相同的结点点*/ArcNode;typedefstructVertexNode/*顶点点结点的点的类型定型定义*/VertexTypedata;/*用于存用于存储顶点点*/ArcNode*firstin,*firstout;/*分分别指向指向顶点的第一条入弧和出弧点的第一条入弧和出弧*/VertexNode;typedefstruct/*图的的类型定型定义*/VertexNodevertexMAXVERTEX;intvexnum,arcnum;/*图的的顶点数目与弧的数目点数目与弧的数目*/OLGraph;7.2.4 邻接多重链表表示法邻接多重链表邻接多重链

34、表(AdjacencyMulti_list)是无向图的另一是无向图的另一种链式存储结构。之所以提出邻接多重表是因为它能提供种链式存储结构。之所以提出邻接多重表是因为它能提供更为方便的边的信息。更为方便的边的信息。7.3 图 的 遍 历与树类似，图也存在遍历问题。图的遍历是指从图中与树类似，图也存在遍历问题。图的遍历是指从图中某个顶点出发，按照某种方法对图中每个顶点访问且仅访某个顶点出发，按照某种方法对图中每个顶点访问且仅访问一次的操作。图的遍历是求解图的连通性问题、拓扑排问一次的操作。图的遍历是求解图的连通性问题、拓扑排序和关键路径的基础。图的遍历主要有两种方式：深度优序和关键路径的基础。图的

35、遍历主要有两种方式：深度优先搜索和广度优先搜索。先搜索和广度优先搜索。7.3 图 的 遍 历7.3.1 图的深度优先搜索1.图的深度优先搜索的定义图的深度优先搜索图的深度优先搜索(Depth_FirstSearch，DFS)是指是指按照深度方向搜索，它类似于树的先根遍历，是树的先序按照深度方向搜索，它类似于树的先根遍历，是树的先序遍历的推广。图的深度优先搜索的思想是：遍历的推广。图的深度优先搜索的思想是：(1)从图中某个顶点从图中某个顶点v0出发，访问顶点出发，访问顶点v0。(2)访问顶点访问顶点v0的第一个邻接点，然后以该邻接点为的第一个邻接点，然后以该邻接点为新的顶点，访问该顶点的邻接点。

36、重复执行以上操作，直新的顶点，访问该顶点的邻接点。重复执行以上操作，直到当前顶点没有邻接点为止。到当前顶点没有邻接点为止。(3)返回到上一个已经访问过还有未被访问的邻接点返回到上一个已经访问过还有未被访问的邻接点的顶点，按照以上步骤继续访问该顶点的其他未被访问的的顶点，按照以上步骤继续访问该顶点的其他未被访问的邻接点。以此类推，直到图中所有的顶点都被访问过。邻接点。以此类推，直到图中所有的顶点都被访问过。7.3 图 的 遍 历图的深度优先搜索过程如图图的深度优先搜索过程如图7.18所示。其中，访问顶所示。其中，访问顶点的方向用实箭头表示，回溯用虚箭头表示，旁边的数字点的方向用实箭头表示，回溯用

37、虚箭头表示，旁边的数字表示访问或回溯的次序。表示访问或回溯的次序。7.3 图 的 遍 历2.图的深度遍历的算法实现图的深度优先搜素图的深度优先搜素(邻接表实现邻接表实现)的算法描述如下。的算法描述如下。intvisitedMAXVERTEX;/*访问标志数志数组*/voidDFSTraverse(AdjGraphG)/*从第从第1个个顶点起，深度点起，深度优先搜索先搜索图G*/intv;for(v=0;vG.vexnum;v+)visitedv=0;/*访问标访问标志数志数组组初始化初始化为为未被未被访问访问*/for(v=0;v=0;w=NextAdjVertex(G,G.vertexv.d

38、ata,G.vertexw.data)if(!visitedw)DFS(G,w);/*递归调递归调用用DFS访问访问的序号的序号为为w的的邻邻接接顶顶点点*/如果要遍历的图是一个无向连通图或者是一个强连通图，如果要遍历的图是一个无向连通图或者是一个强连通图，则只需要调用一次则只需要调用一次DFS(G,v)就可以搜素整个图，否则需要多次调就可以搜素整个图，否则需要多次调用用DFS(G,v)。7.3 图 的 遍 历以邻接表作为存储结构，查找以邻接表作为存储结构，查找v的第一个邻接点的算法实现的第一个邻接点的算法实现如下。如下。intFirstAdjVertex(AdjGraphG,VertexTy

39、pev)/*返回返回顶点点v的第一个的第一个邻接接顶点的序号点的序号*/ArcNode*p;intv1;v1=LocateVertex(G,v);/*v1为顶点点v在在图G中的序号中的序号*/p=G.vertexv1.firstarc;if(p)/*如果如果顶点点v的第一个的第一个邻接点存在，返回接点存在，返回邻接点的接点的序号，否序号，否则返回返回-1*/returnp-adjvex;elsereturn-1;7.3 图 的 遍 历以邻接表作为存储结构，查找以邻接表作为存储结构，查找v的相对于的相对于w的下一个邻接点的算法实现如下。的下一个邻接点的算法实现如下。intNextAdjVerte

40、x(AdjGraphG,VertexTypev,VertexTypew)/*返回返回v的相的相对于于w的下一个的下一个邻接接顶点的序号点的序号*/ArcNode*p,*next;intv1,w1;v1=LocateVertex(G,v);/*v1为顶点点v在在图G中的序号中的序号*/w1=LocateVertex(G,w);/*w1为顶点点w在在图G中的序号中的序号*/for(next=G.vertexv1.firstarc;next;)if(next-adjvex!=w1)next=next-nextarc;p=next;/*p指向指向顶点点v的的邻接接顶点点w的的结点点*/if(!p|!p

41、-nextarc)/*如果如果w不存在或不存在或w是最后一个是最后一个邻接点，接点，则返回返回-1*/return-1;elsereturnp-nextarc-adjvex;/*返回返回v的相的相对于于w的下一个的下一个邻接点的序号接点的序号*/图的非递归实现深度优先搜素的算法如下。图的非递归实现深度优先搜素的算法如下。7.3 图 的 遍 历7.3.2 图的广度优先搜索1.图的广度优先搜索的定义图的广度优先搜索图的广度优先搜索(Breadth-FirstSearch，BFS)类类似于树的层次遍历，是树的按层次遍历的推广。图的广度似于树的层次遍历，是树的按层次遍历的推广。图的广度优先搜索的思想是

42、：优先搜索的思想是：(1)从图的某个顶点从图的某个顶点v0出发，首先访问顶点出发，首先访问顶点v0。(2)依次访问顶点依次访问顶点v0的未被访问的每一个邻接点。的未被访问的每一个邻接点。(3)分别从这些邻接顶点出发，依次访问它们各个未分别从这些邻接顶点出发，依次访问它们各个未被访问的邻接顶点，并保证先被访问的邻接点的邻接点先被访问的邻接顶点，并保证先被访问的邻接点的邻接点先访问，后被访问的邻接点的邻接点后访问。重复执行步骤访问，后被访问的邻接点的邻接点后访问。重复执行步骤(3)，直到所有顶点都被访问。，直到所有顶点都被访问。图图7.18给出了一个广度优先搜索的过程示意图，其中，给出了一个广度优

43、先搜索的过程示意图，其中，箭头表示搜索方向，箭头旁边的数字表示搜索顺序，箭头表示搜索方向，箭头旁边的数字表示搜索顺序，A为为起始点。起始点。2.图的广度优先搜索的算法实现在图的广度优先的搜索过程中，同样也需要设立一个在图的广度优先的搜索过程中，同样也需要设立一个访问标志数组访问标志数组visitedn，其初值为，其初值为0，如果某个顶点被访，如果某个顶点被访问，则相应的分量置为问，则相应的分量置为1。广度优先搜索的算法描述如下：。广度优先搜索的算法描述如下：(1)首先访问首先访问v0，并置访问标志为，并置访问标志为1，然后将，然后将v0入队入队列。列。(2)如果队列不为空，则重复执行以下步骤：

44、如果队列不为空，则重复执行以下步骤：队头结点队头结点v出队列。出队列。对于对于v的所有邻接顶点的所有邻接顶点w，如果，如果w未被访问，则访问未被访问，则访问w并设置访问标志，然后将并设置访问标志，然后将w入队列。入队列。图的广度的广度优先搜索的算法先搜索的算法实现如下。如下。voidBFSTraverse(AdjGraphG)/*从第从第1个个顶点出点出发，按广度，按广度优先非先非递归搜索搜索图G*/intv,front,rear;ArcNode*p;intqueueMAXVERTEX;/*定定义一个一个队列列Q*/front=rear=-1;/*初始化初始化队列列Q*/for(v=0;vG.

45、vexnum;v+)/*初始化初始化标志位志位*/visitedv=0;v=0;visitedv=1;/*设置置访问标志志为1，表示已，表示已经被被访问过*/Visit(G.vertexv.data);rear=(rear+1)%MAXVERTEX;queuerear=v;while(frontadjvex=0)/*如果如果该顶点未被点未被访问过*/visitedp-adjvex=1;Visit(G.vertexp-adjvex.data);rear=(rear+1)%MAXVERTEX;queuerear=p-adjvex;p=p-nextarc;/*p指向下一个指向下一个邻接点接点*/7.

46、4 图 的 应 用7.4.1 图的连通性问题1.无向图的连通分量在在图的遍的遍历中，中，对于于连通通图，无，无论是广度是广度优先搜索先搜索还是深度是深度优先搜索，只需要先搜索，只需要调用一次搜索用一次搜索过程，即从任何一程，即从任何一个个顶点出点出发，都可以遍，都可以遍历图中的各个中的各个顶点。点。对于非于非连通通图，则需要从多个需要从多个顶点出点出发对图进行遍行遍历，每次从新，每次从新顶点开始点开始遍遍历得到的序列就是得到的序列就是图的各个的各个连通分量的通分量的顶点集合。点集合。7.4 图 的 应 用例如，图例如，图7.3中的非连通图中的非连通图G3的邻接表如图的邻接表如图7.21所示。所

47、示。对图对图G3进行深度优先遍历，因为图进行深度优先遍历，因为图G3是非连通图且有是非连通图且有3个个连通分量，需要调用连通分量，需要调用3次次FirstAdjVertex过程才能完成图的过程才能完成图的深度搜索，得到的序列为深度搜索，得到的序列为A,B,C,D,I,EF,GH7.4 图 的 应 用2.图中两个顶点之间的简单路径在图的应用问题中，常常需要找出从顶点在图的应用问题中，常常需要找出从顶点u到顶点到顶点v的的简单路径。从顶点简单路径。从顶点u到顶点到顶点v可能存在多条简单路径，由于可能存在多条简单路径，由于在遍历过程中，要访问图中的所有顶点，因此，可以在深在遍历过程中，要访问图中的所

48、有顶点，因此，可以在深度度(或广度或广度)优先搜索算法的基础上增加适当的条件，以得优先搜索算法的基础上增加适当的条件，以得到此问题的算法。到此问题的算法。【算法思想】从顶点【算法思想】从顶点u出发，进行深度出发，进行深度(或广度或广度)优先优先搜索，如果能搜索到顶点搜索，如果能搜索到顶点v，则表明从顶点，则表明从顶点u到顶点到顶点v存在存在一条简单路径。因为在搜索过程中，每个顶点访问且仅访一条简单路径。因为在搜索过程中，每个顶点访问且仅访问一次，所以这条路径一定是简单路径。因此，只要在搜问一次，所以这条路径一定是简单路径。因此，只要在搜索过程中，将搜索的路线记录下来，就得到了从顶点索过程中，将

49、搜索的路线记录下来，就得到了从顶点u到顶到顶点点v的一条简单路径。的一条简单路径。intpreMAXVERTEXvoidBriefPath(AdjGraphG,intu,intv)/*求求连通通图G中从中从顶点点u到到顶点点v的一条的一条简单路径路径*/inti;pre=(int*)malloc(G-vexnum*sizeof(int);for(i=0;ivexnum;i+)/*prei=-1表示表示顶点未被点未被访问*/prei=-1;preu=u;/*prei!=-1表示表示顶点点u已已经被被访问*/DFS_Path(G,u,v);/*深度深度优先搜索找出一条从先搜索找出一条从顶点点u到到

50、顶点点v的的简单路径路径*/free(pre);voidDFS_Path(GraphG,intu,intv)/*深度深度优先搜索先搜索图G，找出一条从，找出一条从顶点点u到到顶点点v的的简单路径路径*/intj;for(j=FirstAdjVertex(G,u);j=0;j=NextAdjVertex(G,u,j)if(prej=-1)prej=u;if(j=v)/*当找到当找到顶点点v时，输出出顶点点u到到顶点点v的路径的路径*/PrintPath(pre,v);elseDFS_Path(G,j,v);3.图的生成树与最小生成树对非连通图进行深度对非连通图进行深度(或广度或广度)优先搜索，可