C语言数据结构第06讲课件

1、C语言数据结构第06讲第第7 7章章 图图C语言数据结构第06讲知 识 点图的逻辑结构及基本术语图的逻辑结构及基本术语邻接矩阵和邻接表的存储结构和特点邻接矩阵和邻接表的存储结构和特点深度优先搜索和广度优先搜索两种遍历算法深度优先搜索和广度优先搜索两种遍历算法图的连通性和生成树的概念图的连通性和生成树的概念最短路径的含义及求最短路径的算法最短路径的含义及求最短路径的算法C语言数据结构第06讲难难 点点图的遍历图的遍历 最小生成树最小生成树 最短路径最短路径要要 求求熟练掌握以下内容：熟练掌握以下内容： 图的存储结构图的存储结构 图的遍历算法图的遍历算法了解以下内容：了解以下内容： 图的最小生成树

2、和求最小生成树算法图的最小生成树和求最小生成树算法 带权有向图的最短路径问题带权有向图的最短路径问题C语言数据结构第06讲7-1 7-1 图的定义和术语图的定义和术语7-2 7-2 图的存储表示图的存储表示7-3 7-3 图的遍历图的遍历7-4 7-4 图的连通性图的连通性7-5 7-5 最短路径最短路径小小 结结实验实验7 7 图子系统图子系统习题习题7 7C语言数据结构第06讲 图（图（GraphGraph）是一种比树形结构更复杂的非线性结构。在）是一种比树形结构更复杂的非线性结构。在图形结构中，每个结点都可以有多个直接前驱和多个直接后图形结构中，每个结点都可以有多个直接前驱和多个直接后继

3、。继。7-1 7-1 图的定义和术语图的定义和术语7-1-1 7-1-1 图的定义图的定义 图（图（GraphGraph）是由非空的顶点（）是由非空的顶点（VerticesVertices）集合和一个描）集合和一个描述顶点之间关系述顶点之间关系边（边（EdgesEdges）的有限集合组成的一种数据）的有限集合组成的一种数据结构。可以用二元组定义为：结构。可以用二元组定义为： G G（V V，E E） 其中，其中，G G表示一个图，表示一个图，V V是图是图G G中顶点的集合，中顶点的集合，E E是图是图G G中边中边的集合。的集合。C语言数据结构第06讲 图图7-1 无向图无向图G1 图图7-

4、2 有向图有向图G G2 2 V1V3V2V4V5V1V3V2V4 G1=（V，E） Vv1,v2,v3,v4,v5； E(v1,v2),(v1,v4),(v2,v3),(v3,v4), (v3,v5),(v2,v5)。(v(vi i,v,vj j) )表示顶点表示顶点v vi i和顶点和顶点v vj j之间有一之间有一条无向直接连线，也称为边。条无向直接连线，也称为边。G2=(V,E)V=v1,v2,v3,v4E=, 表示顶点表示顶点vi和顶点和顶点vj之间有一条之间有一条有向直接连线，也称为弧。其中有向直接连线，也称为弧。其中vi称称为弧尾，为弧尾，vj称为弧头。称为弧头。C语言数据结构第

5、06讲7-1-2 7-1-2 图的相关术语图的相关术语（1 1）无向图（）无向图（UndigraphUndigraph） 在一个图中，如果每条边都没有方向（如图在一个图中，如果每条边都没有方向（如图7-17-1），），则称该图为无向图。则称该图为无向图。（2 2）有向图（）有向图（DigraphDigraph） 在一个图中，如果每条边都有方向（如图在一个图中，如果每条边都有方向（如图7-27-2），则），则称该图为有向图。称该图为有向图。（3 3）无向完全图）无向完全图 在一个无向图中，如果任意两顶点都有一条直接边相在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。可以

6、证明，在一个含有连接，则称该图为无向完全图。可以证明，在一个含有n n个顶点的无向完全图中，有个顶点的无向完全图中，有n (n-1)/2n (n-1)/2条边。条边。 C语言数据结构第06讲（4 4）有向完全图）有向完全图 在一个有向图中，如果任意两顶点之间都有方向互为在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。在一个含相反的两条弧相连接，则称该图为有向完全图。在一个含有有n n个顶点的有向完全图中，有个顶点的有向完全图中，有n (n-1) n (n-1) 条弧。条弧。（5 5）稠密图、稀疏图）稠密图、稀疏图 我们称边数很多的图为稠密图；称边数很少的

7、图为稀我们称边数很多的图为稠密图；称边数很少的图为稀疏图。疏图。（6 6）顶点的度）顶点的度 在无在无向向图中：一个顶点拥有的边数，称为该顶点的度。图中：一个顶点拥有的边数，称为该顶点的度。记为记为TD (v)TD (v)。C语言数据结构第06讲 在有向图中：在有向图中： (a) 一个顶点拥有的弧头的数目，称为该顶点的入度，一个顶点拥有的弧头的数目，称为该顶点的入度， 记为记为ID (v)； (b) 一个顶点拥有的弧尾的数目，称为该顶点的出度，一个顶点拥有的弧尾的数目，称为该顶点的出度， 记为记为OD (v)； (c) 一个顶点度等于顶点的入度一个顶点度等于顶点的入度+出度，出度， 即：即：T

