[理学]数据结构第七章 图ppt课件

1、第7章 图本章中介绍以下主要内容：l图的定义l图的存储构造l图的遍历操作l图的几个典型问题第第7 7章章 图图 图图Graph是一种比线性表和树更为复杂的数是一种比线性表和树更为复杂的数据构造。据构造。 线性构造线性构造：是研究数据元素之间的一对一关系。：是研究数据元素之间的一对一关系。在这种构造中，除第一个和最后一个元素外，任何一在这种构造中，除第一个和最后一个元素外，任何一个元素都有唯一的一个直接前驱和直接后继。个元素都有唯一的一个直接前驱和直接后继。 树构造树构造：是研究数据元素之间的一对多的关系。：是研究数据元素之间的一对多的关系。在这种构造中，每个元素对下在这种构造中，每个元素对下层

2、层可以有可以有0个或多个或多个元素相联络，对上个元素相联络，对上层层只有唯一的一个元素相关，只有唯一的一个元素相关，数据元素之间有明显的层次关系。数据元素之间有明显的层次关系。 图构造图构造：是研究数据元素之间的多对多：是研究数据元素之间的多对多的关系。在这种构造中，任意两个元素之间可的关系。在这种构造中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相关。图中任意元素之间都可能相关。 图的应用极为广泛，已渗入到诸如语言图的应用极为广泛，已渗入到诸如语言学、逻辑学、物理、化学、电讯、计算机科学学、逻辑学、物理、化学、

3、电讯、计算机科学以及数学的其它分支。以及数学的其它分支。第第7章章 图图7.1 图的根本概念图的根本概念7.1.1 图的定义和术语图的定义和术语 一个图一个图G定义为一个偶对定义为一个偶对V,E ，记为，记为G=V,E 。其中：其中： V是是顶点顶点Vertex的非空有限集合，记为的非空有限集合，记为VG；E是无序集是无序集V&V的一个子集，记为的一个子集，记为EG ，其元素是图的，其元素是图的弧弧Arc。 将顶点集合为空的图称为空图。其形式化定义为：将顶点集合为空的图称为空图。其形式化定义为：G=V ，EV=v|v data objectE=| v,w Vpv,wPv,w表示从顶点表

4、示从顶点v到顶点到顶点w有一条直接通路。有一条直接通路。 弧弧Arc ：表示两个顶点表示两个顶点v和和w之间存在一个之间存在一个关系，用顶点偶对关系，用顶点偶对表示。通常根据图的顶点偶表示。通常根据图的顶点偶对将图分为有向图和无向图。对将图分为有向图和无向图。 有向图有向图Digraph： 假设图假设图G的关系集合的关系集合EG中，顶点偶对中，顶点偶对的的v和和w之间是之间是有序有序的的，称，称图图G是有向图。是有向图。 在有向图中，假设在有向图中，假设 EG ，表示从顶点，表示从顶点v到顶点到顶点w有一条有一条弧弧。 其中：其中：v称为称为弧尾弧尾tail或或始点始点initial node

5、，w称为称为弧头弧头head或或终点终点terminal node 。定义和术语定义和术语2 2 无向图无向图Undigraph： 假设图假设图G的关系集合的关系集合EG中，顶点偶对中，顶点偶对的的v和和w之间是之间是无序无序的，的，称图称图G是无向图。是无向图。 在无向图中，假设在无向图中，假设 EG ，有，有 EG ，即，即EG是对称，那么用无序是对称，那么用无序对对v,w 表示表示v和和w之间的一条之间的一条边边Edge，因，因此此v,w 和和w,v代表的是同一条边。代表的是同一条边。定义和术语定义和术语3 3 例例1：设有有向图：设有有向图G1和无向图和无向图G2，形式化定义，形式化定

6、义：G1=V1 ，E1V1=a,b,c,d,eE1=, , ,G2=V2 ，E2V2=a,b,c,dE2=a,b, a,c, a,d, b,d, b,c, c,dabcd(b) 无向图无向图G2 (a) 有向图有向图G1 acbde 完全无向图完全无向图：对于无向图，假设图中顶点数为对于无向图，假设图中顶点数为n ，用用e表示边的数目，那么表示边的数目，那么e 0，nn-1/2 。具有。具有nn-1/2条边的无向图称为完全无向图。条边的无向图称为完全无向图。 完全无向图另外的定义是：完全无向图另外的定义是： 对于无向图对于无向图G=V，E，假设，假设 vi，vj V ，当，当vivj时，有时，

7、有vi ,vj E，即，即图中任意两个不同的顶点图中任意两个不同的顶点间都有一条无向边间都有一条无向边，这样的无向图称为，这样的无向图称为完全无向图完全无向图。定义和术语定义和术语4 4 完全有向图完全有向图：对于有向图，假设图中顶点数为：对于有向图，假设图中顶点数为n ，用用e表示弧的数目，那么表示弧的数目，那么e 0，nn-1 。具有。具有nn-1条边的有向图称为完全有向图。条边的有向图称为完全有向图。 完全有向图另外的定义是：完全有向图另外的定义是： 对于有向图对于有向图G=V，E，假设，假设 vi，vj V ，当，当vi vj时，有时，有 E E ，即，即图中任意图中任意两个不同的顶点

8、间都有一条弧两个不同的顶点间都有一条弧，这样的有向图称为，这样的有向图称为完完全有向图全有向图。定义和术语定义和术语5 5 有很少边或弧的图有很少边或弧的图enn的图称为的图称为稀疏图稀疏图，反之称为反之称为稠密图稠密图。 权权Weight：与图的边和弧相关的数。权可以：与图的边和弧相关的数。权可以表示从一个顶点到另一个顶点的间隔表示从一个顶点到另一个顶点的间隔 或消耗。或消耗。 子图和生成子图子图和生成子图：设有图：设有图G=V，E和和G=V，E，假设，假设V V且且E E ，那么称图，那么称图G是是G的的子图子图；假；假设设V=V且且E E，那么称图，那么称图G是是G的一个的一个生成子图生

