广优先遍历PPT课件

1、第8 8章 图 知 识 点图的逻辑结构及基本术语邻接矩阵和邻接表的存储结构和特点深度优先搜索和广度优先搜索两种遍历算法图的连通性和生成树的概念最短路径的含义及求最短路径的算法第1页/共82页 难难 点点图的遍历 最小生成树 最短路径 要要 求求熟练掌握以下内容： 图的存储结构 图的遍历算法了解以下内容： 图的最小生成树和求最小生成树算法 带权有向图的最短路径问题第2页/共82页第8 8章 目录 8-1 8-1 图的定义和术语 8-2 8-2 图的存储表示 8-3 8-3 图的遍历 8-4 8-4 图的连通性 8-5 8-5 最短路径 8-6 8-6 有向无环图及其应用 小 结 验证性实验8 8

2、 图子系统 自主设计实验最小生成树 单元练习8 8第3页/共82页-1 图的定义和术语 图（图（GraphGraph）是一种比树形结构更复杂的非线性结构。在图形结构中，每个结）是一种比树形结构更复杂的非线性结构。在图形结构中，每个结点都可以有多个直接前驱和多个直接后继。点都可以有多个直接前驱和多个直接后继。-1 -1 图的定义和术语图的定义和术语-1-1 -1-1 图的定义图的定义 图（图（GraphGraph）是由非空的顶点（）是由非空的顶点（VerticesVertices）集合和一个描述顶点之间关系）集合和一个描述顶点之间关系边（边（EdgesEdges）的有限集合组成的一种数据结构。可

3、以用二元组定义为：）的有限集合组成的一种数据结构。可以用二元组定义为： G G（V V，E E） 其中，其中，G G表示一个图，表示一个图，V V是图是图G G中顶点的集合，中顶点的集合，E E是图是图G G中边的集合。中边的集合。第4页/共82页 图-1 无向图G1 图-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之间有一条无向直接之间有一

4、条无向直接连线，也称为边。连线，也称为边。G2=(V,E)V=v1,v2,v3,v4E=, 表示顶点表示顶点vi和顶点和顶点vj之间有一条有向直接连之间有一条有向直接连线，也称为弧。其中线，也称为弧。其中vi称为弧尾，称为弧尾，vj称为弧头。称为弧头。第5页/共82页-1-2 -1-2 图的相关术语图的相关术语（1 1）无向图（）无向图（UndigraphUndigraph） 在一个图中，如果每条边都没有方向（如图在一个图中，如果每条边都没有方向（如图-1-1），则称该图为无向图。），则称该图为无向图。（2 2）有向图（）有向图（DigraphDigraph） 在一个图中，如果每条边都有方向（

5、如图在一个图中，如果每条边都有方向（如图-2-2），则称该图为有向图。），则称该图为有向图。（3 3）无向完全图）无向完全图 在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。可以证明，在一个含有无向完全图。可以证明，在一个含有n n个顶点的无向完全图中，有个顶点的无向完全图中，有n (n-1)/2n (n-1)/2条边。条边。 第6页/共82页（4 4）有向完全图）有向完全图 在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，

6、则称该图为有向完全图。在一个含有则称该图为有向完全图。在一个含有n n个顶点的有向完全图中，有个顶点的有向完全图中，有n (n-1) n (n-1) 条条弧。弧。（5 5）稠密图、稀疏图）稠密图、稀疏图 我们称边数很多的图为稠密图；称边数很少的图为稀疏图。我们称边数很多的图为稠密图；称边数很少的图为稀疏图。（6 6）顶点的度）顶点的度 在无向图中：一个顶点拥有的边数，称为该顶点的度。记为在无向图中：一个顶点拥有的边数，称为该顶点的度。记为TD (v)TD (v)。第7页/共82页 在有向图中：在有向图中： (a) 一个顶点拥有的弧头的数目，称为该顶点的入度，一个顶点拥有的弧头的数目，称为该顶点

7、的入度， 记为记为ID (v)； (b) 一个顶点拥有的弧尾的数目，称为该顶点的出度，一个顶点拥有的弧尾的数目，称为该顶点的出度， 记为记为OD (v)； (c) 一个顶点度等于顶点的入度一个顶点度等于顶点的入度+出度，出度， 即：即：TD (v)=ID (v)OD (v)。 在图在图-1的的G1中有：中有： TD(v1)=2 TD(v2)=3 TD(v3)=3 TD(v4)=2 TD(v5)=2 在图在图 -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