8、D (v)=ID (v)OD (v)。 在图在图7-1的的G1中有：中有： TD(v1)=2 TD(v2)=3 TD(v3)=3 TD(v4)=2 TD(v5)=2 在图在图7-2的的G2中有：中有： ID(v1)=1 OD(v1)=2 TD(v1)=3 ID(v2)=1 OD(v2)=0 TD(v2)=1 ID(v3)=1 OD(v3)=1 TD(v3)=2 ID(v4)=1 OD(v4)=1 TD(v4)=2C语言数据结构第06讲 可以证明，对于具有可以证明，对于具有n n个顶点、个顶点、e e条边的图，顶点条边的图，顶点v vi i的的度度TD (vTD (vi i) )与顶点的个数以及

9、边的数目满足关系：与顶点的个数以及边的数目满足关系：（7 7）权）权 图的边或弧有时具有与它有关的数据信息，这个数据图的边或弧有时具有与它有关的数据信息，这个数据信息就称为权（信息就称为权（WeightWeight）。）。21niViTDeACBD58697（8 8）网）网边（或弧）上带权边（或弧）上带权的图称为网（的图称为网（NetworkNetwork）。）。 如图如图7-37-3所示，就是一个无所示，就是一个无向网。如果边是有方向的带权向网。如果边是有方向的带权图，则就是一个有向网。图，则就是一个有向网。图图7-3 一个无向网示意一个无向网示意图图7-3 一个无向网示意一个无向网示意C语

10、言数据结构第06讲（9 9）路径、路径长度）路径、路径长度 顶点顶点v vi i到顶点到顶点v vj j之间的路径是指顶点序列之间的路径是指顶点序列v vi i,v,vi1i1,v,vi2i2, , , v , vimim,v,vj.j.。其中，（。其中，（v vi i,v,vi1i1），），(v(vi1i1,v,vi2i2) )，,(v(vimim,.v,.vj j) )分别为图中的边。路径上边的数目称为路径长度。分别为图中的边。路径上边的数目称为路径长度。 在图在图7-17-1的无向图的无向图G1G1中，中，v v1 1vv4 4vv3 3vv5 5与与v v1 1vv2 2vv5 5是是

11、从顶点从顶点v v1 1 到顶点到顶点v v5 5 的两条路径，路径长度分别为的两条路径，路径长度分别为3 3和和2 2。（1010）回路、简单路径、简单回路）回路、简单路径、简单回路 在一条路径中，如果其起始点和终止点是同一顶点，则在一条路径中，如果其起始点和终止点是同一顶点，则称其为回路或者环。如果一条路径上所有顶点除起始点和终称其为回路或者环。如果一条路径上所有顶点除起始点和终止点外彼此都是不同的，则称该路径为简单路径。止点外彼此都是不同的，则称该路径为简单路径。 在图在图7-17-1中，前面提到的中，前面提到的v v1 1到到v v5 5的两条路径都为简单路的两条路径都为简单路径。除起

12、始点和终止点外，其他顶点不重复出现的回路称为径。除起始点和终止点外，其他顶点不重复出现的回路称为简单回路，或者简单环。如图简单回路，或者简单环。如图7-27-2中的中的v v1 1vv3 3vv4 4vv1 1。C语言数据结构第06讲（1111）子图）子图 对于图对于图G=G=（V V，E E），），G=G=（VV，EE），若存在），若存在VV是是V V的子集的子集 ，EE是是E E的子集的子集 ，则称图，则称图GG是是G G的一个子图。的一个子图。 图图7-47-4示出了示出了G G1 1和和G G2 2的子图。的子图。 图图7-4 图图G1和和G2的两个子图示意的两个子图示意 (a) G1

13、的子图的子图 (b) G2的子图的子图 V1V3V2V1V3V2V4V5V1V3V2V4V5 图图7-1 无向图无向图G1C语言数据结构第06讲（1212）连通图、连通分量）连通图、连通分量 在无向图中，如果从一个顶点在无向图中，如果从一个顶点v vi i到另一个顶点到另一个顶点v vj j(ij)(ij)有路径，则称顶点有路径，则称顶点v vi i和和v vj j是连通的。任意两顶点都是连通的是连通的。任意两顶点都是连通的图称为连通图。无向图的极大连通子图称为连通分量。图图称为连通图。无向图的极大连通子图称为连通分量。图7-5 (a)7-5 (a)中有两个连通分量，如图中有两个连通分量，如图

14、7-5 (b)7-5 (b)所示。所示。AEBFCDAEBFCD (a) 无向图无向图G3 (b) G3的两个连通分量的两个连通分量 图图7-5 无向图及连通分量示意无向图及连通分量示意C语言数据结构第06讲（13）强连通图、强连通分量）强连通图、强连通分量 对于有向图来说，若图中任意一对对于有向图来说，若图中任意一对顶点顶点vi 和和vj(ij)均有从一个顶点均有从一个顶点vi到另一到另一个顶点个顶点vj有路径，也有从有路径，也有从vj到到vi的路径，的路径，则称该有向图是强连通图。有向图的极则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量。大强连通子图称为强连通分量。 图图7-