9、成子图。定义和术语定义和术语6 6 顶点的邻接顶点的邻接Adjacent：对于无向图对于无向图G=V，E，假设边假设边v,w E，那么称顶点，那么称顶点v和和w 互为互为邻接点邻接点，即，即v和和w相相邻接。边邻接。边v,w依附依附incident与顶点与顶点v和和w 。 对于有向图对于有向图G=V ，E，假设有向弧，假设有向弧 E，那么，那么称顶点称顶点v “邻接到邻接到顶点顶点w，顶点，顶点w “邻接自邻接自顶点顶点v ，弧，弧 与顶点与顶点v和和w “相关联相关联 。 顶点的度、入度、出度顶点的度、入度、出度：对于无向图对于无向图G=V，E， vi V，图，图G中中依附于于vi的边的数目

10、称为顶点的边的数目称为顶点vi的的度度degree，记为记为TDvi。定义和术语定义和术语7 7 显然，在无向图中，所有顶点度的和是图中边的显然，在无向图中，所有顶点度的和是图中边的2倍。倍。 即即 TDvi=2e i=1,2, ,n，e为图的边为图的边数数。 对有向图对有向图G=V，E，假设，假设 vi V ，图，图G中中以以vi作为起点作为起点的有向边的有向边弧弧的数目称为顶点的数目称为顶点vi的的出度出度Outdegree，记为，记为ODvi ；以以vi作为终点作为终点的有的有向边向边弧弧的数目称为顶点的数目称为顶点vi的的入度入度Indegree，记，记为为IDvi 。顶点。顶点vi的

11、的出度出度与与入度入度之和称为之和称为vi的的度度，记，记为为TDvi 。即。即 TDvi=ODvi+IDvi 定义和术语定义和术语8 8 途径途径Path、途径长度、回路、途径长度、回路Cycle ：对：对无向图无向图G=V，E，假设从顶点，假设从顶点vi经过假设干条边经过假设干条边能到达能到达vj，称顶点，称顶点vi和和vj是是连通连通的，又称顶点的，又称顶点vi到到vj有有途径途径。 对有向图对有向图G=V，E，从顶点，从顶点vi到到vj有有有向途有向途径径，指的是从顶点，指的是从顶点vi经过假设干条有向边经过假设干条有向边弧弧能到能到达达vj。 或或途径途径是图是图G中连接两顶点间所经

12、过的顶点序列。中连接两顶点间所经过的顶点序列。Path=vi0vi1vim ，vij V且且vij-1, vij E j=1,2, ,m定义和术语定义和术语9 9 途径上边或有向边途径上边或有向边弧弧的数目称为该途径的的数目称为该途径的长长度度。 在一条途径中，假设在一条途径中，假设没有重复一样没有重复一样的顶点，该途的顶点，该途径称为径称为简单途径简单途径；第一个顶点和最后一个顶点一样的；第一个顶点和最后一个顶点一样的途径称为途径称为回路回路环环；在一个回路中，假设除第一个；在一个回路中，假设除第一个与最后一个顶点外，其余顶点不重复出现的回路称为与最后一个顶点外，其余顶点不重复出现的回路称为

13、简单回路简单回路简单环简单环。定义和术语定义和术语1010 连通图、图的连通分量连通图、图的连通分量：对无向图：对无向图G=V，E，假设假设 vi ，vj V，vi和和vj都是连通的，那么称图都是连通的，那么称图G是是连连通图通图，否那么称为，否那么称为非连通图非连通图。假设。假设G是非连通图，那么是非连通图，那么极大的连通子图极大的连通子图称为称为G的的连通分量连通分量。 对有向图对有向图G=V，E，假设，假设 vi ，vj V，都有，都有以以vi为起点为起点， vj 为终点为终点以及以以及以vj为起点，为起点，vi为终点的有为终点的有向途径，称图向途径，称图G是是强连通图强连通图，否那么称

14、为，否那么称为非强连通图非强连通图。假设假设G是非强连通图，那么是非强连通图，那么极大的强连通子图极大的强连通子图称为称为G的的强连通分量强连通分量。 “极大极大的含义：指的是对子图再增加图的含义：指的是对子图再增加图G中的其中的其它顶点，子图就不再连通。它顶点，子图就不再连通。定义和术语定义和术语1111 生成树、生成森林生成树、生成森林：一个连通图一个连通图无向图无向图的的生成树是一个极小连通子图，它生成树是一个极小连通子图，它含有图中全部含有图中全部n个顶点个顶点和只有足以构成一棵树的和只有足以构成一棵树的n-1条边条边，称为图的，称为图的生成树生成树，如图如图7-2所示。所示。 关于无

15、向图的生成树的几个结论：关于无向图的生成树的几个结论： 一棵有一棵有n个顶点的生成树有且仅有个顶点的生成树有且仅有n-1条边；条边； 假如一个图有假如一个图有n个顶点和小于个顶点和小于n-1条边，那么是非条边，那么是非连通图；连通图；adbc图图7-2 图图G2的一棵生成树的一棵生成树 假如多于假如多于n-1条边，那么一条边，那么一定有环；定有环； 有有n-1条边的图不一定是生条边的图不一定是生成树。成树。 有向图的有向图的生成森林生成森林是这样一个子图，由假设干棵是这样一个子图，由假设干棵有有向树向树组成，含有图中全部顶点。组成，含有图中全部顶点。 有向树有向树是只有一个顶点的入度为是只有一