8、ID(v4)=1 OD(v4)=1 TD(v4)=2第8页/共82页 可以证明，对于具有可以证明，对于具有n n个顶点、个顶点、e e条边的图，顶点条边的图，顶点v vi i的度的度TD (vTD (vi i) )与顶点的与顶点的个数以及边的数目满足关系：个数以及边的数目满足关系： （7 7）权）权 图的边或弧有时具有与它有关的数据信息，这个数据信息就称为权图的边或弧有时具有与它有关的数据信息，这个数据信息就称为权（WeightWeight）。）。ACBD58697（8 8）网）网边（或弧）上带权的图称为边（或弧）上带权的图称为网（网（NetworkNetwork）。）。 如图如图-3-3所示

9、，就是一个无向网。如所示，就是一个无向网。如果边是有方向的带权图，则就是一个有向果边是有方向的带权图，则就是一个有向网。网。图图-3 一个无向网示意一个无向网示意11()2niieTD v第9页/共82页（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) )分别为图中的边。路径上边的数目称为路

10、径长度。分别为图中的边。路径上边的数目称为路径长度。 在图在图-1-1的无向图的无向图G1G1中，中，v v1 1vv4 4vv3 3vv5 5与与v v1 1vv2 2vv5 5是从顶点是从顶点v v1 1 到顶点到顶点v v5 5 的两条路径，路径长度分别为的两条路径，路径长度分别为3 3和和2 2。（1010）回路、简单路径、简单回路）回路、简单路径、简单回路 在一条路径中，如果其起始点和终止点是同一顶点，则称其为回路或者环。在一条路径中，如果其起始点和终止点是同一顶点，则称其为回路或者环。如果一条路径上所有顶点除起始点和终止点外彼此都是不同的，则称该路径为如果一条路径上所有顶点除起始点

11、和终止点外彼此都是不同的，则称该路径为简单路径。简单路径。 在图在图-1-1中，前面提到的中，前面提到的v v1 1到到v v5 5的两条路径都为简单路径。除起始点和终的两条路径都为简单路径。除起始点和终止点外，其他顶点不重复出现的回路称为简单回路，或者简单环。如图止点外，其他顶点不重复出现的回路称为简单回路，或者简单环。如图 -2-2中中的的v v1 1vv3 3vv4 4vv1 1。第10页/共82页（1111）子图）子图 对于图对于图G=G=（V V，E E），），G G= =（V V，E E），若存在），若存在V V是是V V的子集的子集 ，E E是是E E的子集的子集 ，则称图则称图

12、G G是是G G的一个子图。的一个子图。 图图-4(a)-4(a)表示出了图表示出了图8-18-1无向图无向图G G1 1的一个子图，图的一个子图，图-4(b)表示出了图表示出了图8-2有向图有向图G G2 2的一个子图。的一个子图。 图图-4 图图G1和和G2的两个子图示意的两个子图示意 (a) G1的子图的子图 (b) G2的子图的子图 V1V4V2V1V3V2V4V5第11页/共82页（1212）连通图、连通分量）连通图、连通分量 在无向图中，如果从一个顶点在无向图中，如果从一个顶点v vi i到另一个顶点到另一个顶点v vj j(ij)(ij)有路径，则称顶点有路径，则称顶点v vi

13、i和和v vj j是连通的。任意两顶点都是连通的图称为连通图。无向图的极大连通子是连通的。任意两顶点都是连通的图称为连通图。无向图的极大连通子图称为连通分量。图图称为连通分量。图-5 (-5 (a)a)中有两个连通分量，如图中有两个连通分量，如图 -5 (-5 (b)b)所示。所示。AEBFCDAEBFCD (a) 无向图无向图G3 (b) G3的两个连通分量的两个连通分量 图图-5 无向图及连通分量示意无向图及连通分量示意第12页/共82页（13）强连通图、强连通分量）强连通图、强连通分量 对于有向图来说，若图中任意一对顶点对于有向图来说，若图中任意一对顶点vi 和和vj(ij)均有从一个顶