15、2中有两个强连通分量，分别是中有两个强连通分量，分别是v1,v2,v3和和v4，如图，如图7-6所示。所示。（14）生成树）生成树 连通图连通图G的一个子图如果是一棵包含的一个子图如果是一棵包含G的所有顶点的树，的所有顶点的树，则该子图称为则该子图称为G的生成树（的生成树（Spanning Tree）。在生成树中添）。在生成树中添加任意一条属于原图中的边必定会产生回路，因为新添加的加任意一条属于原图中的边必定会产生回路，因为新添加的边使其所依附的两个顶点之间有了第二条路径。若生成树中边使其所依附的两个顶点之间有了第二条路径。若生成树中减少任意一条边，则必然成为非连通的。减少任意一条边，则必然成

16、为非连通的。n个顶点的生成树具个顶点的生成树具有有n-1条边。条边。V1V3V2V4图图7-6 有向图有向图G2的两个的两个 强连通分量示意强连通分量示意C语言数据结构第06讲7-1-3 图的基本操作图的基本操作 图的基本操作有：图的基本操作有：（1）CreatGraph（G）输入图）输入图G的顶点和边，建立图的顶点和边，建立图G的存储。的存储。（2）DFSTraverse（G，v）在图）在图G中，从顶点中，从顶点v出发深度出发深度优先遍历图优先遍历图G。（3）BFSTtaverse（G，v）在图）在图G中，从顶点中，从顶点v出发广度出发广度优先遍历图优先遍历图G。 图的存储结构比较多。对于图

17、的存储结构的选择取决图的存储结构比较多。对于图的存储结构的选择取决于具体的应用和需要进行的运算。于具体的应用和需要进行的运算。 下面介绍几种常用的图的存储结构。下面介绍几种常用的图的存储结构。C语言数据结构第06讲 邻接矩阵是表示顶点之间相邻关系的矩阵。邻接矩阵是表示顶点之间相邻关系的矩阵。 假设图假设图G（V，E）有）有n个顶点，即个顶点，即Vv0,v1,vn-1，则，则G的邻接矩阵是具有如下性质的的邻接矩阵是具有如下性质的n阶方阵：阶方阵： 1 若若(vi,vj)或或是是E(G)中的边中的边 Aij= 0 若若(vi,vj)或或不是不是E(G)中的边中的边 若若G是网，则邻接矩阵可定义为：

18、是网，则邻接矩阵可定义为： wij 若若(vi,vj)或或是是E(G)中的边中的边 Aij= 0或或 若若(vi,vj)或或不是不是E(G)中的边中的边 其中，其中，wij表示边表示边(vi,vj)或或上的权值（如图上的权值（如图7-3）；）；表示一个计算机允许的、大于所有边上权值的数。表示一个计算机允许的、大于所有边上权值的数。C语言数据结构第06讲 用邻接矩阵表示法如图用邻接矩阵表示法如图7-77-7所示；用邻接矩阵表示法所示；用邻接矩阵表示法如图如图7-87-8所示。所示。C语言数据结构第06讲 图的邻接矩阵具有以下性质：图的邻接矩阵具有以下性质：（1 1）无向图的邻接矩阵一定是一个对称

19、矩阵。因此，在具体）无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。（2 2）对于无向图，邻接矩阵的第）对于无向图，邻接矩阵的第i i行（或第行（或第i i列）非零元素列）非零元素（或非（或非元素）的个数正好是第元素）的个数正好是第i i个顶点的度个顶点的度TD(vTD(vi i) )。（3 3）对于有向图，邻接矩阵的第）对于有向图，邻接矩阵的第i i行（或第行（或第i i列）非零元素列）非零元素（或非（或非元素）的个数正好是第元素）的个数正好是第i i个顶点的出度个顶点的出度OD(vOD(

20、vi i) )（或入（或入度度ID(vID(vi i) )）。）。（4 4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。这是用邻接矩阵存储图的局限性。C语言数据结构第06讲 图的邻接矩阵存储的描述如下：图的邻接矩阵存储的描述如下：#define MAXLEN 10typedef struct char ve