16、个顶点的入度为0 ，其余顶点的入，其余顶点的入度均为度均为1的有向图，如图的有向图，如图7-3所示。所示。 网网：每个边每个边或弧或弧都附加一个权值的图，称为都附加一个权值的图，称为带权图带权图。带权的连通图带权的连通图包括弱连通的有向图包括弱连通的有向图称为称为网网或网络或网络。网络是工程上常用的一个概念，用来表示一个。网络是工程上常用的一个概念，用来表示一个工程或某种流程，如图工程或某种流程，如图7-4所示。所示。图图7-3 有向图及其生成森林有向图及其生成森林abcdea 有向图有向图b 生成森林生成森林acbde354126abcde3图图7-4 带权有向图带权有向图7.1.2 图的抽

17、象数据类型定义图的抽象数据类型定义 图是一种数据构造，加上一组根本操作就构成了图图是一种数据构造，加上一组根本操作就构成了图的抽象数据类型。的抽象数据类型。 图的抽象数据类型定义如下：图的抽象数据类型定义如下：ADT Graph数据对象数据对象V：具有一样特性的数据元素集合具有一样特性的数据元素集合，称为顶点集称为顶点集。数据关系数据关系R：R=VRVR=| v,w Vpv,w ，表表示示 从从v到到w的弧，的弧，Pv,w定定义了弧义了弧的信息的信息 根本操作根本操作P： Create_Graph ： 图的创立操作图的创立操作。 初始条件：无。初始条件：无。 操作结果：生成一个没有顶点的空图操

18、作结果：生成一个没有顶点的空图G。GetVexG, v ： 求图中的顶点求图中的顶点v的值。的值。初始条件：图初始条件：图G存在，存在，v是图中的一个顶点。是图中的一个顶点。操作结果：生成一个没有顶点的空图操作结果：生成一个没有顶点的空图G。 DFStraverG,V：从：从v出发对图出发对图G深度优先遍历深度优先遍历。 初始条件：图初始条件：图G存在。存在。 操作结果：对图操作结果：对图G深度优先遍历，每个顶点访问且只访问深度优先遍历，每个顶点访问且只访问一次。一次。 ADT Graph7.2 7.2 图的存储构造图的存储构造 图的存储构造比较复杂，其复杂性主要表如今：图的存储构造比较复杂，

19、其复杂性主要表如今： 任意顶点之间可能存在联络，无法以数据元素任意顶点之间可能存在联络，无法以数据元素在存储区中的在存储区中的物理位置来表示元素之间的关系物理位置来表示元素之间的关系。 图中顶点的度不一样，有的可能相差很大，假图中顶点的度不一样，有的可能相差很大，假设按度数最大的顶点设计构造，那么会浪费很多存设按度数最大的顶点设计构造，那么会浪费很多存储单元，反之按每个顶点自己的度设计不同的构造，储单元，反之按每个顶点自己的度设计不同的构造，又会影响操作。又会影响操作。 图的常用的存储构造有：图的常用的存储构造有：邻接矩阵邻接矩阵、邻接链表邻接链表、十字链表十字链表、邻接多重表邻接多重表和和边

20、表边表。7.2.1 邻接矩阵邻接矩阵数组数组表表示法示法 根本思想根本思想：对于有对于有n个顶点的图，用一维数组个顶点的图，用一维数组vexsn存储顶点信息，用二维数组存储顶点信息，用二维数组Ann存储顶存储顶点之间关系的信息。该二维数组称为点之间关系的信息。该二维数组称为邻接矩阵邻接矩阵。在。在邻接矩阵中，以顶点在邻接矩阵中，以顶点在vexs数组中的下标代表顶点，数组中的下标代表顶点，邻接矩阵中的元素邻接矩阵中的元素Aij存放的是顶点存放的是顶点i到顶点到顶点j之间之间关系的信息。关系的信息。 1 无向图无向图-无权图的邻接矩阵无权图的邻接矩阵 无向无权图无向无权图G=V，E有有nn1个顶点

21、，其邻接矩阵个顶点，其邻接矩阵是是n阶对称方阵，如图阶对称方阵，如图7-5所示。其元素的定义如下：所示。其元素的定义如下：(a) 无向图无向图 abcd图图7-5 无向无权图的数组存储无向无权图的数组存储(b) 顶点矩阵顶点矩阵vexsabcd0 1 1 11 0 1 11 1 0 11 1 1 0(c) 邻接矩阵邻接矩阵1 若若(vi , vj) E，即，即vi , vj邻接邻接0 若若(vi , vj) E，即，即vi , vj不邻接不邻接Aij= 1 无向图无向图-带权图的邻接矩阵带权图的邻接矩阵 无向带权图无向带权图G=V，E 的邻接矩阵如图的邻接矩阵如图7-6所所示。其元素的定义如下

22、：示。其元素的定义如下：(a) 带权无向图带权无向图 (b) 顶点矩阵顶点矩阵图图7-6 无向带权图的数组存储无向带权图的数组存储(c) 邻接矩阵邻接矩阵354126abcde3vexsabcde 6 2 6 3 4 32 3 1 4 3 5 3 5 Wij 若若(vi , vj) E，即，即vi , vj邻接，权值为邻接，权值为wij 若若(vi , vj) E，即，即vi , vj不邻接时不邻接时Aij= 无向图邻接矩阵的特性：无向图邻接矩阵的特性： 邻接矩阵是邻接矩阵是对称方阵对称方阵； 对于顶点对于顶点vi，其，其度数度数是第是第i行的非行的非0元素的个数；元素的个数； 无向图的无向图