14、点均有从一个顶点vi到另一个顶点到另一个顶点vj有路径，也有从有路径，也有从vj到到vi的路径，则称该有向图是强连通图。有向图的极的路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量。大强连通子图称为强连通分量。 图图-2中有两个强连通分量，分别是中有两个强连通分量，分别是v1,v3,v4和和v2，如图如图8-6所示。所示。（14）生成树）生成树 连通图连通图G的一个子图如果是一棵包含的一个子图如果是一棵包含G的所有顶点的树，则该子图称为的所有顶点的树，则该子图称为G的生的生成树（成树（Spanning Tree）。）。在生成树中添加任意一条属于原图中的边必定会产生在生成树中添

15、加任意一条属于原图中的边必定会产生回路，因为新添加的边使其所依附的两个顶点之间有了第二条路径。若生成树中回路，因为新添加的边使其所依附的两个顶点之间有了第二条路径。若生成树中减少任意一条边，则必然成为非连通的。减少任意一条边，则必然成为非连通的。n个顶点的生成树具有个顶点的生成树具有n-1条边。条边。V1V3V2V4图图-6 有向图有向图G2的两个的两个 强连通分量示意强连通分量示意第13页/共82页8-1-3 图的基本操作图的基本操作 图的基本操作有：图的基本操作有：（1）CreatGraph（G）输入图）输入图G的顶点和边，建立图的顶点和边，建立图G的存储。的存储。（2）DFSTraver

16、se（G，v）在图）在图G中，从顶点中，从顶点v出发深度优先遍历图出发深度优先遍历图G。（3）BFSTtaverse（G，v）在图）在图G中，从顶点中，从顶点v出发广度优先遍历图出发广度优先遍历图G。 图的存储结构比较多。对于图的存储结构的选择取决于具体的应用和需图的存储结构比较多。对于图的存储结构的选择取决于具体的应用和需要进行的运算。要进行的运算。 下面介绍几种常用的图的存储结构。下面介绍几种常用的图的存储结构。8-2 图的存储表示第14页/共82页 邻接矩阵是表示顶点之间相邻关系的矩阵。邻接矩阵是表示顶点之间相邻关系的矩阵。 假设图假设图G（V，E）有）有n个顶点，即个顶点，即Vv0,v

17、1,vn-1，则，则G的邻接矩阵是具的邻接矩阵是具有如下性质的有如下性质的n阶方阵：阶方阵： 1 若若(vi,vj)或或是是E(G)中的边中的边 Aij= 0 若若(vi,vj)或或不是不是E(G)中的边中的边 若若G是网，则邻接矩阵可定义为：是网，则邻接矩阵可定义为： wij 若若(vi,vj)或或是是E(G)中的边中的边 Aij= 0或或 若若(vi,vj)或或不是不是E(G)中的边中的边 其中，其中，wij表示边表示边(vi,vj)或或上的权值（如图上的权值（如图7-3）；）；表示一个计算机允表示一个计算机允许的、大于所有边上权值的数。许的、大于所有边上权值的数。第15页/共82页 无向

18、图用邻接矩阵表示如图无向图用邻接矩阵表示如图8-7所示；有向网用邻接矩阵表示如图所示；有向网用邻接矩阵表示如图8-8所所示。示。图图8-7 一个无向图的邻接矩阵表示一个无向图的邻接矩阵表示图8-8 一个有向网的邻接矩阵表示第16页/共82页 从图的邻接矩阵存储具有以下性质：从图的邻接矩阵存储具有以下性质：（1 1）无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只）无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。需存放上（或下）三角矩阵的元素即可。 （2 2）对于无向图，邻接矩阵的第）对于无向图，邻接矩阵的第i i行（或第行（或

19、第i i列）非零元素（或非列）非零元素（或非元素）的个元素）的个数正好是第数正好是第i i个顶点的度个顶点的度TD(vTD(vi i) )。 （3 3）对于有向图，邻接矩阵的第）对于有向图，邻接矩阵的第i i行（或第行（或第i i列）非零元素（或非列）非零元素（或非元素）的个元素）的个数正好是第数正好是第i i个顶点的出度个顶点的出度OD(vOD(vi i) )（或入度（或入度ID(vID(vi i) )）。）。 （4 4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行

20、、按列对每个元素进行检测，所花费但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。的时间代价很大。这是用邻接矩阵存储图的局限性。第17页/共82页图的邻接矩阵存储的描述如下：图的邻接矩阵存储的描述如下：#define MAXLEN 10typedef struct char vexsMAXLEN; int edgesMAXLENMAXLEN; int n,e; MGraph;建立一个有向图的邻接矩阵存储的算法如下：建立一个有向图的邻接矩阵存储的算法如下： 第18页/共82页void CreateMGraph(MGraph &am