21、xsMAXLEN; int edgesMAXLENMAXLEN; int n,e; MGraph; C语言数据结构第06讲 建立一个图的邻接矩阵存储的算法如下：建立一个图的邻接矩阵存储的算法如下：void CreateMGraph(MGraph *G) int i,j,k; char ch1,ch2; printf(请输入顶点数和边数请输入顶点数和边数(输入格式为输入格式为:顶点数顶点数,边数边数):n); scanf(%d,%d,&(G-n),&(G-e); printf(请输入顶点信息请输入顶点信息(顶点号顶点号)每个顶点以回车作为结束每个顶点以回车作为结束:n); for

22、(i=0;in;i+) getchar(); scanf (%c,&(G-vexsi); for(i=0;in;i+) for(j=0;jn;j+) G-edgesij=0;C语言数据结构第06讲printf (请输入每条边对应的两个顶点的序号请输入每条边对应的两个顶点的序号(输入格式为输入格式为:i,j):n); for(k=0;ke;k+) getchar(); printf (请输入第请输入第%d条边的顶点序号：条边的顶点序号：,k+1); scanf (%c,%c,&ch1,&ch2); for (i=0;ch1!=G-vexsi;i+); for (j=0;c

23、h2!=G-vexsj;j+);G-edgesij=1; C语言数据结构第06讲7-2-2 7-2-2 邻接表邻接表 邻接表邻接表(Adjacency List)是图的一种顺序存储与链式存是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图示法。就是对于图G中的每个顶点中的每个顶点vi，该方法将所有邻接，该方法将所有邻接于于vi的顶点的顶点vj链成一个单链表，这个单链表就称为顶点链成一个单链表，这个单链表就称为顶点vi的邻接表。再将所有点的邻接表表头放到数组中，就构成的邻接表。再将所有点的邻接表表头放到数

24、组中，就构成了图的邻接表。了图的邻接表。 在邻接表表示中有两种结点结构，如图在邻接表表示中有两种结点结构，如图7-9所示。所示。 顶点域顶点域 边表头指针边表头指针 邻接点域邻接点域 指针域指针域 顶点表顶点表 边表边表 图图7-9 邻接矩阵表示的结点结构邻接矩阵表示的结点结构vertexfirstedgeadjvexnextC语言数据结构第06讲 一种是顶点表的结点结构，它由顶点域（一种是顶点表的结点结构，它由顶点域（vertex）和）和指向第一条邻接边的指针域（指向第一条邻接边的指针域（firstedge）构成，另一种是）构成，另一种是边表结点，它由邻接点域边表结点，它由邻接点域(adjv

25、ex)和指向下一条邻接边的和指向下一条邻接边的指针域指针域(next)构成。对于网的边表需再增设一个存储边上构成。对于网的边表需再增设一个存储边上信息（如权值等）的域（信息（如权值等）的域（info），网的边表结构如图），网的边表结构如图7-10所示。所示。 邻接点域邻接点域 边上信息边上信息 指针域指针域 图图7-10 网的边表结构网的边表结构adjvex infonextC语言数据结构第06讲 图图7-11给出无向图给出无向图7-7对应的邻接表表示。对应的邻接表表示。 邻接表表示形式描述如下：邻接表表示形式描述如下：C语言数据结构第06讲define MAXLEN 10 / 最大顶点数为最

26、大顶点数为10typedef struct node / 边表结点边表结点 int adjvex; / 邻接点域邻接点域 struct node * next; / 指向下一个邻接点的指针域指向下一个邻接点的指针域 /若要表示边上信息，则应增加一个数据域若要表示边上信息，则应增加一个数据域info EdgeNode; typedef struct vnode / 顶点表结点顶点表结点 VertexType vertex; / 顶点域顶点域 EdgeNode * firstedge; / 边表头指针边表头指针 VertexNode; typedef VertexNode AdjListMAXLE

27、N; / AdjList是邻接表类型是邻接表类型typedef struct AdjList adjlist; / 接表接表 int n,e; / 顶点数和边数顶点数和边数 ALGraph; / ALGraph是以邻接表方式存储的图类型是以邻接表方式存储的图类型C语言数据结构第06讲 建立一个有向图的邻接表存储的算法如下：建立一个有向图的邻接表存储的算法如下： void CreateGraphAL (ALGraph *G) int i,j,k; EdgeNode * s; printf(“请输入顶点数和边数请输入顶点数和边数(输入格式为输入格式为:顶点数顶点数,边数边数) ：n); scanf

28、(%d,%d,&(G-n),&(G-e); / 读入顶点数和边数读入顶点数和边数 printf(请输入顶点请输入顶点(格式为格式为:顶点号顶点号)以回车作为结束以回车作为结束:n); for (i=0;in;i+) / 立有立有n个顶点的顶点表个顶点的顶点表 scanf(n%c,&(G-adjlisti.vertex); / 读入顶点信息读入顶点信息 G-adjlisti.firstedge=NULL; / 点的边表头指针设为空点的边表头指针设为空 printf(请输入边的信息请输入边的信息(输入格式为输入格式为:i,j)：n); for (k=0;ke;k+) / 建

29、立边表建立边表 scanf(“n%d,%d”,&i,&j); / 读入边读入边的顶点对应序号的顶点对应序号 s=new EdgeNode; / 生成新边表结点生成新边表结点s s-adjvex=j; / 邻接点序号为邻接点序号为j s-next=G-adjlisti.firstedge; / 新边表插入到顶点边表头部新边表插入到顶点边表头部 G-adjlisti.firstedge=s; C语言数据结构第06讲 若无向图中有若无向图中有n 个顶点、个顶点、e条边，则它的邻接表需条边，则它的邻接表需n个头个头结点和结点和2e个表结点。显然，在边稀疏个表结点。显然，在边稀疏(en(

30、n-1)/2)的情况下，的情况下，用邻接表表示图比邻接矩阵节省存储空间，当和边相关的信用邻接表表示图比邻接矩阵节省存储空间，当和边相关的信息较多时更是如此。息较多时更是如此。 在无向图的邻接表中，顶点在无向图的邻接表中，顶点vi的度恰为第的度恰为第i个链表中的结个链表中的结点数；但在有向图中，第点数；但在有向图中，第i个链表中的结点个数只是顶点个链表中的结点个数只是顶点vi的的出度。如果要求入度，则必须遍历整个邻接表才能得到结果。出度。如果要求入度，则必须遍历整个邻接表才能得到结果。有时，为了便于确定顶点的入度或以顶点有时，为了便于确定顶点的入度或以顶点vi为头的弧，可以为头的弧，可以建立一个

31、有向图的逆邻接表，即对每个顶点建立一个有向图的逆邻接表，即对每个顶点vi 建立一个链接，建立一个链接，以以vi为弧头的弧的链表。例如图为弧头的弧的链表。例如图7-12所示为有向图所示为有向图G2（图（图7-2）的邻接表和逆邻接表。）的邻接表和逆邻接表。C语言数据结构第06讲 在建立邻接表或逆邻接表时，若输入的顶点信息即为在建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则建立邻接表的复杂度为顶点的编号，则建立邻接表的复杂度为O（n+e），否则，），否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为需要通过查找才能得到顶点在图中位置，则时间复杂度为O（n*e）。）。 C语言数据结构

32、第06讲 图的遍历（图的遍历（traversing graph）是指从图中的某一顶点出）是指从图中的某一顶点出发，对图中的所有顶点访问一次，而且仅访问一次。图的遍发，对图中的所有顶点访问一次，而且仅访问一次。图的遍历是图的一种基本操作。由于图结构本身的复杂性，所以图历是图的一种基本操作。由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面：的遍历操作也较复杂，主要表现在以下四个方面：（1）在图结构中，每一个结点的地位都是相同的，没有一）在图结构中，每一个结点的地位都是相同的，没有一个个“自然自然”的首结点，图中任意一个顶点都可作为访问的起的首结点，图中任意一个顶点都可作为访

33、问的起始结点。始结点。（2）在非连通图中，从一个顶点出发，只能够访问它所在）在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何访问图中其的连通分量上的所有顶点，因此，还需考虑如何访问图中其余的连通分量。余的连通分量。（3）在图结构中，如果有回路存在，那么一个顶点被访问）在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。之后，有可能沿回路又回到该顶点。（4）在图中，一个顶点可以和其它多个顶点相连，当这个）在图中，一个顶点可以和其它多个顶点相连，当这个顶点访问过后，就要考虑如何选取下一个要访问的顶点。顶点访问过后，就要考虑如何选取下

34、一个要访问的顶点。C语言数据结构第06讲7-3-1 深度优先搜索深度优先搜索 深度优先搜索（深度优先搜索（Depth-Fisrst Search）遍历类似于树的先）遍历类似于树的先根遍历，是树的先根遍历的推广。根遍历，是树的先根遍历的推广。 假设初始状态是图中所有顶点未曾被访问，则深度优先假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点发搜索可从图中某个顶点发v出发，首先访问此顶点，然后任出发，首先访问此顶点，然后任选一个选一个v的未被访问的邻接点的未被访问的邻接点w出发，继续进行深度优先搜出发，继续进行深度优先搜索，直到图中所有和索，直到图中所有和v路径相通的顶点都被访问

35、到；若此时路径相通的顶点都被访问到；若此时图中还有顶点未被访问到，则另选一个未被访问的顶点作为图中还有顶点未被访问到，则另选一个未被访问的顶点作为起始点，重复上面的做法，直至图中所有的顶点都被访问。起始点，重复上面的做法，直至图中所有的顶点都被访问。V1V5V2V4V8V3V6V7图图7-13 无向图无向图G5 以图以图7-13的无向图的无向图G5为例，为例，其深度优先搜索得到的顶点访问其深度优先搜索得到的顶点访问序列为：序列为： v1 v2 v4 v8 v5 v3 v6 、 v7C语言数据结构第06讲 显然，以上方法是一个递归的过程。为了在遍历过程中显然，以上方法是一个递归的过程。为了在遍历

36、过程中便于区分顶点是否已被访问，需附设访问标志数组便于区分顶点是否已被访问，需附设访问标志数组visited0:n-1, ，其初值为，其初值为FALSE ，一旦某个顶点被访问，一旦某个顶点被访问，则其相应的分量置为则其相应的分量置为TRUE。 从图的某一点从图的某一点v出发，递归地进行深度优先遍历的过程如出发，递归地进行深度优先遍历的过程如下面算法所示。下面算法所示。 void DFSTraverseM(MGraph *G) int i; for(i=0;in;i+) visitedi=FALSE; / FALSE在在c语言中定义为语言中定义为0，以下同，以下同 for(i=0;in;i+)

37、if (!visitedi) DFSM(G,i); C语言数据结构第06讲void DFSM(MGraph *G,int i) int j; printf (tt深度优先遍历结点深度优先遍历结点: 结点结点%cn,G-vexsi); visitedi=TRUE; / TRUE在在c语言中定义为语言中定义为1，以下同，以下同 for (j=0;jn;j+) if (G-edgesij=1&!visitedj)DFSM(G,j); 在遍历时，对图中每个顶点至多调用一次在遍历时，对图中每个顶点至多调用一次DFSM 函数，函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行因为一旦某个顶

38、点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间为接点所需时间为O(n2) ，其中，其中n为图中顶点数。为图中顶点数。C语言数据结构第06讲 当以邻接表作图的存储结构时，找邻接点所需时间为当以邻接表作图的存储结构时，找邻接点所需时间为O(e)，其中，其中e为无向图中边的数或有向图中弧的

39、数。由此，为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为度为O(n+e) 。 7-3-2广度优先搜索广度优先搜索 广度优先搜索广度优先搜索 遍历类似于树的按层次遍历。遍历类似于树的按层次遍历。 假设从图中某顶点假设从图中某顶点v出发，在访问了出发，在访问了v之后依次访问之后依次访问v的各的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使问它们的邻接点，并使“先被访问的顶点的邻接点先被访问的顶点的邻接点”先于先于“后被

40、访问的顶点的邻接点后被访问的顶点的邻接点”被访问，直至图中所有已被访被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程中以优先搜索遍历图的过程中以v为起始点，由近至远，依次访为起始点，由近至远，依次访问和问和v有路径相通且路径长度为有路径相通且路径长度为1,2,的顶点。的顶点。C语言数据结构

41、第06讲 对图对图7-13无向图无向图G5 进行广度优先进行广度优先搜索遍历，首先访问搜索遍历，首先访问v1 和和v1的邻接点的邻接点v2和和v3，然后依次访问，然后依次访问v2 的邻接点的邻接点v4 和和v5 及及v3 的邻接点的邻接点v6和和v7，最后访问，最后访问v4 的邻接点的邻接点v8。由于这些顶点的邻接。由于这些顶点的邻接点均已被访问，并且图中所有顶点都点均已被访问，并且图中所有顶点都被访问，由些完成了图的遍历。得到被访问，由些完成了图的遍历。得到的顶点访问序列为：的顶点访问序列为： v1v2 v3 v4 v5 v6 v7 v8 和深度优先搜索类似，在遍历的过程中也需要一个访和深度

42、优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺次访问路径长度为问标志数组。并且，为了顺次访问路径长度为2、3、的的顶点，需附设队列以存储已被访问的路径长度为顶点，需附设队列以存储已被访问的路径长度为1、2、 的顶点。的顶点。V1V5V2V4V8V3V6V7图图7-13 无向图无向图G5 C语言数据结构第06讲 从图的某一点从图的某一点v出发，递归地进行广度优先遍历的过程如出发，递归地进行广度优先遍历的过程如下面的算法所示。下面的算法所示。 void BFSTraverseM(MGraph *G) int i; for (i=0;in;i+) visitedi=FALSE; f

43、or (i=0;in;i+) if (!visitedi) BFSM(G,i);C语言数据结构第06讲 void BFSM(MGraph *G,int k)int i,j; CirQueue Q; InitQueue(&Q); printf (广度优先遍历结点广度优先遍历结点: 结点结点%cn,G-vexsk); visitedk=TRUE; EnQueue(&Q,k); while (!QueueEmpty(&Q) i=DeQueue(&Q); for (j=0;jn;j+) if (G-edgesij=1&!visitedj) printf (广度优

44、先遍历结点广度优先遍历结点:%cn,G-vexsj); visitedj=TRUE; EnQueue(&Q,j); C语言数据结构第06讲 分析上述算法，每个顶点至多进一次队列。遍历图的分析上述算法，每个顶点至多进一次队列。遍历图的过程实质是通过边或弧找邻接点的过程，因此广度优先搜过程实质是通过边或弧找邻接点的过程，因此广度优先搜索遍历图和深度优先搜索遍历的时间复杂度是相同的，两索遍历图和深度优先搜索遍历的时间复杂度是相同的，两者不同之处仅仅在于对顶点访问的顺序不同。者不同之处仅仅在于对顶点访问的顺序不同。 判定一个图的连通性是图的一个应用问题，我们可以判定一个图的连通性是图的一个应用

45、问题，我们可以利用图的遍历算法来求解这一问题。本节将讨论无向图利用图的遍历算法来求解这一问题。本节将讨论无向图的连通性问题，并讨论最小代价生成树等问题。的连通性问题，并讨论最小代价生成树等问题。C语言数据结构第06讲7-4-1 7-4-1 无向图的连通分量和生成树无向图的连通分量和生成树 在对无向图进行遍历时，对于连通图，仅需从图中任在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点。对非连通图，则需从多个顶点出发进问到图中所有顶点。对非连通图，则需从多个顶点出发进行搜索，而每一次从

46、一个新的起始点出发进行搜索过程中行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。得到的顶点访问序列恰为其各个连通分量中的顶点集。 例如，图例如，图7-14 (a)是一个非连通图是一个非连通图G6，按照图，按照图7-14 (b) 所示所示G3 的邻接表进行深度优先搜索遍历的邻接表进行深度优先搜索遍历AEBFCD 图图7-14(a) 非连通图非连通图 图图7-14(b) G6的邻接表的邻接表C语言数据结构第06讲 两次调用两次调用DFS过程（即分别从顶点过程（即分别从顶点A 和和D出发），得到出发），得到的顶点访问序列为：的顶点访问序列为： A B

47、 F E C E 这两个顶点集分别加上所有依附于这些顶点的边，便这两个顶点集分别加上所有依附于这些顶点的边，便构成了非连通图构成了非连通图G3的两个连通分量。的两个连通分量。 因此，要想判定一个无向图是否为连通图，或有几个连因此，要想判定一个无向图是否为连通图，或有几个连通分量，就可设一个计数变量通分量，就可设一个计数变量count，初始时取值为，初始时取值为0，在，在深度优先搜索算法循环中，每调用一次深度优先搜索算法循环中，每调用一次DFS，就给，就给count增增1。这样，当整个算法结束时，依据。这样，当整个算法结束时，依据count 的值，就可确定的值，就可确定图的连通性了。图的连通性了

48、。 设设E(G)E(G)为连通图为连通图G G中所有边的集合，则从图中任一顶点中所有边的集合，则从图中任一顶点出发遍历图时，必定将出发遍历图时，必定将E(G)E(G)分成两个集合分成两个集合T(G)T(G)和和B(G)B(G)，其，其中中T(G)T(G)是遍历图过程中历经的边的集合；是遍历图过程中历经的边的集合；B(G)B(G)是剩余的边是剩余的边的集合。显然，的集合。显然，T(G)T(G)和图和图G G中所有顶点一起构成连通图中所有顶点一起构成连通图G G的的极小连通子图。极小连通子图。C语言数据结构第06讲 按照按照7-1-27-1-2节的定义，它是连通图的一棵生成树，并且由节的定义，它是

49、连通图的一棵生成树，并且由深度优先搜索得到的为深度优先生成树；由广度优先搜索得深度优先搜索得到的为深度优先生成树；由广度优先搜索得到的为广度优先生成树。例如，图到的为广度优先生成树。例如，图7-15(a)7-15(a)和和(b)(b)所示分别为所示分别为图图7-137-13连通图连通图G5G5的深度优先生成树和广度优先生成树。图中的深度优先生成树和广度优先生成树。图中虚线为集合虚线为集合B(G) B(G) 中的边，实线为集合中的边，实线为集合T(G)T(G)中的边。中的边。图图7-15(a) G5的深度优先生成树的深度优先生成树图图7-15(b) G5的广度优先生成树的广度优先生成树V1V5V

50、2V4V8V3V6V7V1V5V2V4V8V3V6V7C语言数据结构第06讲 对于非连通图，通过这样的遍历，将得到的是生对于非连通图，通过这样的遍历，将得到的是生成森林。例如，图成森林。例如，图7-16 (b) 7-16 (b) 所示为图所示为图7-16 (a)7-16 (a)的深的深度优先生成森林，它由三棵深度优先生成树组成。度优先生成森林，它由三棵深度优先生成树组成。图图7-16(a) 非连通无向图非连通无向图G7图图7-16(b) G7的深度优先生成树林的深度优先生成树林JHKLMAICFGBDEJHKLMAICFGBDEC语言数据结构第06讲7-4-2 7-4-2 最小生成树最小生成树

51、1 1最小生成树的基本概念最小生成树的基本概念 由生成树的定义可知，无向连通图的生成树不一定由生成树的定义可知，无向连通图的生成树不一定是唯一的。连通图的一次遍历所经过的边的集合及图中是唯一的。连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。图的不同遍历，就可能得到不同的生成树。图7-17 (a)、(b)和和(c)所示的均为图所示的均为图7-13的无向连通图的无向连通图G5的生成树。的生成树。V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7V1V5V2V4V

52、8V3V6V7 图图7-17 7-17 无向连通图无向连通图G5G5的三棵生成树的三棵生成树（a）（b）（c）C语言数据结构第06讲 可以证明，对于有可以证明，对于有n个顶点的无向连通图，无论其生成个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有树的形态如何，所有生成树中都有且仅有n-1条边。条边。 如果无向连通图是一个网，那么，它的所有生成树中必如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值之和为最小的生成树，简称为最小生成树。有一棵边的权值之和为最小的生成树，简称为最小生成树。 最小生成树的概念可以应用到许多实际问题中。例如有最小生成树的概念可以应用到许多

53、实际问题中。例如有这样一个问题：以尽可能抵的总造价建造城市间的通讯网络，这样一个问题：以尽可能抵的总造价建造城市间的通讯网络，把十个城市联系在一起。在这十个城市中，任意两个城市之把十个城市联系在一起。在这十个城市中，任意两个城市之间都可以建造通讯线路，通讯线路的造价依据城市间的距离间都可以建造通讯线路，通讯线路的造价依据城市间的距离不同而有不同的造价，可以构造一个通讯线路造价网络，在不同而有不同的造价，可以构造一个通讯线路造价网络，在网络中，每个顶点表示城市，顶点之间的边表示城市之间可网络中，每个顶点表示城市，顶点之间的边表示城市之间可构造通讯线路，每条边的权值表示该条通讯线路的造价，要构造通

54、讯线路，每条边的权值表示该条通讯线路的造价，要想使总的造价最低，实际上就是寻找该网络的最小生成树。想使总的造价最低，实际上就是寻找该网络的最小生成树。C语言数据结构第06讲2常用的构造最小生成树的方法常用的构造最小生成树的方法（1 1）构造最小生成树的）构造最小生成树的PrimPrim算法算法 假设假设G（V，E）为一连通网，顶点集）为一连通网，顶点集V=v1，v2，vn，E为网中所有带权边的集合。设置两个新的集合为网中所有带权边的集合。设置两个新的集合U和和T，其中集合其中集合U用于存放用于存放G的最小生成树中的顶点，集合的最小生成树中的顶点，集合T存放存放G的最小生成树中的边。令集合的最小

55、生成树中的边。令集合U的初值为的初值为Uv1（假设构造（假设构造最小生成树时，从顶点最小生成树时，从顶点v1出发），集合出发），集合T的初值为的初值为T。 Prim算法的基本思想：从所有算法的基本思想：从所有uU，vVU的边中，的边中，选取具有最小权值的边（选取具有最小权值的边（u，v），将顶点），将顶点v加入集合加入集合U中，将中，将边（边（u，v）加入集合）加入集合T中，如此不断重复，直到中，如此不断重复，直到UV时，最时，最小生成树构造完毕，这时集合小生成树构造完毕，这时集合T中包含了最小生成树的所有中包含了最小生成树的所有边。边。 图图7-18 (a)所示的一个网，按照所示的一个网，按

56、照Prim方法，从顶点方法，从顶点A出发，出发，该网的最小生成树的产生过程如图该网的最小生成树的产生过程如图7-18 (b)、(c)、(d)、(e)、(f)所示。所示。C语言数据结构第06讲图图7-18 Prim 算法构造最小生成树的过程示意图算法构造最小生成树的过程示意图 AEBFCDAEBFCDAEBFCDAEBFCDAEBFCDAEBFCD(a)(b)(c)(d)(e)(f)6812141617515666668888812121214145C语言数据结构第06讲（2 2）构造最小生成树的）构造最小生成树的KruskalKruskal算法算法 KruskalKruskal算法是一种按照网

57、中边的权值递增的算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。其基本思想是：首先顺序构造最小生成树的方法。其基本思想是：首先选取全部的选取全部的n n个顶点，将其看成个顶点，将其看成n n个连通分量；然后个连通分量；然后按照网中边的权值由小到大的顺序，不断选取当前按照网中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边。依据生成树的概未被选取的边集中权值最小的边。依据生成树的概念，念，n n个结点的生成树，有个结点的生成树，有n-1n-1条边，故反复上述过条边，故反复上述过程，直到选取了程，直到选取了n-1n-1条边为止，就构成了一棵最小条边为止，就构成了一棵最小生

58、成树。生成树。C语言数据结构第06讲图图7-19 Kruskal 算法构造最小生成树的过程示意图算法构造最小生成树的过程示意图 AEBFCDAEBFCDAEBFCDAEBFCDAEBFCDAEBFCD(a)(b)(c)(d)(e)(f)68121416175155666688885121255145返 回C语言数据结构第06讲 最短路径问题是图的又一个比较典型的应用问题。例如，最短路径问题是图的又一个比较典型的应用问题。例如，某一地区的一个交通网，给定了该网内的某一地区的一个交通网，给定了该网内的n个城市以及这些城个城市以及这些城市之间的相通公路的距离，问题是如何在城市市之间的相通公路的距离，

59、问题是如何在城市A和城市和城市B之间之间找一条最近的通路。如果将城市用顶点表示，城市间的公路找一条最近的通路。如果将城市用顶点表示，城市间的公路用边表示，公路的长度则作为边的权值，那么，这个问题就用边表示，公路的长度则作为边的权值，那么，这个问题就可归结为在网中，求点可归结为在网中，求点A到点到点B的所有路径中，边的权值之和的所有路径中，边的权值之和最短的那一条路径。这条路径就称为两点之间的最短路径，最短的那一条路径。这条路径就称为两点之间的最短路径，并称路径上的第一个顶点为源点（并称路径上的第一个顶点为源点（Sourse），最后一个顶点），最后一个顶点为终点（为终点（Destination）

60、。在不带权的图中，最短路径是指两）。在不带权的图中，最短路径是指两点之间经历的边数最少的路径。点之间经历的边数最少的路径。 例如在图例如在图7-20中，设中，设V1为源点，则从为源点，则从V1出发的路径有出发的路径有（括号里为路径长度）：（括号里为路径长度）：C语言数据结构第06讲V V1 1到到V V2 2的路径有条：的路径有条：V V1 1VV2 2(20)(20)V V1 1到到V V3 3的路径有条：的路径有条：V V1 1VV3 3(15),V(15),V1 1VV2 2VV3 3(55)(55)V V1 1到到V V4 4的路径有条：的路径有条：V V1 1VV2 2VV4 4(30),V(30),V1 1VV3 3VV4 4(45),V(45),V1 1VV2 2VV3 3VV4 4(85)(85)V