23、的边数边数是上是上或下或下三角形矩阵中非三角形矩阵中非0元素个数。元素个数。 2 有向图有向图- 无权图的邻接矩阵无权图的邻接矩阵 假设有向无权图假设有向无权图G=V，E有有nn1个顶点，个顶点，那么其邻接矩阵是那么其邻接矩阵是n阶对称方阵阶对称方阵，如图，如图7-7所示。元素定所示。元素定义如下：义如下：1 若若 E，从，从vi到到vj有弧有弧Aij=0 若若 E 从从vi到到vj 没有弧没有弧(a) 有向图有向图acbde图图7-7 有向无权图的数组存储有向无权图的数组存储(b) 顶点矩阵顶点矩阵vexsabcde(c) 邻接矩阵邻接矩阵0 1 1 0 10 0 0 0 00 0 0 1

24、11 1 0 0 00 0 0 1 0 2 有向图有向图- 带权图的邻接矩阵带权图的邻接矩阵 有向带权图有向带权图G=V，E的邻接矩阵如图的邻接矩阵如图7-8所示。所示。其元素的定义如下：其元素的定义如下：wij 若若 E，即，即vi , vj邻接，权值为邻接，权值为wij 若若 E，即，即vi , vj不邻接时不邻接时Aij=图图7-8 带权有向图的数组存储带权有向图的数组存储(b) 顶点矩阵顶点矩阵vexsabcde(c) 邻接矩阵邻接矩阵 6 2 3 3 1 4 5 (a) 带权有向图带权有向图 354126abcde3 有向图邻接矩阵的特性：有向图邻接矩阵的特性： 对于顶点对于顶点vi

25、，第，第i行的非行的非0元素的个数是其元素的个数是其出度出度ODvi；第；第i列的非列的非0元素的个数是其元素的个数是其入度入度IDvi 。 邻接矩阵中非邻接矩阵中非0元素的个数就是图的弧的数目。元素的个数就是图的弧的数目。 3 图的邻接矩阵的操作图的邻接矩阵的操作 图的邻接矩阵的实现比较容易，定义两个数组分图的邻接矩阵的实现比较容易，定义两个数组分别存储别存储顶点信息顶点信息数据元素数据元素和和边或弧的信息边或弧的信息数据数据元素之间的关系元素之间的关系 。其。其存储构造形式定义存储构造形式定义如下：如下：#define INFINITY MAX_VAL /* 最大值最大值 */ /* 根据

26、图的权值类型，分别定义为最大整数或实数根据图的权值类型，分别定义为最大整数或实数 */#define MAX_VEX 30 /* 最大顶点数目最大顶点数目 */typedef enum DG, AG, WDG,WAG GraphKind ; /* 有向图，无向图，带权有向图，带权无向图有向图，无向图，带权有向图，带权无向图 */typedef struct ArcCell VRType adj ; /*弧或边两顶点关系弧或边两顶点关系,1或或0或权值或无穷或权值或无穷 */InfoType *Info ; /* 弧或边的其它信息弧或边的其它信息 */ArcCell ; /* 弧或边的构造定义弧

27、或边的构造定义 */typedef struct GraphKind kind ; /* 图的种类标志图的种类标志 */int vexnum , arcnum ; /* 图的当前顶点数和弧数图的当前顶点数和弧数 */VexType vexsMAX_VEX ; /* 顶点向量顶点向量 */ArcCell arcsMAX_VEXMAX_VEX;MGraph ; /* 图的构造定义图的构造定义 */ 利用上述定义的数据构造，可以方便地实利用上述定义的数据构造，可以方便地实现图的各种操作。现图的各种操作。1 图的创立图的创立AdjGraph *Create_GraphMGraph * G printf

28、“请输入图的种类标志：请输入图的种类标志： ;scanf“%d, &G-kind ;G-vexnum=0 ; /* 初始化顶点个数初始化顶点个数 */returnG ; 2 图的顶点定图的顶点定位位 图的顶点定位操作实际上是确定一个顶点在图的顶点定位操作实际上是确定一个顶点在vexs数组中的位置数组中的位置下标下标 ，其过程完全等同于在顺序，其过程完全等同于在顺序存储的线性表中查找一个数据元素。存储的线性表中查找一个数据元素。int LocateVexMGraph *G , VexType *vp int k ; for k=0 ; kvexnum ; k+ if G-vexsk=*v

29、p returnk ; return-1 ; /* 图中无此顶点图中无此顶点 */ 3 向图中增加顶点向图中增加顶点 向图中增加一个顶点的操作，类似在顺序存储的向图中增加一个顶点的操作，类似在顺序存储的线性表的末尾增加一个数据元素。线性表的末尾增加一个数据元素。int AddVertexMGraph *G , VexType *vp int k , j ;if G-vexnum=MAX_VEX printf“Vertex Overflow !n ; return-1 ; if LocateVexG , vp!=-1 printf“Vertex has existed !n ; return-1

30、 ; k=G-vexnum ; G-vexsG-vexnum+=*vp ;if G-kind=DG|G-kind=AG for j=0 ; jvexnum ; j+G-adjjk.ArcVal=G-adjkj.ArcVal=0 ; /* 是不带权的有向图或无向图是不带权的有向图或无向图 */elsefor j=0 ; jvexnum ; j+ G-adjjk.ArcVal=INFINITY ; G-adjkj.ArcVal=INFINITY ; /* 是带权的有向图或无向图是带权的有向图或无向图 */returnk ; 4 向图中增加一条弧向图中增加一条弧 根据给定的弧或边所依附的顶点，修改邻