21、p;G) int i,j,k; char ch1,ch2; printf(请输入顶点数和边数请输入顶点数和边数(输入格式为输入格式为:顶点数顶点数,边数边数):n); scanf(%d%d,&(G.n),&(G.e); printf(请输入顶点信息请输入顶点信息(顶点标志顶点标志)每个顶点以回车作为结束每个顶点以回车作为结束:n); for (i=0;iG.n;i+) fflush(stdin); scanf(%c,&(G.vexsi); for (i=0;iG.n;i+) for (j=0;jG.n;j+)G.edgesij=0;/ 邻接矩阵初始化邻接矩阵初始化 pr

22、intf (请输入每条边所对应的两个顶点（先输入弧尾，后输入弧头）请输入每条边所对应的两个顶点（先输入弧尾，后输入弧头）!n); for(k=0;kG.e;k+) fflush(stdin); printf(请输入第请输入第%d条边的两个顶点标志条边的两个顶点标志(用逗号分隔用逗号分隔)：,k+1); scanf(%c,%c,&ch1,&ch2); for(i=0;ch1!=G.vexsi;i+); for(j=0;ch2!=G.vexsj;j+) G.edgesij=1; / 将输入边对应的矩阵元素值设为将输入边对应的矩阵元素值设为1第19页/共82页8-2-2 8-2-2

23、邻接表邻接表 邻接表邻接表(Adjacency List)是图的一种顺序存储与链式存储结合的存储方法。是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点中的每个顶点vi，该，该方法将所有邻接于方法将所有邻接于vi的顶点的顶点vj链成一个单链表，这个单链表就称为顶点链成一个单链表，这个单链表就称为顶点vi的邻的邻接表。再将所有点的邻接表表头放到数组中，就构成了图的邻接表。接表。再将所有点的邻接表表头放到数组中，就构成了图的邻接表。 在邻接表表示中有两种结点结构，如图在邻接表表示中有两种结点结构

24、，如图8-9所示。所示。 图图8-9 邻接矩阵表示的结点结构邻接矩阵表示的结点结构第20页/共82页 一种是顶点表的结点结构，它由顶点域（一种是顶点表的结点结构，它由顶点域（vertex）和指向第一条邻接边）和指向第一条邻接边的指针域（的指针域（firstedge）构成，另一种是边表结点，它由邻接点域）构成，另一种是边表结点，它由邻接点域(adjvex)和和指向下一条邻接边的指针域指向下一条邻接边的指针域(next)构成。对于网的边表需再增设一个存储边构成。对于网的边表需再增设一个存储边上信息（如权值等）的域（上信息（如权值等）的域（info），网的边表结构如图），网的边表结构如图8-10所示

25、。所示。 图图8-10 网的边表结构网的边表结构第21页/共82页 图图8-11给出无向图给出无向图8-7对应的邻接表表示。对应的邻接表表示。 图图8-11 图图8-7无向图的邻接表表示无向图的邻接表表示邻接表表示形式描述如下：邻接表表示形式描述如下：第22页/共82页define MAXLEN 10 / 最大顶点数为最大顶点数为10typedef struct edgenode int adjvex; / 邻接顶点的下标邻接顶点的下标 struct edgenode *next; / 指向下一个邻接边结点的指针指向下一个邻接边结点的指针 EdgeNode; / 定义边结点类型定义边结点类型t

26、ypedef struct VertexType vertex; / 顶点标志顶点标志 EdgeNode *firstedge; / 保存第一个边结点地址的指针保存第一个边结点地址的指针 VertexNode; / 定义顶点结点类型定义顶点结点类型typedef struct VertexNode adjlistMAXLEN; / 顶点数组顶点数组 int n,e; / 顶点数和边数顶点数和边数 ALGraph; / 定义邻接表的类型名定义邻接表的类型名ALGraph第23页/共82页void CreateGraphAL(ALGraph &G) / 有向图的邻接表存储算法 int i,

27、k; EdgeNode *s; char ArcTail,ArcHead; / 保存弧尾、弧头标志 int TailPoi,HeadPoi; / 保存弧尾、弧头下标 printf(请输入顶点数和边数(输入格式为:顶点数,边数)：n); scanf(%d%d,&(G.n),&(G.e); / 读入顶点数和边数 printf(请输入顶点信息(输入格式为:顶点号) 以回车作为结束:n); for (i=0;iG.n;i+) / 建立有n个顶点的顶点表 scanf(%c,&(G.adjlisti.vertex); / 输入顶点信息 G.adjlisti.firstedge=NU

28、LL; / 指向第一个边结点的指针设为空 printf(请输入边的信息(输入格式为:弧尾,弧头)：n);for(k=0;kG.e;k+) / 建立边表 scanf(“%c,%c”,&ArcTail,&ArcHead); for(i=0;iadjvex=HeadPoi; / 构造新边结点 s-next=G.adjlistTailPoi.firstedge; G.adjlisti.firstedge=s; 第24页/共82页 若无向图中有若无向图中有n 个顶点、个顶点、e条边，则它的邻接表需条边，则它的邻接表需n个头结点和个头结点和2e个表结点。个表结点。显然，在边稀疏显然，在边稀

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

30、立一个有向图的逆邻接表，即对每个顶点可以建立一个有向图的逆邻接表，即对每个顶点vi 建立一个链接，以建立一个链接，以vi为弧头为弧头的弧的链表。例如图的弧的链表。例如图8-12所示为有向图所示为有向图G2（见图（见图8-2）的邻接表和逆邻接表。）的邻接表和逆邻接表。第25页/共82页 在建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则建在建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则建立邻接表的复杂度为立邻接表的复杂度为O（n+e），否则，需要通过查找才能得到顶点在图中），否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为位置，则时间复杂度为O（n*e）。）。 图8

31、-12 图8-8有向网的邻接表和逆邻接表第26页/共82页8.2.3 十字链表十字链表 由于邻接表中通过某顶点查找以该顶点为弧尾的弧结点很方便，但是通由于邻接表中通过某顶点查找以该顶点为弧尾的弧结点很方便，但是通过该顶点查找以其为弧头的弧结点则需要遍历整个邻接表；而逆邻接表在查过该顶点查找以其为弧头的弧结点则需要遍历整个邻接表；而逆邻接表在查找弧结点方面的优缺点则刚好与邻接表相反。为了通过某顶点能够方便地同找弧结点方面的优缺点则刚好与邻接表相反。为了通过某顶点能够方便地同时查找到以该顶点为弧尾和弧头的弧结点，可以将邻接表和逆邻接表合并，时查找到以该顶点为弧尾和弧头的弧结点，可以将邻接表和逆邻接

32、表合并，这样就构成了有向图的十字链表存储结构。这样就构成了有向图的十字链表存储结构。十字链表的结点结构如图所示：十字链表的结点结构如图所示：图8-13 十字链表的结点结构第27页/共82页十字链表的结点结构定义如下：#define MAXLEN 20typedef struct arcnode int TailVex, HeadVex; / 弧尾和弧头顶点的下标 struct arcnode *TLink, *HLink; / 指向同弧尾和同弧头的下一个弧结点的指针 int weight; / 弧的权值信息 ArcNode; / 定义弧结点的类型typedef struct vexnode c

33、har vertex; / 顶点标志 ArcNode *FirstIn, *FirstOut; / 指向第一个弧头结点和弧尾结点的指针 VexNode; / 定义顶点结点的类型typedef struct VexNode listMAXLEN; / 顶点数组 int VexNum, ArcNum; / 顶点数和弧数 OLGraph; / 定义十字链表的类型第28页/共82页图8-8所示有向网的十字链表存储结构如图8-14所示。图8-14 有向图的十字链表结构 创建十字链表的算法如下：第29页/共82页void CreateOrthList(OLGraph &G) ArcNode *p;

34、 int i, j; char ArcTail, ArcHead; char ArcTail, ArcHead; printf(请输入有向网的顶点数和弧数:n); scanf(%d%d,&G.VexNum,&G.ArcNum); printf(请依次输入%d个顶点(用回车分隔):n,G.VexNum); for(i=0;ivexnum;i+) scanf(%c,&G.listi.vertex);/ 输入顶点标志 G.listi.FirstIn=NULL; / 初始化弧结点指针 G.listi.FirstOut=NULL;printf(顶点数组创建成功！n);第30页/共

35、82页void CreateOrthList(OLGraph &G) ArcNode *p; int i, j; char ArcTail, ArcHead; char ArcTail, ArcHead; printf(请输入有向网的顶点数和弧数请输入有向网的顶点数和弧数:n); scanf(%d%d,&G.VexNum,&G.ArcNum); printf(请依次输入请依次输入%d个顶点个顶点(用回车分隔用回车分隔):n,G.VexNum); for(i=0;ivexnum;i+) scanf(%c,&G.listi.vertex);/ 输入顶点标志输入顶点标

36、志 G.listi.FirstIn=NULL;/ 初始化弧结点指针初始化弧结点指针 G.listi.FirstOut=NULL; printf(顶点数组创建成功！顶点数组创建成功！n);第31页/共82页 类似于有向图（或网）的十字链表存储结构，无向图（或网）类似于有向图（或网）的十字链表存储结构，无向图（或网）还有一种邻接多重表（还有一种邻接多重表（Adjacency MultiList）的存储结构。）的存储结构。 虽然邻接表是无向图的一种很有效的存储结构，但是，在无虽然邻接表是无向图的一种很有效的存储结构，但是，在无向图的邻接表结构中，每条边都存在两个顶点，并且这两个顶点分向图的邻接表结构

37、中，每条边都存在两个顶点，并且这两个顶点分别位于两个链表中，这给无向图的某些操作带来了不便。例如，在别位于两个链表中，这给无向图的某些操作带来了不便。例如，在某些图的问题中需要对某条边进行某种操作，如插入或删除一条边某些图的问题中需要对某条边进行某种操作，如插入或删除一条边等，此时都必须找到表示同一条边的两个边结点，并分别对其操作，等，此时都必须找到表示同一条边的两个边结点，并分别对其操作，这样显得比较繁琐。因此，在处理和边有关的大量问题中，更多的这样显得比较繁琐。因此，在处理和边有关的大量问题中，更多的时候邻接多重表比邻接表显得更为合适。时候邻接多重表比邻接表显得更为合适。 邻接多重表的每条

38、边都用一个边结点表示，其边结点和顶点邻接多重表的每条边都用一个边结点表示，其边结点和顶点结点的结构分别如图结点的结构分别如图8-15中的中的(a)(b)所示。所示。图8-15 邻接多重表的结点结构第32页/共82页邻接多重表的类型定义如下：邻接多重表的类型定义如下：#define MAXLEN 20typedef struct edgenode int iVex, jVex; / 边两端顶点的下标边两端顶点的下标 struct edgenode *iLink, *jLink; / 指向具有相同端点的下一个边指向具有相同端点的下一个边结点的指针结点的指针 int weight; / 边的权值信息

39、边的权值信息 EdgeNode; / 定义边结点的类型定义边结点的类型typedef struct vexnode char vertex; / 顶点标志顶点标志 ArcNode *FirstEdge; / 指向第一个邻接边结点的指针指向第一个邻接边结点的指针 VexNode; / 定义顶点结点的类型定义顶点结点的类型typedef struct VexNode listMAXLEN; / 顶点数组顶点数组int VexNum, EdgeNum; / 顶点数和边数顶点数和边数 AMLGraph; / 定义邻接多重表的类型定义邻接多重表的类型第33页/共82页-3 图的遍历 图的遍历（图的遍历（

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

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

42、82页-3-1 深度优先搜索深度优先搜索 深度优先搜索（深度优先搜索（Depth-Fisrst Search）遍历类似于树的先根）遍历类似于树的先根遍历，是树的先根遍历的推广。遍历，是树的先根遍历的推广。 假设初始状态是图中所有顶点未曾被访问，则深度优先搜索假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点发可从图中某个顶点发v出发，首先访问此顶点，然后任选一个出发，首先访问此顶点，然后任选一个v的的未被访问的邻接点未被访问的邻接点w出发，继续进行深度优先搜索，直到图中所出发，继续进行深度优先搜索，直到图中所有和有和v路径相通的顶点都被访问到；若此时图中还有顶点未被访路径相通

43、的顶点都被访问到；若此时图中还有顶点未被访问到，则另选一个未被访问的顶点作为起始点，重复上面的做法，问到，则另选一个未被访问的顶点作为起始点，重复上面的做法，直至图中所有的顶点都被访问。直至图中所有的顶点都被访问。V1V5V2V4V8V3V6V7图图-16 无向图无向图G5 以图以图-16的无向图的无向图G5为例，其为例，其深度优先搜索得到的顶点访问序列深度优先搜索得到的顶点访问序列为：为： v1 v2 v4 v8 v5 v3 v6 、 v7动画演示动画演示第35页/共82页 显然，以上方法是一个递归的过程。为了在遍历过程中便于区分顶点是否显然，以上方法是一个递归的过程。为了在遍历过程中便于区

44、分顶点是否已被访问，需附设访问标志数组已被访问，需附设访问标志数组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+) if (!visitedi)

45、DFSM(G,i); 第36页/共82页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函数，因为一旦某个顶函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质点被标志

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

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

48、直至图中所有被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。访问到为止。第38页/共82页 对图对图-16无向图无向图 进行广度优先遍历，首先进行广度优先遍历，首先访问访问v1 和和v1的邻接点的邻接点v2和和v3，然后依次访问，然后依次访问v2 的的邻接点邻接点v4 和和v5 及及v3 的邻接点的邻接点v6和和v7，最后访问，最后访问v4

49、的邻接点的邻接点v8。由于这些顶点的邻接点均已被访问，。由于这些顶点的邻接点均已被访问，并且图中所有顶点都被访问，由些完成了图的遍并且图中所有顶点都被访问，由些完成了图的遍历。得到的顶点访问序列为：历。得到的顶点访问序列为： v1v2 v3 v4 v5 v6 v7 v8 和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺次访问路径长度为为了顺次访问路径长度为2、3、的顶点，需附设队列以存储已被访问的路的顶点，需附设队列以存储已被访问的路径长度为径长度为1、2、 的顶点。的顶点。V1V5V2V4V8V3V6V7图

50、图-16 无向图无向图G5 动画演示动画演示第39页/共82页 从图的某一点从图的某一点v出发，递归地进行广度优先遍历的过程如下面的算法所示。出发，递归地进行广度优先遍历的过程如下面的算法所示。 void BFSTraverseM(MGraph *G) int i; for (i=0;in;i+) visitedi=FALSE; for (i=0;in;i+) if (!visitedi) BFSM(G,i);第40页/共82页 void BFSM(MGraph *G,int k)int i,j; CirQueue Q; InitQueue(&Q); printf (广度优先遍历结点广

51、度优先遍历结点: 结点结点%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 (广度优先遍历结点广度优先遍历结点:%cn,G-vexsj); visitedj=TRUE; EnQueue(&Q,j); 第41页/共82页-4 图的连通性 分析上述算法，每个顶点至多进一次队列。遍历图的过程实质是通过边分析上述算法，每个顶点至多进一次队列。遍历图的过

52、程实质是通过边或弧找邻接点的过程，因此广度优先搜索遍历图和深度优先搜索遍历的时间或弧找邻接点的过程，因此广度优先搜索遍历图和深度优先搜索遍历的时间复杂度是相同的，两者不同之处仅仅在于对顶点访问的顺序不同。复杂度是相同的，两者不同之处仅仅在于对顶点访问的顺序不同。 判定一个图的连通性是图的一个应用问题，我们可以利用图的遍历算法判定一个图的连通性是图的一个应用问题，我们可以利用图的遍历算法来求解这一问题。本节将讨论无向图的连通性问题，并讨论最小代价生成树来求解这一问题。本节将讨论无向图的连通性问题，并讨论最小代价生成树等问题。等问题。第42页/共82页-4-1 -4-1 无向图的连通分量和生成树无

53、向图的连通分量和生成树 在对无向图进行遍历时，对于连通图，仅需从图中任一顶在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点。对非连通图，则需从多个顶点出发进行搜索，而每所有顶点。对非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。列恰为其各个连通分量中的顶点集。 例如，图例如，图-17 (a) 是一个非连通图，按照图是一个非连通图，按照图-17 (

54、b) 所所示示 的邻接表进行深度优先搜索遍历的邻接表进行深度优先搜索遍历 图图-17(a) 非连通图非连通图 图图-17(b) G6的邻接表的邻接表AEBFCD第43页/共82页 两次调用两次调用DFS过程（即分别从顶点过程（即分别从顶点A 和和D出发），得到的顶点访问序列出发），得到的顶点访问序列为：为： A B F E C E 这两个顶点集分别加上所有依附于这些顶点的边，便构成了非连通图这两个顶点集分别加上所有依附于这些顶点的边，便构成了非连通图G3的两个连通分量。的两个连通分量。 因此，要想判定一个无向图是否为连通图，或有几个连通分量，就可设因此，要想判定一个无向图是否为连通图，或有几个

55、连通分量，就可设一个计数变量一个计数变量count，初始时取值为，初始时取值为0，在深度优先搜索算法循环中，每调用，在深度优先搜索算法循环中，每调用一次一次DFS，就给，就给count增增1。这样，当整个算法结束时，依据。这样，当整个算法结束时，依据count 的值，就的值，就可确定图的连通性了。可确定图的连通性了。 设设E(G)E(G)为连通图为连通图G G中所有边的集合，则从图中任一顶点出发遍历图时，中所有边的集合，则从图中任一顶点出发遍历图时，必定将必定将E(G)E(G)分成两个集合分成两个集合T(G)T(G)和和B(G)B(G)，其中，其中T(G)T(G)是遍历图过程中历经的边的是遍历

56、图过程中历经的边的集合；集合；B(G)B(G)是剩余的边的集合。显然，是剩余的边的集合。显然，T(G)T(G)和图和图G G中所有顶点一起构成连通图中所有顶点一起构成连通图G G的极小连通子图。的极小连通子图。第44页/共82页 按照-1-2-1-2节的定义，它是连通图的一棵生成树，并且由深度优先搜索得到的为深度优先生成树；由广度优先搜索得到的为广度优先生成树。例如，图-18(a)-18(a)和(b)(b)所示分别为图-16-16连通图G5G5的深度优先生成树和广度优先生成树。图中虚线为集合B(G) B(G) 中的边，实线为集合T(G)T(G)中的边。图图-18(a) G5的深度优先生成树的深

57、度优先生成树图图-18(b) G5的广度优先生成树的广度优先生成树V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7第45页/共82页 对于非连通图，通过这样的遍历，将得到的是生成森林。例如，图-19 (b) -19 (b) 所示为图-19 (a)-19 (a)的深度优先生成的森林，它由三棵深度优先生成树组成。图图-19(a) 非连通无向图非连通无向图G图图-19(b) G的深度优先生成树林的深度优先生成树林JHKLMAICFGBDEJHKLMAICFGBDE第46页/共82页-4-2 -4-2 最小生成树最小生成树1 1最小生成树的基本概念最小生成树的基本概念 由生成树的定义可

58、知，无向连通图的生成树不一定是唯由生成树的定义可知，无向连通图的生成树不一定是唯一的。连通图的一次遍历所经过的边的集合及图中所有顶点的一的。连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。图能得到不同的生成树。图-20 (a)、(b)和和(c)所示的均为图所示的均为图-16的无向连通图的无向连通图G5的生成树。的生成树。V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7 图图-17 -17 无向连通图无向连通图G5G5的三

59、棵生成树的三棵生成树（a）（b）（c）第47页/共82页 可以证明，对于有可以证明，对于有n个顶点的无向连通图，无论其生成树的形态如何，所个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有有生成树中都有且仅有n-1条边。条边。 如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值之如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值之和为最小的生成树，简称为最小生成树。和为最小的生成树，简称为最小生成树。 最小生成树的概念可以应用到许多实际问题中。例如有这样一个问题：以最小生成树的概念可以应用到许多实际问题中。例如有这样一个问题：以尽可能抵的总造价建造城市间

60、的通讯网络，把十个城市联系在一起。在这十个尽可能抵的总造价建造城市间的通讯网络，把十个城市联系在一起。在这十个城市中，任意两个城市之间都可以建造通讯线路，通讯线路的造价依据城市间城市中，任意两个城市之间都可以建造通讯线路，通讯线路的造价依据城市间的距离不同而有不同的造价，可以构造一个通讯线路造价网络，在网络中，每的距离不同而有不同的造价，可以构造一个通讯线路造价网络，在网络中，每个顶点表示城市，顶点之间的边表示城市之间可构造通讯线路，每条边的权值个顶点表示城市，顶点之间的边表示城市之间可构造通讯线路，每条边的权值表示该条通讯线路的造价，要想使总的造价最低，实际上就是寻找该网络的最表示该条通讯线路的造价，要想使总的造价最低，实际上就是寻找该网络的最小生成树。小生成树。第48页/共82页2常用的构造最小生成树的方法常用的构造最小生成树的方法（1 1）构造最小生成树的）构造最小生成树的Pri