1、数数 据据 结结 构构 测测 绘绘 学学 院院一、教学内容：一、教学内容：1、图的基本概念2、图的存储结构（邻接矩阵、邻接表及有向图十字邻接表）3、图的遍历（深度优先搜索、广度优先搜索）二、教学要求：二、教学要求：1、理解图的基本概念，熟悉图的各种存储结构及其构造算法；2、掌握图的两种搜索路径的遍历；数数 据据 结结 构构 测测 绘绘 学学 院院 图（Graph）是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，即每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素 之间有着明显的层次关系，虽然每一层上的数据元素可能和下一层中多个元素（孩子） 相关，但只
2、能和上一层中一个元素（双亲）相关；而在图形结构中，结点之间图形结构中，结点之间 的关系可以是任的关系可以是任意的，任意两个数据元素之间都可能相关。意的，任意两个数据元素之间都可能相关。 数数 据据 结结 构构 测测 绘绘 学学 院院7.1 图的基本概念图的基本概念7.1.1 图的定义图的定义 图图G是由顶点集是由顶点集V和顶点间的关系集合和顶点间的关系集合E（边的集合）组成的一种数据结构，可以用二（边的集合）组成的一种数据结构，可以用二元组定义为：元组定义为：G=（V,E）数数 据据 结结 构构 测测 绘绘 学学 院院例如，对于图例如，对于图7-1所示的无向图所示的无向图G1和有向图和有向图G
3、2，它们的，它们的数据结构可以描述为：数据结构可以描述为：G1=(V1,E1), 其中其中 V1=a,b,c,d,E1=(a,b),(a,c),(a,d),(b,d),(c,d)G2=(V2,E2)，其中，其中V2=1,2,3, E2=,。 d A cA b a 2 1 3 (a) 无向图G1 (b) 有向图G2 图7-1 无向图和有向图 数数 据据 结结 构构 测测 绘绘 学学 院院7.1.2 图的基本术语图的基本术语 1. 有向图和无向图有向图和无向图 在图中，若用箭头标明了边是有方向性的，则称在图中，若用箭头标明了边是有方向性的，则称这样的图为有向图，否则称为无向图。如图这样的图为有向图
4、，否则称为无向图。如图7-1中，中，G1为无向图，为无向图，G2为有向图。为有向图。 在无向图中，一条边（在无向图中，一条边（x,y）与（）与（y,x）表示的结果）表示的结果相同，用圆括号表示，在有向图中，一条边相同，用圆括号表示，在有向图中，一条边与与表示的结果不相同，故用尖括号表示。表示的结果不相同，故用尖括号表示。表表示从顶点示从顶点x发向顶点发向顶点y的边，的边，x为始点，为始点，y为终点。有向为终点。有向边也称为弧，边也称为弧，x为弧尾，为弧尾，y为弧头为弧头,则则表示为一条表示为一条弧弧,而而表示表示y为弧尾，为弧尾，x为弧头的另一条弧为弧头的另一条弧 。 数数 据据 结结 构构
5、测测 绘绘 学学 院院2. 完全图、稠密图、稀疏图完全图、稠密图、稀疏图 具有具有n个顶点，个顶点，n(n-1)/2条边的图，称为完全无向图，条边的图，称为完全无向图，具有具有n个顶点，个顶点，n(n-1) 条弧的有向图条弧的有向图,称为完全有向图。称为完全有向图。完全无向图和完全有向图都称为完全图。完全无向图和完全有向图都称为完全图。对于一般无向图，顶点数为对于一般无向图，顶点数为n，边数为，边数为e，则则 0e n(n-1)/2。对于一般有向图，顶点数为对于一般有向图，顶点数为n，弧数为，弧数为e， 则则 0en(n-1) 。当一个图接近完全图时，则称它为稠密图，相反地，当一个图接近完全图
6、时，则称它为稠密图，相反地，当一个图中含有较少的边或弧时，则称它为稀疏图。当一个图中含有较少的边或弧时，则称它为稀疏图。数数 据据 结结 构构 测测 绘绘 学学 院院3. 度、入度、出度度、入度、出度 图中，一个顶点依附的边或弧的数目，称为该顶图中，一个顶点依附的边或弧的数目，称为该顶点的度。在有向图中，一个顶点依附的弧头数目，称点的度。在有向图中，一个顶点依附的弧头数目，称为该顶点的入度。一个顶点依附的弧尾数目，称为该为该顶点的入度。一个顶点依附的弧尾数目，称为该顶点的出度，某个顶点的入度和出度之和称为该顶点顶点的出度，某个顶点的入度和出度之和称为该顶点的度。的度。另外，若图中有另外，若图中
7、有n个顶点，个顶点，e条边或弧，第条边或弧，第i个顶点个顶点的度为的度为di，则有，则有e= 21niid1niiniicr11ri 为入度，为入度， ci为出度为出度数数 据据 结结 构构 测测 绘绘 学学 院院端点和邻接点端点和邻接点在一个无向图中在一个无向图中,若存在一条边若存在一条边(vi,vj),则称则称vi和和vj为此边的两个端点为此边的两个端点,并称它们互为邻接点并称它们互为邻接点(adjacent).在一个有向图中在一个有向图中,若存在一条边若存在一条边,则称则称vi和和vj为此边的起始端点和终止端点为此边的起始端点和终止端点,称它们互为邻称它们互为邻接点接点(adjacent
8、),称称vj为为vi得出边邻接点得出边邻接点,vi为为vj的的入边邻接点入边邻接点.数数 据据 结结 构构 测测 绘绘 学学 院院4. 子图子图若有两个图若有两个图G1和和G2， G1=(V1,E1)， G2=(V2,E2)， 满满足如下条件：足如下条件： V2 V1 ，E2 E1，即，即V2为为V1的子集，的子集，E2为为E1的子集，称图的子集，称图G2为图为图G1的子图。的子图。 4 3 1 2 4 3 1 2 4 1 2 (a)图 G (b)图 G 的两个子图 图 7-2 图与子图示意 4 3 1 2 数数 据据 结结 构构 测测 绘绘 学学 院院5 权权 在图的边或弧中给出相关的数，称
9、为权。在图的边或弧中给出相关的数，称为权。 权可权可以代表一个顶点到另一个顶点的距离，耗费等，带以代表一个顶点到另一个顶点的距离，耗费等，带权图一般称为网。权图一般称为网。 (a) 无向网 (b)有向网 图 7-3 无向带权图和有向带权图 5 3 1 2 4 4 1 6 7 2 3 5 8 A B C 2 1 5 3 4 数数 据据 结结 构构 测测 绘绘 学学 院院6路径、回路路径、回路 在无向图在无向图G中，若存在一个顶点序列中，若存在一个顶点序列Vp ,Vi1，Vi2，Vin，Vq, 使得（使得（Vp,Vi1）,(Vi1,Vi2),.，(Vin,Vq)均属于均属于E（G），则称顶点），则
10、称顶点Vp到到Vq存在一条路存在一条路径。若一条路径上除起点和终点可以相同外，其余顶径。若一条路径上除起点和终点可以相同外，其余顶点均不相同，则称此路径为简单路径。起点和终点相点均不相同，则称此路径为简单路径。起点和终点相同的路径称为回路，简单路径组成的回路称为简单回同的路径称为回路，简单路径组成的回路称为简单回路。路径上经过的边的数目称为该路径的路径长度。路。路径上经过的边的数目称为该路径的路径长度。数数 据据 结结 构构 测测 绘绘 学学 院院7 连通图和强连通图连通图和强连通图在无向图中，若从顶点在无向图中，若从顶点i到顶点到顶点j有路径，则称顶点有路径，则称顶点i和和顶点顶点j是连通的
11、。若任意两个顶点都是连通的，则称是连通的。若任意两个顶点都是连通的，则称此无向图为连通图，否则称为非连通图。此无向图为连通图，否则称为非连通图。 连通图和非连通图示例见图连通图和非连通图示例见图7-4。 3 1 2 4 1 2 3 4 5 （a） 连通图 (b) 非连通图 图 7-4 连通图和非连通图 数数 据据 结结 构构 测测 绘绘 学学 院院 在有向图中，若从顶点在有向图中，若从顶点i到顶点到顶点j有路径，则称从有路径，则称从顶点顶点i和顶点和顶点j是连通的，若图中任意两个顶点都是是连通的，若图中任意两个顶点都是连通的，则称此有向图为强连通图，否则称为非强连通的，则称此有向图为强连通图，
12、否则称为非强连通图。连通图。 A B D C 1 2 1 6 5 4 3 (a)强连通图 (b)非强连通图 图 7-5 强连通图和非强连通图 数数 据据 结结 构构 测测 绘绘 学学 院院8 连通分量和强连通分量连通分量和强连通分量 无向图中，极大的连通子图为该图的连通分量。无向图中，极大的连通子图为该图的连通分量。显然，任何连通图的连通分量只有一个，即它本身，显然，任何连通图的连通分量只有一个，即它本身，而非连通图有多个连通分量。而非连通图有多个连通分量。对于图对于图7-4 中的非连通图，它的连通分量见图中的非连通图，它的连通分量见图7-6。 1 2 3 5 4 图 7-6 图 7-4(b)
13、的连通分量 数数 据据 结结 构构 测测 绘绘 学学 院院 有向图中，极大的强连通子图为该图的强连通有向图中，极大的强连通子图为该图的强连通分量。显然，任何强连通图的强连通分量只有一个，分量。显然，任何强连通图的强连通分量只有一个，即它本身，而非强连通图有多个强连通分量。即它本身，而非强连通图有多个强连通分量。 对于图对于图7-5 中的非强连通图，它的强连通中的非强连通图，它的强连通分量见图分量见图7-7。 6 3 5 图 7-7 图 7-5(b)的强连通分量 2 1 4 数数 据据 结结 构构 测测 绘绘 学学 院院9 生成树、生成森林生成树、生成森林 连通图的生成树是一个极小连通子图，它连
14、通图的生成树是一个极小连通子图，它包含图中全部包含图中全部n个顶点和个顶点和n-1条不构成回路的边。条不构成回路的边。非连通图的生成树则组成一个生成森林。若图中非连通图的生成树则组成一个生成森林。若图中有有n个顶点，个顶点，m个连通分量，则生成森林中有个连通分量，则生成森林中有n-m条边。条边。数数 据据 结结 构构 测测 绘绘 学学 院院7.1.3 图的运算概述图的运算概述 图的基本操作也是插入和删除。但在操作中常常需图的基本操作也是插入和删除。但在操作中常常需要指出顶点在图中位置，要指出顶点在图中位置， 从图的逻辑结构的定义来看，图中的顶点之间是无从图的逻辑结构的定义来看，图中的顶点之间是
15、无序的（无法将图中顶点序的（无法将图中顶点 排列成一个线性序列），任何排列成一个线性序列），任何一个顶点都可被看成是第一个顶点一个顶点都可被看成是第一个顶点;同样，任一顶点的同样，任一顶点的邻邻 接点之间也不存在次序关系。接点之间也不存在次序关系。 为了操作方便，将图中顶点按任意的顺序排列起为了操作方便，将图中顶点按任意的顺序排列起 来，所谓来，所谓顶点在图中的位置顶点在图中的位置指的是该顶点在这个指的是该顶点在这个人为人为 的随意排列中的位置（或序号）。同理可对某个顶点的随意排列中的位置（或序号）。同理可对某个顶点的所有邻接点进行排队，在这个排队的所有邻接点进行排队，在这个排队 中自然形成了
16、第中自然形成了第一个或第一个或第k个邻接点。若某个顶点的邻接点的个数大于个邻接点。若某个顶点的邻接点的个数大于k则称第则称第k1个个 邻接点为第邻接点为第k个邻接点的下一个邻接点，个邻接点的下一个邻接点，而最后一个邻接点的下一个邻接点为而最后一个邻接点的下一个邻接点为“空空”。 数数 据据 结结 构构 测测 绘绘 学学 院院下面列出图的几种基本操作下面列出图的几种基本操作:LocateVex（G，v）顶点定位函数。确定顶点顶点定位函数。确定顶点v在图在图G中的位置。若图中无中的位置。若图中无此顶点此顶点,则函数值为零。则函数值为零。 GetVex（G，i）取顶点函数。求图取顶点函数。求图G中第
17、中第i个顶点。若个顶点。若i图图G中顶点数，中顶点数，则函数值为则函数值为“空空”。 FirstAdjVex（Q，v）求第一个邻接点函数。求图求第一个邻接点函数。求图G中顶点中顶点v的第一个邻接点。的第一个邻接点。若若v没有邻接点或图中无顶点没有邻接点或图中无顶点v，则函数值为，则函数值为“零零”。 NextAdjVex（G，v，w）求下一邻接点函数。已知求下一邻接点函数。已知w为图为图G中顶点中顶点v的某个邻接点，的某个邻接点，求项点求项点w的下一个邻接点。若的下一个邻接点。若w是是v的最后一个邻接点，的最后一个邻接点，则函数值为则函数值为“零零”。 数数 据据 结结 构构 测测 绘绘 学学
18、 院院InsertVex（G，u）插入顶点操作。在图插入顶点操作。在图c中增添一个顶点中增添一个顶点u为图为图G的第的第n+1个顶点，其中个顶点，其中n为插入之前图为插入之前图G中含顶点的个数。中含顶点的个数。 InsertArc（G，v，w）插入弧的操作。在图插入弧的操作。在图c中增添一条从顶点中增添一条从顶点V到顶点到顶点w的弧。的弧。 DeleteVex（G，v）删除顶点操作。从图删除顶点操作。从图G中删除顶点中删除顶点v以及所有与顶点以及所有与顶点v相关联的弧。相关联的弧。 DeleteArc（G，v，w）删除弧的操作。在图删除弧的操作。在图G中删去一条从顶点中删去一条从顶点v到顶点到
19、顶点w的弧。的弧。 Traverse(G) :遍历遍历数数 据据 结结 构构 测测 绘绘 学学 院院7.2 图的存贮结构图的存贮结构 图的结构比较复杂，任意两个顶点之间都可能存图的结构比较复杂，任意两个顶点之间都可能存在关系，因此无法以数据元素在存储区中的物理位置在关系，因此无法以数据元素在存储区中的物理位置来表示元素之间关系，来表示元素之间关系，即图没有顺序映象的存储结构即图没有顺序映象的存储结构用多重链表表示图是自然的事，它是一种最简单的链用多重链表表示图是自然的事，它是一种最简单的链式映象结构，即以一个由一个数据域和多个指针域组式映象结构，即以一个由一个数据域和多个指针域组成的结点表示图
20、中一个顶点，其中数据域存储该顶点成的结点表示图中一个顶点，其中数据域存储该顶点的信息，指针域存储指向其邻接点的指针。但是，由的信息，指针域存储指向其邻接点的指针。但是，由于图中各个结点的度数各不相同，最大度数和最小度于图中各个结点的度数各不相同，最大度数和最小度数可能相差很多，因此，若按数可能相差很多，因此，若按度数最大的顶点度数最大的顶点设计结设计结点结构，则会浪费很多存储单元。反之，若按每个顶点结构，则会浪费很多存储单元。反之，若按每个顶点自己的度数设计不同的结点结构，则会给操作带来点自己的度数设计不同的结点结构，则会给操作带来不便不便.数数 据据 结结 构构 测测 绘绘 学学 院院 多重
21、链表多重链表例例G12413例例15324G2V1V2 V4 V3 V1 V2 V4 V5 V3数数 据据 结结 构构 测测 绘绘 学学 院院 我们一般采用一些改进的方式来存储图，我们一般采用一些改进的方式来存储图，常用的常用的有邻接矩阵、邻接表和十字链表等。有邻接矩阵、邻接表和十字链表等。不管哪一种方式，它除了要存储图中各个顶不管哪一种方式，它除了要存储图中各个顶点本身的信息外，同时还要存储顶点与顶点点本身的信息外，同时还要存储顶点与顶点之间的所有关系（边的信息）。存储方法的之间的所有关系（边的信息）。存储方法的选择，取决于具体的应用。下面分别讨论之。选择，取决于具体的应用。下面分别讨论之。
22、 数数 据据 结结 构构 测测 绘绘 学学 院院7.2.1 邻接矩阵邻接矩阵1 图的邻接矩阵表示图的邻接矩阵表示(数组表示法数组表示法) 在邻接矩阵表示中，除了存放顶点本身信息在邻接矩阵表示中，除了存放顶点本身信息外，还用一个矩阵表示各个顶点之间的关系。若外，还用一个矩阵表示各个顶点之间的关系。若（i,j）E(G)或或i,jE(G),则矩阵中第则矩阵中第i行行 第第j列元素值为列元素值为1，否则为，否则为0 。图的邻接矩阵定义为：图的邻接矩阵定义为： 1 若（若（i,j）E(G)或或i,jE(G) Aij= 0 其它情形其它情形 数数 据据 结结 构构 测测 绘绘 学学 院院例如例如, 对图对
23、图7-8所示的无向图和有向图所示的无向图和有向图,它们它们的邻接矩阵见图的邻接矩阵见图7-9。 3 1 2 (a) 无 向 图G3 (b)有 向 图G4 图7-8 无 向 图G3及 有 向 图G4 1 2 4 3 0111101011011010 001100110 (a) G3的 邻 接 矩 阵 (b) G4的 邻 接 矩 图7-9 邻 接 矩 阵 表 示 数数 据据 结结 构构 测测 绘绘 学学 院院2 从无向图的邻接矩阵可以得出如下结论从无向图的邻接矩阵可以得出如下结论 （1）矩阵是对称的，可压缩存储（上（下）三角）矩阵是对称的，可压缩存储（上（下）三角）;（2）第）第i行或第行或第i
24、列中列中1的个数为顶点的个数为顶点i 的度的度;（3）矩阵中）矩阵中1的个数的一半为图中边的数目的个数的一半为图中边的数目;（4）很容易判断顶点）很容易判断顶点i 和顶点和顶点j之间是否有边相连之间是否有边相连(看矩阵中看矩阵中i行行j列值是否为列值是否为1)。数数 据据 结结 构构 测测 绘绘 学学 院院3 从有向图的邻接矩阵可以得出如下结论从有向图的邻接矩阵可以得出如下结论（1） 矩阵不一定是对称的矩阵不一定是对称的;（2） 第第i 行中行中1的个数为顶点的个数为顶点i 的出度的出度;（3） 第第i列中列中1的个数为顶点的个数为顶点 i的入度的入度;（4） 矩阵中矩阵中1的个数为图中弧的数
25、目的个数为图中弧的数目;（5） 很容易判断顶点很容易判断顶点i 和顶点和顶点j 是否有弧相连是否有弧相连.数数 据据 结结 构构 测测 绘绘 学学 院院4 网的邻接矩阵表示网的邻接矩阵表示 类似地可以定义网的邻接矩阵为：类似地可以定义网的邻接矩阵为： wij 若（若（i,j）E(G)或或i,jE(G)Aij= 其它情形其它情形 7493728421986316 (a) 网 G5 (b) 网 G5 的邻接矩阵示意图 图 8-10 网及邻接矩阵示意图 5 3 1 2 4 3 6 1 2 4 8 9 7 数数 据据 结结 构构 测测 绘绘 学学 院院 容易实现图的操作，如：求某顶点的度、容易实现图的
26、操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的判断顶点之间是否有边（弧）、找顶点的邻接点等等。邻接点等等。 n n个顶点需要个顶点需要n n* *n n个单元存储边个单元存储边( (弧弧););空空间效率为间效率为O(nO(n2 2) )。 对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。邻接矩阵法邻接矩阵法优点：优点：邻接矩阵法邻接矩阵法缺点：缺点：数数 据据 结结 构构 测测 绘绘 学学 院院5 图的邻接矩阵数据类型描述图的邻接矩阵数据类型描述图的邻接矩阵数据类型描述如下图的邻接矩阵数据类型描述如下:#define MAX 100 /* 最大顶点数最大顶点数*/ Elem
27、type VMAX; /* 存放顶点信息存放顶点信息,若顶点若顶点 除编号外无其它信息，则无需数组除编号外无其它信息，则无需数组*/ int AMAXMAX /*邻接矩阵邻接矩阵*/ 数数 据据 结结 构构 测测 绘绘 学学 院院6、邻接矩阵、邻接矩阵 的生成程序的生成程序#define INFINITE 9999void creatadj(int n,int e,int t) /*n为顶点数为顶点数,e为边数为边数,t为为14,分分别表示无向图、有向图、带权无向图、带权有向图别表示无向图、有向图、带权无向图、带权有向图*/ int i,j,k,w; for(i=1;i=n;i+) print
28、f(“输入第输入第%d顶点信息顶点信息”,i); vi=getchar(); for(i=1;i=n;i+) for(j=1;j2) Aij=INFINITE;/初始化初始化 else Aij=0; 数数 据据 结结 构构 测测 绘绘 学学 院院for(k=1;kn |jn) exit(0); if(t2)/带权图带权图 scanf(“%d”,&w); Aij=w; if(t=3) Aji=w;/带权无向图带权无向图 else Aij=1; /有向图有向图 if(t=1)Aji=1;/无向图无向图 数数 据据 结结 构构 测测 绘绘 学学 院院7.2.2 邻接表邻接表1 图的邻接表表示图的邻接
29、表表示 图的邻接表存储方法是一种顺序分配与链式分配图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法，它包括两部分：一部分是单链表，相结合的存储方法，它包括两部分：一部分是单链表，用来存放边的信息；另一部分是数组，主要用来存放用来存放边的信息；另一部分是数组，主要用来存放顶点本身的数据信息。顶点本身的数据信息。 vertex link next adjvex weight next 边结点边结点顶点结点顶点结点数数 据据 结结 构构 测测 绘绘 学学 院院 1 2 3 4 2 4 1 3 4 2 4 1 2 3 (a)无向图 G3 的邻接表 1 2 3 2 3 3 1 1 2 3 3
30、1 1 3 (b) 有向图G4的邻接表 (c) 有向图G4的逆邻接表 图7-11 邻接表示例 例如，无向图例如，无向图G3和有向图和有向图G4的邻接表见图的邻接表见图7-11所示所示 3 1 2 (a) 无向图 G3 (b)有向图 G4 图 7-8 无向图 G3 及有向图 G4 1 2 4 3 数数 据据 结结 构构 测测 绘绘 学学 院院2 从无向图的邻接表可以得到如下结论从无向图的邻接表可以得到如下结论 （1）第）第i 个链表中结点数目为顶点个链表中结点数目为顶点i的度；的度；（2）所有链表中结点数目的一半为图中边数；）所有链表中结点数目的一半为图中边数；（3）占用的存储单元数目为）占用的
31、存储单元数目为n+2e 。数数 据据 结结 构构 测测 绘绘 学学 院院3 从有向图的邻接表可以得到如下结论从有向图的邻接表可以得到如下结论（1）第）第i 个链表中结点数目为顶点个链表中结点数目为顶点i的出度；的出度；（2）所有链表中结点数目为图中弧数；）所有链表中结点数目为图中弧数；（3）占用的存储单元数目为）占用的存储单元数目为n+e 。从有向图的邻接表可知，不能求出顶点的入度。从有向图的邻接表可知，不能求出顶点的入度。为此，我们必须另外建立有向图的逆邻接表，为此，我们必须另外建立有向图的逆邻接表，以便求出每一个顶点的入度。逆邻接表在图以便求出每一个顶点的入度。逆邻接表在图7-11(c)中
32、已经给出，从该图中可知。有向图的逆中已经给出，从该图中可知。有向图的逆邻接表与邻接表类似，只是它是从入度考虑结邻接表与邻接表类似，只是它是从入度考虑结点，而不是从出度考虑结点。点，而不是从出度考虑结点。 数数 据据 结结 构构 测测 绘绘 学学 院院8064125当邻接表当邻接表的存储结的存储结构形成后，构形成后，图便唯一图便唯一确定！确定！数数 据据 结结 构构 测测 绘绘 学学 院院邻接表的邻接表的缺点：缺点：邻接表的邻接表的优点：优点：空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没
33、有邻接矩阵两结点对应的单链表，没有邻接矩阵方便。方便。数数 据据 结结 构构 测测 绘绘 学学 院院4 图的邻接表数据类型描述图的邻接表数据类型描述图的邻接表数据类型描述如下：图的邻接表数据类型描述如下：#define MAXN 50 /*MAXN表示图中最大顶点数表示图中最大顶点数*/typedef struct e_node /定义边结点的结构定义边结点的结构 int adjvex; int weight;struct e_node *next ;E_NODE;typedef struct v_node /定义邻接表的表头类型定义邻接表的表头类型 int vertex; /顶点信息顶点信息
34、 E_NODE *link;V_NODE;V_NODE headMAXN;数数 据据 结结 构构 测测 绘绘 学学 院院5.邻接表的生成程序邻接表的生成程序void creat_adj_list(V_NODE head,int t,int n) int n,i,w=1,v=1; E_NODE *p;for(i=1;i=0)&(w0) scanf(“%d%d”,&v,&w); if(vn)|(wn) continue; 数数 据据 结结 构构 测测 绘绘 学学 院院if(v0)&(w0) p=(E_NODE *)malloc(sizeof(E_NODE); p-adjvex=w; /插入边的结点
35、插入边的结点p-next=headv.link;headv.link=p;if(t=0) /无向图无向图 p=(E_NODE *)malloc(sizeof(E_NODE); p-adjvex=v; p-next=headw.link; headw.link=p;请注意上面的算法中，建立的请注意上面的算法中，建立的邻接表不是唯一的邻接表不是唯一的,与你从键盘与你从键盘输入边的顺序有关，输入的边输入边的顺序有关，输入的边的顺序不同，则得到的链表也的顺序不同，则得到的链表也不同。不同。数数 据据 结结 构构 测测 绘绘 学学 院院1. 1. 联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接
36、表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。2. 2. 区别：区别： 对于任一确定的无向图，邻接矩阵是唯一的（行列对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。与顶点编号无关）。 邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复而邻接表的空间复杂度为杂度为O(n+e)O(n+e)。3. 3. 用途：用途：邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e e接近接近n(n-n
37、(n-1)/2)1)/2)；而邻接表多用于稀疏图的存储（；而邻接表多用于稀疏图的存储（enen2 2) )数数 据据 结结 构构 测测 绘绘 学学 院院 7.2.3有向图的十字链表表示法有向图的十字链表表示法弧结点：弧结点：typedef struct arcnode int tailvex, headvex; /弧尾、弧头在表头数组中位置弧尾、弧头在表头数组中位置 struct arcnode *hlink；/指向弧头相同的下一条弧指向弧头相同的下一条弧 struct arcnode *tlink; /指向弧尾相同的下一条弧指向弧尾相同的下一条弧AD;Tailvex headvex hlin
38、k tlink 顶点结点：顶点结点：typedef struct dnode int data; /存与顶点有关信息存与顶点有关信息 struct arcnode *firstin；/指向以该顶点为弧头的第一个弧结点指向以该顶点为弧头的第一个弧结点 struct arcnode *firstout; /指向以该顶点为弧尾的第一个弧结点指向以该顶点为弧尾的第一个弧结点DD;DD gM; /g0不用不用data firstin firstout数数 据据 结结 构构 测测 绘绘 学学 院院例bdacab cd1234 1 3 1 2 3 4 3 1 4 3 4 2 4 1数数 据据 结结 构构 测
39、测 绘绘 学学 院院 7.2.4无向图的邻接多重表表示法无向图的邻接多重表表示法顶点结点：顶点结点：typedef struct dnode int data; /存与顶点有关的信息存与顶点有关的信息 struct node *firstedge; /指向第一条依附于该顶点的边指向第一条依附于该顶点的边DD;DD gaM; /ga0不用不用data firstedge边结点：边结点：typedef struct node int mark; /标志域标志域 int ivex, jvex; /该边依附的两个顶点在表头数组中位置该边依附的两个顶点在表头数组中位置 struct node *ilin
40、k, *jlink; /分别指向依附于分别指向依附于ivex和和jvex的下一条边的下一条边JD;mark ivex ilink jvex jlink数数 据据 结结 构构 测测 绘绘 学学 院院例aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 2数数 据据 结结 构构 测测 绘绘 学学 院院 7.3 图的遍历图的遍历 图的遍历是从某个顶点出发，沿着某条搜索路径对图的遍历是从某个顶点出发，沿着某条搜索路径对图中所有顶点各作一次访问。若给定的图是连通图，则图中所有顶点各作一次访问。若给定的图是连通图，则从图中任一顶点出发顺着边可以访问到该图中所有的顶从图中任一顶点出发
41、顺着边可以访问到该图中所有的顶点，但是，在图中有回路，从图中某一顶点出发访问图点，但是，在图中有回路，从图中某一顶点出发访问图中其它顶点时，可能又会回到出发点，而图中可能还剩中其它顶点时，可能又会回到出发点，而图中可能还剩余有顶点没有访问到，因此，图的遍历较树的遍历更复余有顶点没有访问到，因此，图的遍历较树的遍历更复杂。我们可以设置一个全局型标志数组杂。我们可以设置一个全局型标志数组visited来标志某来标志某个顶点是否被访问过，未访问的值为个顶点是否被访问过，未访问的值为0，访问过的值为，访问过的值为1。根据搜索路径的方向不同，图的遍历有两种方法：深度根据搜索路径的方向不同，图的遍历有两种
42、方法：深度优先搜索遍历（优先搜索遍历（DFS）和广度优先搜索遍历（）和广度优先搜索遍历（BFS）。）。它们对无向图和有向图都它们对无向图和有向图都 适用。适用。 数数 据据 结结 构构 测测 绘绘 学学 院院7.3.1深度优先搜索遍历深度优先搜索遍历1 深度优先搜索思想深度优先搜索思想 深度优先搜索遍历类似于树的先序遍历。假定给定图深度优先搜索遍历类似于树的先序遍历。假定给定图G的初态是所有顶点均未被访问过，在的初态是所有顶点均未被访问过，在G中任选一个顶中任选一个顶点点i作为遍历的初始点，则深度优先搜索遍历可定义如作为遍历的初始点，则深度优先搜索遍历可定义如下：下：(1) 首先访问顶点首先访
43、问顶点i，并将访问标记置为，并将访问标记置为visitedi=1；(2) 然后搜索与顶点然后搜索与顶点i有边相连的下一个顶点有边相连的下一个顶点j，若，若j未被未被访问过，则访问它，将访问过，则访问它，将j的访问标记置为，的访问标记置为，visitedj=1，然后从然后从j开始重复此过程，若开始重复此过程，若j已访问，再看与已访问，再看与i有边相有边相连的其它顶点；连的其它顶点；(3) 若与若与i有边相连的顶点都被访问过，则退回到前一有边相连的顶点都被访问过，则退回到前一个访问顶点重复刚才过程，直到图中所有顶点都被访个访问顶点重复刚才过程，直到图中所有顶点都被访问完为止。问完为止。数数 据据
44、结结 构构 测测 绘绘 学学 院院例如，对无向图例如，对无向图G7，从顶点，从顶点1出发的深度优先搜出发的深度优先搜索遍历序列可有多种，下面仅给出三种，其它可索遍历序列可有多种，下面仅给出三种，其它可作类似分析。作类似分析。在无向图在无向图G7中，从顶点中，从顶点1出发的深度优先搜索遍出发的深度优先搜索遍历序列举三种为：历序列举三种为： 1, 2, 4, 8, 5, 6, 3, 71, 2, 5, 8, 4, 7, 3, 61, 3, 6, 8, 7, 4, 2, 5 3 1 2 4 5 7 6 8 8-13 无 向 图 G 7 数数 据据 结结 构构 测测 绘绘 学学 院院 若图是连通的或强
45、连通的，则从图中某若图是连通的或强连通的，则从图中某一个顶点出发可以访问到图中所有顶点，一个顶点出发可以访问到图中所有顶点，否则只能访问到一部分顶点。否则只能访问到一部分顶点。 另外，从刚才写出的遍历结果可以看另外，从刚才写出的遍历结果可以看出，从某一个顶点出发的遍历结果是不唯出，从某一个顶点出发的遍历结果是不唯一的。但是一的。但是,若我们给定图的存贮结构若我们给定图的存贮结构,则从则从某一顶点出发的遍历结果应是唯一的。某一顶点出发的遍历结果应是唯一的。 数数 据据 结结 构构 测测 绘绘 学学 院院void dfs(Graph G ,vtx void dfs(Graph G ,vtx * *
46、 v v） / /* *从从v v出发深度优先遍历图出发深度优先遍历图g g* */ / visitvisit（v v）; ; visitedv = 1;visitedv = 1;w=FIRSTADJw=FIRSTADJ（G G，v v）; /w; /w为为v v的邻接点的邻接点 while (w!=0) while (w!=0) / /当邻接点存在时当邻接点存在时 if (!visitedw) dfs if (!visitedw) dfs （G G，w w）; ; w= NEXTADJw= NEXTADJ（G G，v v，w w）/ /找下一邻接找下一邻接点点 数数 据据 结结 构构 测测
47、绘绘 学学 院院(1) 用邻接矩阵实现图的深度优先搜索用邻接矩阵实现图的深度优先搜索 以下页中无向图以下页中无向图G7 为例，来说明算法的实现，为例，来说明算法的实现，G7的邻接矩阵见图的邻接矩阵见图7-14。分析上述过程，在遍历图时，对图中每个顶点至分析上述过程，在遍历图时，对图中每个顶点至多调用一次多调用一次dfsdfs过程，因为一旦某个过程，因为一旦某个 顶点被标志顶点被标志成已被访问，就不再从它出发进行搜索。因此，成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结的过程
48、。其耗费的时间则取决于所采用的存储结构。构。数数 据据 结结 构构 测测 绘绘 学学 院院0111100010000100100001001000001010000010011000010001100100000110 图 7-14 无向图 G7 的邻接矩阵 3 1 2 4 5 7 6 8 7-13 无向图 G7 数数 据据 结结 构构 测测 绘绘 学学 院院算法描述为下面形式：算法描述为下面形式：void dfs (int i) / 从顶点从顶点i 出发遍历出发遍历 int j; visit(i); /输出访问顶点输出访问顶点 visitedi=1; /全局数组访问标记置全局数组访问标记置1
49、表示已经访问表示已经访问 for(j=1; jnext ) if (!visitedp-adjvex) dfs1(p-adjvex); ;而当以邻接表作图的存储结构时，找邻接点所需时间而当以邻接表作图的存储结构时，找邻接点所需时间为为O O（e e），其中），其中e e为无向图中边的数或有向图中弧的为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复遍历图的时间复 杂度为杂度为O O（n ne e）。）。 数数 据据 结结 构构 测测 绘绘 学学 院院用图用图7-16，可以描述从顶点，可以描述从顶点7出发的深度
50、优先搜索遍出发的深度优先搜索遍历示意图，见图历示意图，见图7-17,其中实线表示下一层递归，虚其中实线表示下一层递归，虚线表示递归返回，箭头旁边数字表示调用的步骤。线表示递归返回，箭头旁边数字表示调用的步骤。于是，从顶点于是，从顶点7出发的深度优先搜索遍历序列，从图出发的深度优先搜索遍历序列，从图7-17中可得出为中可得出为 7， 3， 1， 2， 4， 8， 5， 6。从其。从其它顶点出发的深度优先搜索序列，请读者自已写出。它顶点出发的深度优先搜索序列，请读者自已写出。 DFS1(7) DFS1(3) DFS1(1) DFS1(2) DFS1(4) DFS1(8) DFS1(5) DFS1(