31、接矩阵根据给定的弧或边所依附的顶点，修改邻接矩阵中所对应的数组元素。中所对应的数组元素。 int AddArcMGraph *G , ArcType *arc int k , j ;k=LocateVexG , &arc-vex1 ;j=LocateVexG , &arc-vex1 ;if k=-1|j=-1 printf“Arcs Vertex do not existed !n ;return-1 ;if G-kind=DG|G-kind=WDG G-adjkj.ArcVal=arc-ArcVal;G-adjkj.ArcInfo=arc-ArcInfo ; /* 是有向图或

32、带权的有向图是有向图或带权的有向图*/else G-adjkj.ArcVal=arc-ArcVal ;G-adjjk.ArcVal=arc-ArcVal ;G-adjkj.ArcInfo=arc-ArcInfo ;G-adjjk.ArcInfo=arc-ArcInfo ; /* 是无向图或带权的无向图是无向图或带权的无向图,需对称赋值需对称赋值 */return1 ; 7.2.2 邻接链表法邻接链表法 根本思想：根本思想：对图的每个顶点建立一个单链对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。每一个单链表设

33、一个表头结点。 第第i个单链表表示依附于顶点个单链表表示依附于顶点Vi的边的边对对有向图是以顶点有向图是以顶点Vi为头或尾的弧为头或尾的弧。 1 结点构造与邻接链表例如结点构造与邻接链表例如 链表中的结点称为链表中的结点称为表结点表结点，每个结点由三个域组成，如图，每个结点由三个域组成，如图7-9a所示。其中所示。其中邻接点域邻接点域adjvex指示与顶点指示与顶点Vi邻接的邻接的顶点在图中的位置顶点在图中的位置顶点编号顶点编号，链域链域nextarc指向下一个指向下一个与顶点与顶点Vi邻接的表结点，邻接的表结点，数据域数据域info存储和边或弧相关的信存储和边或弧相关的信息，如权值等。对于无

34、权图，假如没有与边相关的其他信息，可息，如权值等。对于无权图，假如没有与边相关的其他信息，可省略此域。省略此域。 每个链表设一个表头结点每个链表设一个表头结点称为称为顶点结点顶点结点，由两个域组成，由两个域组成，如图如图7-9b所示。所示。链域链域firstarc指向链表中的第一个结点，指向链表中的第一个结点，数据域数据域data 存储顶点名或其他信息。存储顶点名或其他信息。adjvex info nextarc表结点表结点：data firstarc顶点结点顶点结点：图图7-9 邻接链表结点结构邻接链表结点结构 用邻接链表存储图时，对无向图，其邻接链表是唯用邻接链表存储图时，对无向图，其邻接

35、链表是唯一的，如图一的，如图7-10所示；对有向图，其邻接链表有两种形所示；对有向图，其邻接链表有两种形式，如图式，如图7-11所示。所示。图图7-10 无向图及其邻接链表无向图及其邻接链表v1v2v3v4v501234MAX_VEX-1v1 v2v3 v4 v5 213 02 0314 204 23 (a) 有向图有向图v1v2v3v4v513 014 2 3 01234MAX_VEX-1v1 2 v2 0 v3 3v4 1 v5 1 (b) 正邻接链表，出度直观正邻接链表，出度直观2 02 2 01234MAX_VEX-1v1 1v2 2v3 1v4 2 v5 1 3 04 (c) 逆邻接

36、链表，入度直观逆邻接链表，入度直观图图7-11 有向图及其邻接链表有向图及其邻接链表构造体定义，详见P163 邻接表法的特点邻接表法的特点 表头向量中每个分量就是一个单链表的头结点，分量个数就是图中表头向量中每个分量就是一个单链表的头结点，分量个数就是图中的顶点数目；的顶点数目； 在边或弧稀疏的条件下，用邻接表表示比用邻接矩阵表示节省存储在边或弧稀疏的条件下，用邻接表表示比用邻接矩阵表示节省存储空间；空间； 在无向图，顶点在无向图，顶点Vi的度是第的度是第i个链表的结点数；个链表的结点数； 对对有向图有向图可以建立可以建立正邻接表正邻接表或或逆邻接表逆邻接表。正邻接表是以顶点。正邻接表是以顶点

37、Vi为出为出度度即为弧的起点即为弧的起点而建立的邻接表；逆邻接表是以顶点而建立的邻接表；逆邻接表是以顶点Vi为入度为入度即即为弧的终点为弧的终点而建立的邻接表；而建立的邻接表； 在有向图中，第在有向图中，第i个链表中的结点数是顶点个链表中的结点数是顶点Vi的出的出 或入或入度；求入度；求入 或出或出度，须遍历整个邻接表；度，须遍历整个邻接表； 在邻接表上容易找出任一顶点的第一个邻接点和下一个邻接点；在邻接表上容易找出任一顶点的第一个邻接点和下一个邻接点；7.2.3 十字链表法十字链表法 十字链表十字链表Orthogonal List是有向图的另一种是有向图的另一种链式存储构造，是将有向图的正邻

38、接表和逆邻接表结合链式存储构造，是将有向图的正邻接表和逆邻接表结合起来得到的一种链表。起来得到的一种链表。 在这种构造中，每条弧的弧头结点和弧尾结点都在这种构造中，每条弧的弧头结点和弧尾结点都存放在链表中，并将存放在链表中，并将弧结点弧结点分别组织到分别组织到以弧尾结点为头以弧尾结点为头顶点顶点结点结点和和以弧头结点为头以弧头结点为头顶点顶点结点结点的链表中。的链表中。这种构造的结点逻辑构造如图这种构造的结点逻辑构造如图7-12所示。所示。弧结点弧结点tailvex headvex info hlink tlink顶点结点顶点结点Data firstin firstout图图7-12 十字链表

39、结点结构十字链表结点结构 data域：存储和顶点相关的信息；域：存储和顶点相关的信息； 指针域指针域firstin：指向：指向以该顶点为弧头以该顶点为弧头的第一条的第一条弧所对应的弧结点；弧所对应的弧结点； 指针域指针域firstout：指向：指向以该顶点为弧尾以该顶点为弧尾的第一条的第一条弧所对应的弧结点；弧所对应的弧结点； 尾域尾域tailvex：指示弧尾顶点在图中的位置；：指示弧尾顶点在图中的位置； 头域头域headvex：指示弧头顶点在图中的位置；：指示弧头顶点在图中的位置； 指针域指针域hlink：指向弧头一样的下一条弧；：指向弧头一样的下一条弧； 指针域指针域tlink：指向弧尾一

40、样的下一条弧；：指向弧尾一样的下一条弧； Info域：指向该弧的相关信息；域：指向该弧的相关信息；V0V1V2V30 10 2 2 02 3 3 0 3 1 3 2 0213V0V1 V2V3图图7-13 有向图的十字链表结构有向图的十字链表结构有向图的十字链表构造构造体定义，详见P1657.2.4 邻接多重表邻接多重表 邻接多重表邻接多重表Adjacency Multilist是无向图的另一种是无向图的另一种链式存储构造。链式存储构造。 邻接表是无向图的一种有效的存储构造，在无向图的邻邻接表是无向图的一种有效的存储构造，在无向图的邻接表中，一条边接表中，一条边v,w的两个表结点分别初选在以的

41、两个表结点分别初选在以v和和w为为头结点的链表中，很容易求得顶点和边的信息，但在涉及到边头结点的链表中，很容易求得顶点和边的信息，但在涉及到边的操作会带来不便。的操作会带来不便。 邻接多重表的构造和十字链表类似，邻接多重表的构造和十字链表类似，每条边用一个结点每条边用一个结点表示表示；邻接多重表中的顶点结点构造与邻接表中的完全一样，；邻接多重表中的顶点结点构造与邻接表中的完全一样，而表结点包括六个域如图而表结点包括六个域如图7-14所示。所示。data firstedge顶点结点顶点结点图图7-14 邻接多重表的结点结构邻接多重表的结点结构表结点表结点mark ivex ilink jvex

42、jlink info Data域：存储和顶点相关的信息；域：存储和顶点相关的信息； 指针域指针域firstedge：指向依附于该顶点的第一条边：指向依附于该顶点的第一条边所对应的表结点；所对应的表结点； 标志域标志域mark：用以标识该条边是否被访问过；：用以标识该条边是否被访问过； ivex和和jvex域：分别保存该边所依附的两个顶点域：分别保存该边所依附的两个顶点在图中的位置；在图中的位置； info域：保存该边的相关信息；域：保存该边的相关信息； 指针域指针域ilink：指向下一条依附于顶点：指向下一条依附于顶点ivex的边；的边； 指针域指针域jlink：指向下一条依附于顶点：指向下一

43、条依附于顶点jvex的边；的边； 邻接多重表与邻接表的区别邻接多重表与邻接表的区别： 后者的同一条边用两个表结点表示，而前者只用后者的同一条边用两个表结点表示，而前者只用一个表结点表示一个表结点表示；除标志域外，邻接多重表与邻接表除标志域外，邻接多重表与邻接表表达的信息是一样的，因此，操作的实现也根本相似。表达的信息是一样的，因此，操作的实现也根本相似。图图7-15 无向图及其多重邻接链表无向图及其多重邻接链表v1v2v3v4v1v2v3v40123 0 1 0 2 2 1 2 3 0 3构造体定义，详见P166-1677.3 图的遍历图的遍历 图的遍历图的遍历Travering Graph：

44、从图的某一顶点出发，访：从图的某一顶点出发，访遍图中的其余顶点，且每个顶点仅被访问一次。图的遍历算法是遍图中的其余顶点，且每个顶点仅被访问一次。图的遍历算法是各种图的操作的根底。各种图的操作的根底。 复杂性：复杂性：图的任意顶点可能和其余的顶点相邻接，可能图的任意顶点可能和其余的顶点相邻接，可能在访问了某个顶点后，沿某条途径搜索后又回到原顶点。在访问了某个顶点后，沿某条途径搜索后又回到原顶点。 解决方法：解决方法：在遍历过程中记下已被访问过的顶点。设置在遍历过程中记下已被访问过的顶点。设置一个辅助向量一个辅助向量Visited1nn为顶点数为顶点数，其初值为，其初值为0，一旦访问了顶点一旦访问

45、了顶点vi后，使后，使Visitedi为为1或为访问的次序号或为访问的次序号。 图的遍历算法有图的遍历算法有深度优先搜索算法深度优先搜索算法和和广度优先搜索广度优先搜索算法算法。采用的数据构造是。采用的数据构造是正正邻接链表邻接链表。7.3.1 深度优先搜索算法深度优先搜索算法 深度优先搜索深度优先搜索Depth First Search-DFS遍历类似遍历类似树树的先序遍历的先序遍历，是，是树的先序遍历的推广树的先序遍历的推广。1 算法思想算法思想 设初始状态时图中的所有顶点未被访问，那么：设初始状态时图中的所有顶点未被访问，那么： 从图中某个顶点从图中某个顶点vi出发出发，访问，访问vi；

46、然后找到；然后找到vi的的一个邻一个邻接顶点接顶点vi1 ； 从从vi1出发，深度优先搜索访问和出发，深度优先搜索访问和vi1相相邻接且未被访问邻接且未被访问的所有顶点；的所有顶点； 转转 ，直到和，直到和vi相相邻接的所有顶点都被访问为止邻接的所有顶点都被访问为止 继续选取图中未被访问顶点继续选取图中未被访问顶点vj作为起始顶点，转作为起始顶点，转1 1，直到图中所有顶点都被访问为止。直到图中所有顶点都被访问为止。图图7-17 无向图深度优先搜索遍历无向图深度优先搜索遍历(a) 无向图无向图Gv1v2v3v4v5(b) G的邻接链表的邻接链表01234MAX_VEX-1v1 v2v3 v4

47、v5 21 20 01 4 3 无向图的深度优先搜索遍历例如无向图的深度优先搜索遍历例如红色箭红色箭头头。某种。某种DFS次序是次序是：v1 v3 v2 v4 v5 由算法思想知，这是一个递归过程。因此，先设由算法思想知，这是一个递归过程。因此，先设计一个从某个顶点计一个从某个顶点编号编号为为v0开场开场深度优先深度优先搜索的搜索的函数函数，便于调用。，便于调用。代码详见代码详见P169P1692 算法实现算法实现3 算法分析算法分析 遍历时，对图的每个顶点至多调用一次遍历时，对图的每个顶点至多调用一次DFS函函数。其本质就是对每个顶点查找邻接顶点的过程，取数。其本质就是对每个顶点查找邻接顶点

48、的过程，取决于存储构造。当图有决于存储构造。当图有e条边，其时间复杂度为条边，其时间复杂度为Oe，总时间复杂度为，总时间复杂度为On+e 。7.3.2 广度优先搜索算法广度优先搜索算法 广度优先搜索广度优先搜索Breadth First Search-BFS遍历类似遍历类似树树的按层次遍历的按层次遍历的过程的过程。1 算法思想算法思想 设初始状态时图中的所有顶点未被访问，那么：设初始状态时图中的所有顶点未被访问，那么： 从图中某个顶点从图中某个顶点vi出发出发，访问，访问vi； 访问访问vi的所有相的所有相邻接且未被访问的所有顶点邻接且未被访问的所有顶点vi1，vi2，vim； 以以vi1，v

49、i2， ，vim的次序的次序，以，以vij1jm依此作依此作为为vi ，转；，转； 继续选取图中继续选取图中未被访问未被访问顶点顶点vk作为起始顶点作为起始顶点，转，直，转，直到图中所有顶点都被访问为止。到图中所有顶点都被访问为止。有向图的广度优先搜索遍历例如有向图的广度优先搜索遍历例如红色箭头红色箭头。上述图的上述图的BFS次序是次序是：v1 v2 v4 v3 v5(b) G的正邻接链表的正邻接链表13 014 2 3 01234MAX_VEX-1v1 2 v2 0 v3 3v4 1 v5 1 图图7-18 有向图广度优先搜索遍历有向图广度优先搜索遍历(a) 有向图有向图Gv1v2v3v4v

50、5 2 算法实现算法实现 为了标记图中顶点是否被访问过，同样需要一个为了标记图中顶点是否被访问过，同样需要一个访问标记数组；其次，为了依此访问与访问标记数组；其次，为了依此访问与vi相邻接的各相邻接的各个顶点个顶点，需要附加一个队列来保存访问，需要附加一个队列来保存访问vi的相邻接的的相邻接的顶点。顶点。代码实现详见代码实现详见P170P170。 3 算法分析算法分析 用用广度优先搜索算法广度优先搜索算法遍历图与遍历图与深度优先搜索算法深度优先搜索算法遍历图的遍历图的唯一区别唯一区别是是邻接点搜索次序不同邻接点搜索次序不同，因此，因此，广广度优先搜索算法度优先搜索算法遍历图的总时间复杂度为遍历

51、图的总时间复杂度为On+e 。7.4 图的连通性问题图的连通性问题 本节所讨论的内容是图的遍历算法的详细应用。本节所讨论的内容是图的遍历算法的详细应用。7.4.1 无向图的连通分量与生成树无向图的连通分量与生成树1 无向图的连通分量和生成树无向图的连通分量和生成树 对于无向图，对其进展遍历时：对于无向图，对其进展遍历时： 假设是假设是连通图连通图：仅需从图中：仅需从图中任一顶点出发任一顶点出发，就能访问，就能访问图中的所有顶点；图中的所有顶点； 假设是假设是非连通图非连通图：需从图中：需从图中多个顶点出发多个顶点出发。每次从一。每次从一个新顶点出发所访问的顶点集序列个新顶点出发所访问的顶点集序

52、列恰好是恰好是各个连通分量的各个连通分量的顶点集；顶点集；(a) 无向图无向图Gv1v2v3v4v5(b) G的邻接链表的邻接链表01234MAX_VEX-1v1 v2v3 v4 v5 21 20 01 4 3 图图7-19 无向图及深度优先生成森林无向图及深度优先生成森林(c) 深度优先生成森林深度优先生成森林v1v2v3v4v5无向非连通图，按图中给定的邻接表进展深度无向非连通图，按图中给定的邻接表进展深度优先搜索遍历，优先搜索遍历，2次调用次调用DFS所得到的顶点访所得到的顶点访问序列集是：问序列集是： v1 ,v3 ,v2和和 v4 ,v5 假设假设G=V,E是无向连通图是无向连通图，

53、 顶点集和边集顶点集和边集分别是分别是VG ，EG 。假设从。假设从G中中任意点出发遍任意点出发遍历时，历时， EG被分成两个互不相交的集合：被分成两个互不相交的集合：TG ：遍历过程中所：遍历过程中所经过的边经过的边的集合；的集合；BG ：遍历过程中：遍历过程中未经过的边未经过的边的集合；的集合； 显然：显然： EG=TGBG ，TGBG= 显然，显然，图图G=V, TG是是G的极小连通子图的极小连通子图，且且G是一棵树是一棵树。G称为图称为图G的一棵生成树的一棵生成树。 从任意点出发从任意点出发按按DFS算法算法得到生成树得到生成树G称为称为深度优深度优先生成树先生成树；按按BFS算法算法

54、得到的得到的G称为称为广度优先生成树广度优先生成树。 假设假设G=V,E是无向非连通图是无向非连通图，对图进展遍对图进展遍历时得到假设干个连通分量的顶点集历时得到假设干个连通分量的顶点集：V1G ,V2G ,VnG和相应所经过的边集和相应所经过的边集：T T1G ,T2G , ,TnG 那么对应的顶点集和边集的二元组：那么对应的顶点集和边集的二元组：Gi=ViG,TiG1in是对应分量的生成树是对应分量的生成树，所有这些，所有这些生成树构生成树构成了原来非连通图的生成森林成了原来非连通图的生成森林。说明说明：当给定无向图要求画出其对应的生成树或生成当给定无向图要求画出其对应的生成树或生成森林时

55、，森林时，必须先给出相应的邻接表，然后才能根据邻必须先给出相应的邻接表，然后才能根据邻接表画出其对应的生成树或生成森林接表画出其对应的生成树或生成森林。7.4.2 有向图的强连通分量有向图的强连通分量 对于有向图，在其每一个对于有向图，在其每一个强连通分量中强连通分量中，任何两任何两个顶点都是可达的个顶点都是可达的。 V G，与，与V可互相到达的所有可互相到达的所有顶点就是包含顶点就是包含V的强连通分量的所有顶点的强连通分量的所有顶点。 设从设从V可到达可到达 以以V为起点的所有有向途径的终为起点的所有有向途径的终点点的顶点集合为的顶点集合为T1G，而到达，而到达V 以以V为终点的为终点的所有

56、有向途径的起点所有有向途径的起点的顶点集合为的顶点集合为T2G，那么，那么包含包含V的强连通分量的顶点集合是的强连通分量的顶点集合是： T1GT2G 。 求有向图求有向图G的强连通分量的的强连通分量的根本步骤根本步骤是：是： 对对G进展深度优先遍历，生成进展深度优先遍历，生成G的深度优先生成森的深度优先生成森林林T。 对对森林森林T的顶点按的顶点按中序遍历中序遍历顺序进展编号。顺序进展编号。 改变改变G中每一条弧的方向中每一条弧的方向，构成一个新的有向图，构成一个新的有向图G。 按中标出的顶点编号，从编号最大的顶点开场对按中标出的顶点编号，从编号最大的顶点开场对G进展深度优先搜索，得到一棵深度

57、优先生成树。假进展深度优先搜索，得到一棵深度优先生成树。假设一次完好的搜索过程没有遍历设一次完好的搜索过程没有遍历G的所有顶点，那么的所有顶点，那么从未访问的顶点中选择一个编号最大的顶点，由它开从未访问的顶点中选择一个编号最大的顶点，由它开场再进展深度优先搜索，并得到另一棵深度优先生成场再进展深度优先搜索，并得到另一棵深度优先生成树。在该步骤中，每一次深度优先搜索所得到的生成树。在该步骤中，每一次深度优先搜索所得到的生成树中的顶点就是树中的顶点就是G的一个强连通分量的所有顶点。的一个强连通分量的所有顶点。 重复步骤重复步骤 ，直到，直到G中的所有顶点都被访问。中的所有顶点都被访问。dacfeb

58、(a) 有向图有向图G654321dacfeb(b) 执行步骤执行步骤(1)和和(2)acdfeb(c) 执行步骤执行步骤(3)adcbefd) 执行步骤执行步骤(4)和和(5)图图7-20 利用深度优先搜索求有向图的强连通分量利用深度优先搜索求有向图的强连通分量 在算法实现时，建立一个数组在算法实现时，建立一个数组in_ordern存放深存放深度优先生成森林的中序遍历序列。对每个顶点度优先生成森林的中序遍历序列。对每个顶点v，在调，在调用用DFS函数完毕时函数完毕时，将顶点依次存放在将顶点依次存放在数组数组in_ordern中中。图采用十字链表作为存储构造最适宜。图采用十字链表作为存储构造最

59、适宜。7.4.3 最小生成树最小生成树 假如假如连通图连通图是一个带权图，那么其生成树中的边也带权，是一个带权图，那么其生成树中的边也带权，生成树中生成树中所有边的权值之和所有边的权值之和称为称为生成树的代价生成树的代价。 最小生成树最小生成树Minimum Spanning Tree ：带权带权连通图中代价最小的生成树称为最小生成树连通图中代价最小的生成树称为最小生成树。 最小生成树在实际中具有重要用处，如设计通信网。设最小生成树在实际中具有重要用处，如设计通信网。设图的顶点表示城市，边表示两个城市之间的通信线路，边的图的顶点表示城市，边表示两个城市之间的通信线路，边的权值表示建造通信线路的

60、费用。权值表示建造通信线路的费用。n个城市之间最多可以建个城市之间最多可以建n n-1/2条线路条线路，如何选择其中的，如何选择其中的n-1条，使总的建造费用最条，使总的建造费用最低低? ?根本原那么是：根本原那么是： 尽可能选取权值最小的边，但不能构成回路；尽可能选取权值最小的边，但不能构成回路； 选择选择n-1条边构成最小生成树条边构成最小生成树。 以上的根本原那么是基于以上的根本原那么是基于MST的如下性质：的如下性质： 设设G=V，E是一个带权连通图，是一个带权连通图，U是顶点集是顶点集V的的 一个非空子集。假设一个非空子集。假设uU ，vV-U，且，且u, v是是U中顶点到中顶点到V-U中顶点之间权值最小的边，那