PowerPoint Presentation - 华中师范大学.ppt

第第7 7章章 图图本章主题：本章主题：本章主题：本章主题：图的基本概念、图的存储结构和图的常用算法图的基本概念、图的存储结构和图的常用算法 教学目的：教学目的：教学目的：教学目的：教学重点：教学重点：教学重点：教学重点：图的各种存储方式及其运算图的各种存储方式及其运算 教学难点：教学难点：教学难点：教学难点：图结构存储方式的选择，几种经典图算法的实现图结构存储方式的选择，几种经典图算法的实现 本章内容本章内容本章内容本章内容：图的基本概念图的基本概念 图的存储结构图的存储结构 图的遍历图的遍历 最小生成树最小生成树 最短路径最短路径 拓扑排序拓扑排序 关键路径关键路径2022/12/201 本本章章主主要要介介绍绍图图的的基基本本概概念念、图图的的存存储储结结构构和和有有关关图图的一些常用算法。通过本章学习，读者应该：的一些常用算法。通过本章学习，读者应该：1)了解图的定义和术语了解图的定义和术语2)掌握图的各种存储结构掌握图的各种存储结构3)掌握图的深度优先搜索和广度优先搜索遍历算法掌握图的深度优先搜索和广度优先搜索遍历算法 4)理理解解最最小小生生成成树树、最最短短路路径径、拓拓扑扑排排序序、关关键键路路径径等等图的常用算法图的常用算法 本章学习导读本章学习导读本章学习导读本章学习导读 2022/12/202图图（GraphGraph）是一种较线性表和树更为复杂的是一种较线性表和树更为复杂的非线性结构非线性结构。是对结点的前趋和后继个数不加限制的数据结构，用来是对结点的前趋和后继个数不加限制的数据结构，用来描述元素描述元素之间之间“多对多多对多”的关系。的关系。在在线性结构线性结构中，结点之间的关系是线性关系，除开始结点和中，结点之间的关系是线性关系，除开始结点和 终端结点外，每个结点只有一个直接前趋和直接后继。终端结点外，每个结点只有一个直接前趋和直接后继。在在树形结构树形结构中，结点之间的关系实质上是层次关系，同层上中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。只能和上一层的一个结点（即双亲）相关（根结点除外）。在在图结构图结构中，对结点（图中常称为顶点）的前趋和后继个数中，对结点（图中常称为顶点）的前趋和后继个数不加限制的，即结点之间的关系是任意的。不加限制的，即结点之间的关系是任意的。由此，图的应用极为广泛，特别是近年来的迅速发展，已渗由此，图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。以及数学的其它分支中。2022/12/203 7 7.1.1.1.1图的定义图的定义图的定义图的定义 图图图图是由一个顶点集是由一个顶点集是由一个顶点集是由一个顶点集 VV和一个弧集和一个弧集和一个弧集和一个弧集 R R构成的数据结构。构成的数据结构。构成的数据结构。构成的数据结构。Graph=(V,R)Graph=(V,R)V V=x x|x x 某个数据对象某个数据对象某个数据对象某个数据对象，是顶点的有穷非空集合；是顶点的有穷非空集合；是顶点的有穷非空集合；是顶点的有穷非空集合；RR边的有限集合边的有限集合边的有限集合边的有限集合 R R=(=(x x,y y)|)|x x,y y V V 无向图无向图无向图无向图或或或或R R=y|x x,y y V V&PathPath(x x,y y)有向图有向图有向图有向图是顶点之间关系的有穷集合，也叫做是顶点之间关系的有穷集合，也叫做是顶点之间关系的有穷集合，也叫做是顶点之间关系的有穷集合，也叫做边边边边(edge)edge)集合集合集合集合。PathPath(x x,y y)表示从表示从表示从表示从 x x 到到到到 y y 的一条单向通路的一条单向通路的一条单向通路的一条单向通路,它是有方向的。它是有方向的。它是有方向的。它是有方向的。x x弧尾，弧尾，弧尾，弧尾，y y弧头弧头弧头弧头。7 7.1.1图及其基本运算图及其基本运算图及其基本运算图及其基本运算 2022/12/204 有向图与无向图有向图与无向图有向图与无向图有向图与无向图 有向图中：边用有向图中：边用有向图中：边用有向图中：边用 x,y表示，且表示，且表示，且表示，且x x与与与与y y是有序的。是有序的。是有序的。是有序的。a.a.有向图中的边称为有向图中的边称为有向图中的边称为有向图中的边称为“弧弧弧弧”b.xb.x弧尾或弧尾或弧尾或弧尾或初始点初始点初始点初始点 yy弧头或终端点弧头或终端点弧头或终端点弧头或终端点无向图：边用无向图：边用无向图：边用无向图：边用(x,y)x,y)表示，且顶表示，且顶表示，且顶表示，且顶x x与与与与 y y是无序的。是无序的。是无序的。是无序的。完全图完全图完全图完全图 在具有在具有在具有在具有n n 个顶点的有向图中，最大弧数为个顶点的有向图中，最大弧数为个顶点的有向图中，最大弧数为个顶点的有向图中，最大弧数为 n n(n n-1)-1)在具有在具有在具有在具有n n 个顶点的无向图中，最大边数为个顶点的无向图中，最大边数为个顶点的无向图中，最大边数为个顶点的无向图中，最大边数为 n n(n n-1)/2-1)/2顶点的度顶点的度顶点的度顶点的度无向图：与该顶点相关的边的数目无向图：与该顶点相关的边的数目无向图：与该顶点相关的边的数目无向图：与该顶点相关的边的数目有向图：有向图：有向图：有向图：入度入度入度入度ID(ID(v v)：以该顶点为头的弧的数目以该顶点为头的弧的数目以该顶点为头的弧的数目以该顶点为头的弧的数目出度出度出度出度OD(OD(v v)：以该顶点为尾头的弧的数目以该顶点为尾头的弧的数目以该顶点为尾头的弧的数目以该顶点为尾头的弧的数目在有向图中在有向图中在有向图中在有向图中,顶点的度等于该顶点的入度与出度之和顶点的度等于该顶点的入度与出度之和顶点的度等于该顶点的入度与出度之和顶点的度等于该顶点的入度与出度之和。2022/12/205图图图图7-17-1无向图和有向图无向图和有向图无向图和有向图无向图和有向图 2022/12/206 在在图图7-17-1中中，图图(a)a)为为无无向向图图，其其中中G1G1的的顶顶点点集集合合和和边边集集合合分分别为：别为：V(G1)=1V(G1)=1，2 2，3 3，4 4，5 5，6 6，77，E(G1)=(1E(G1)=(1，2)2)，(l(l，3)3)，(2(2，3)3)，(3(3，4)4)，(3(3，5)5)，(5(5，6)6)，(5(5，7)7)。图图(c)c)为有向图，其中为有向图，其中G3G3的顶点集合和弧集合分别为的顶点集合和弧集合分别为V(G3)=1V(G3)=1，2 2，3 3，4 4，5 5，66，E(G3)=，2022/12/2077.1.2 图的基本术语图的基本术语1 1 顶点的度顶点的度 与与顶顶点点v v相相关关的的边边或或弧弧的的数数目目称称作作顶顶点点v v的的度度。在在有有向向图图中中，一一个个顶顶点点依依附附的的弧弧头头数数目目，称称为为该该顶顶点点的的入入度度。一一个个顶顶点点依依附附的的弧弧尾尾数数目目，称称为为该该顶顶点点的的出出度度，某某个个顶顶点点的的入入度度和和出出度度之之和和称为该顶点的度。称为该顶点的度。例如图例如图7-17-1中，无向图中，无向图G1G1中顶点中顶点3 3的度为的度为4 4，顶点，顶点5 5的度为的度为3 3。例如在图例如在图7-17-1中，有向图中，有向图G3G3中顶点中顶点1 1的出度的出度OD(1)=3OD(1)=3，入度入度ID ID(1)=1(1)=1，其度其度TD(1)=4TD(1)=4。2022/12/2082 2 2 2路径和回路路径和回路路径和回路路径和回路在无向图在无向图G中，若存在一个顶点序列中，若存在一个顶点序列Vp,Vi1，Vi2，Vin，Vq,使得（使得（Vp,Vi1）,(Vi1,Vi2),.，(Vin,Vq)均属于均属于E（G），），则称顶则称顶点点Vp到到Vq存在一条路径。存在一条路径。若一条路径上除起点和终点可以相同外，其余顶点均不相同，若一条路径上除起点和终点可以相同外，其余顶点均不相同，则称此路径为则称此路径为简单路径简单路径。起点和终点相同的路径称为起点和终点相同的路径称为回路回路；简单路径组成的回路称为简单路径组成的回路称为简单回路简单回路。路径长度路径长度路径长度路径长度路径上经过的路径上经过的边的数目边的数目称为该路径的称为该路径的路径长度路径长度。非带权图的路径非带权图的路径非带权图的路径非带权图的路径长度长度长度长度是指此路径上边是指此路径上边是指此路径上边是指此路径上边/弧的条数。弧的条数。弧的条数。弧的条数。带权图的路径带权图的路径带权图的路径带权图的路径长度长度长度长度是指路径上各边是指路径上各边是指路径上各边是指路径上各边/弧的权之和。弧的权之和。弧的权之和。弧的权之和。2022/12/2092022/12/20103.3.3.3.边和弧边和弧边和弧边和弧边边:无向图中无向图中顶点的偶对，写成（顶点的偶对，写成（VxVx，VyVy）或（或（VyVy，VxVx）。）。弧弧:有向图中顶点的偶对有向图中顶点的偶对,Vx,VyVx,Vy表示从表示从VxVx到到VyVy。弧头弧头:弧的终点弧的终点弧尾弧尾:弧的起点弧的起点弧弧 VxVx，VyVy 弧弧尾尾VxVx 弧头弧头VyVy2022/12/20114 4 4 4子图子图子图子图设设有有两两个个图图 G(V,E)和和 G(V,E)。若若 V V 且且E E,则称则称图图G是是图图G的子图。的子图。2022/12/20121 12 23 34 45 5(a)(a)1 12 23 34 45 5(b)(b)1 12 24 45 5(c)(c)1 14 45 5(d)(d)2 22022/12/20135 5 5 5连通性连通性连通性连通性在无向图中在无向图中在无向图中在无向图中,若从顶点若从顶点若从顶点若从顶点v v1 1到顶点到顶点到顶点到顶点v v2 2有路径有路径有路径有路径,则称顶点则称顶点则称顶点则称顶点v v1 1与与与与v v2 2是连通的。是连通的。是连通的。是连通的。如果图中任意一对顶点如果图中任意一对顶点如果图中任意一对顶点如果图中任意一对顶点v vi i和和v vj j（v vi i，v vj jVV）都是连通的都是连通的都是连通的都是连通的,则称此图是则称此图是则称此图是则称此图是连通图。连通图。连通图。连通图。非连通图的极大连通子图叫做连通分量非连通图的极大连通子图叫做连通分量非连通图的极大连通子图叫做连通分量非连通图的极大连通子图叫做连通分量。66强连通图与强连通分量强连通图与强连通分量强连通图与强连通分量强连通图与强连通分量 在有向图中在有向图中在有向图中在有向图中,若对于每一对顶点若对于每一对顶点若对于每一对顶点若对于每一对顶点v vi i和和和和v vj j,都存在一条从都存在一条从都存在一条从都存在一条从v vi i到到到到v vj j和从和从和从和从v vj j到到到到v vi i的路径的路径的路径的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做则称此图是强连通图。非强连通图的极大强连通子图叫做则称此图是强连通图。非强连通图的极大强连通子图叫做则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。强连通分量。强连通分量。强连通分量。2022/12/20147 7 7 7网络网络网络网络权权权权 某某某某些些些些图图图图的的的的边边边边或或弧弧具具具具有有有有与与与与它它它它相相相相关关关关的的的的数数数数,称称称称之之之之为为为为权权权权。权权可以代表一个顶点到另一个顶点的距离，耗费等。可以代表一个顶点到另一个顶点的距离，耗费等。网络网络网络网络 这种带权这种带权这种带权这种带权连通图连通图连通图连通图一般称为一般称为网络。网络。网络。网络。如图如图7-47-4所示所示。2022/12/20158 8 8 8生成树、生成森林生成树、生成森林生成树、生成森林生成树、生成森林生成树生成树生成树生成树 一个连通图的生成树是它的一个连通图的生成树是它的一个连通图的生成树是它的一个连通图的生成树是它的极小连通子图极小连通子图极小连通子图极小连通子图，在，在，在，在n n个个个个顶点的情形下，有顶点的情形下，有顶点的情形下，有顶点的情形下，有n n-1-1条边。条边。条边。条边。生成树是对连通图而言的生成树是对连通图而言的生成树是对连通图而言的生成树是对连通图而言的 是连同图的极小连同子图是连同图的极小连同子图是连同图的极小连同子图是连同图的极小连同子图 包含图中的所有顶点包含图中的所有顶点包含图中的所有顶点包含图中的所有顶点 有且仅有有且仅有有且仅有有且仅有n-1n-1条边条边条边条边非连通图非连通图的生成树则组成一个的生成树则组成一个生成森林生成森林。若图中有。若图中有n n个顶个顶点，点，m m个连通分量，则生成森林中有个连通分量，则生成森林中有n-mn-m条边。条边。2022/12/20169 9 9 9邻接点邻接点顶点顶点:图中的结点图中的结点 邻接点邻接点:无向图中，若边无向图中，若边(x,x,y)y)E E，两顶点之间有条边，则两顶点互两顶点之间有条边，则两顶点互两顶点之间有条边，则两顶点互两顶点之间有条边，则两顶点互 为邻接点。为邻接点。为邻接点。为邻接点。xy(x,y)xy(x,y)有向图中，若弧有向图中，若弧(x,x,y)y)E E，从从从从x x到到到到y y有一条弧，则有一条弧，则有一条弧，则有一条弧，则y y是是是是x x的邻接点，的邻接点，的邻接点，的邻接点，但但但但x x不是不是不是不是y y的邻接点。的邻接点。的邻接点。的邻接点。xyxy VxVyx、y互为邻接点互为邻接点VxVyy是是x的邻接点的邻接点2022/12/20177.1.3 7.1.3 7.1.3 7.1.3 图的基本运算图的基本运算图的基本运算图的基本运算 图的基本运算图的基本运算:见见P156P1562022/12/20187.2.1 7.2.1 邻接矩阵邻接矩阵邻接矩阵邻接矩阵邻接矩阵邻接矩阵(AdjacencyMatrix)是表示顶点之间相邻关系的矩阵。是表示顶点之间相邻关系的矩阵。设设G(V，E)是具有是具有n个顶点的图，则个顶点的图，则G的邻接矩阵是具有如下性的邻接矩阵是具有如下性质的质的n阶方阵。阶方阵。7.27.2图的存储结构图的存储结构图的存储结构图的存储结构 无向图的邻接矩阵是以主对角线对称的，有向图的邻接矩阵可能无向图的邻接矩阵是以主对角线对称的，有向图的邻接矩阵可能是不对称的。是不对称的。在有向图中：在有向图中：第第i行行1的个数就是顶点的个数就是顶点i的出度，的出度，第第j 列列1的个数就是顶点的个数就是顶点j的入度。的入度。在无向图中在无向图中,第第i行行(列列)1的个数就是顶点的个数就是顶点i的度。的度。2022/12/2019图图7-6 有向图及其邻接矩阵有向图及其邻接矩阵图图7-5无向图及其邻接矩阵无向图及其邻接矩阵 2022/12/2020 对对于于无无向向图图，（vi，vj）和和（vj，vi）表表示示同同一一条条边边，因因此此，在邻接矩阵中在邻接矩阵中Aij=Aji。无无向向图图的的邻邻接接矩矩阵阵是是（关关于于主主对对角角线线）对对称称矩矩阵阵，可可用用主主对对角角线以上（或以下）的部分表示。线以上（或以下）的部分表示。对对有有向向图图，弧弧和和表表示示方方向向不不同同的的两两条条弧弧，Aij和和Aji表示不同的弧，所以有向图的邻接矩阵一般不具有对称性。表示不同的弧，所以有向图的邻接矩阵一般不具有对称性。邻接矩阵表示法适合于以顶点为主的运算。邻接矩阵表示法适合于以顶点为主的运算。2022/12/2021 对对于于有有向向图图，顶顶点点vi的的出出度度OD(vi)等等于于邻邻接接矩矩阵阵第第i行行元元素素之和；顶点之和；顶点vi的的入度入度ID(vi)等于邻接矩阵第等于邻接矩阵第i列元素之和，即列元素之和，即：对于无向图，顶点对于无向图，顶点v vi i的度等于邻接矩阵第的度等于邻接矩阵第i i行的元素之和，即：行的元素之和，即：OD(vOD(vi i)=)=ID(vID(vi i)=)=TDTD（v vi i）=对于带权图的邻接矩阵，定义为：对于带权图的邻接矩阵，定义为：2022/12/2022 顶点表顶点表顶点表顶点表:一个记录各个顶点信息的一维数组，一个记录各个顶点信息的一维数组，一个记录各个顶点信息的一维数组，一个记录各个顶点信息的一维数组，邻接矩阵邻接矩阵邻接矩阵邻接矩阵：一个表示各个顶点之间的关系（边或弧）的二维数组。：一个表示各个顶点之间的关系（边或弧）的二维数组。：一个表示各个顶点之间的关系（边或弧）的二维数组。：一个表示各个顶点之间的关系（边或弧）的二维数组。使使用用邻邻接接矩矩阵阵存存储储结结构构，可可用用一一维维数数组组表表示示图图的的顶顶点点集集合合，用用二二维维数数组组表表示示图图的的顶顶点点之之间间关关系系（边边或或弧弧）的的集集合合，数数据据类类型型定定义义如下：如下：#defineMAX_VERTEX_NUM20/最大顶点数最大顶点数typedefintAdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/邻接矩阵类型邻接矩阵类型typedefstructVertexTypevexsMAX_VERTEX_NUM;/顶点表顶点表AdjMatrixarcs;/邻接矩阵邻接矩阵intvexnum,arcnum;/图的顶点数和弧数图的顶点数和弧数MGraph;由由于于一一般般图图的的边边或或弧弧较较少少，其其邻邻接接矩矩阵阵的的非非零零元元素素较较少少，属属稀稀疏矩阵，因此会造成一定存储空间的浪费。疏矩阵，因此会造成一定存储空间的浪费。2022/12/20237.2.27.2.2邻接表邻接表邻接表邻接表 图的链式存储结构图的链式存储结构 1)1)为每个顶点建立一个单链表，为每个顶点建立一个单链表，2)2)第第i i个单链表中包含顶点个单链表中包含顶点ViVi的所有邻接顶点。的所有邻接顶点。邻邻接接表表是是图图的的一一种种链链式式存存储储结结构构。类类似似于于树树的的孩孩子子链链表表表表示示法法。在在邻邻接接表表中中为为图图中中每每个个顶顶点点建建立立一一个个单单链链表表，用用单单链链表表中中的的一一个个结结点点表表示示依依附附于于该该顶顶点点的的一一条条边边（或或表表示示以以该该顶顶点点为为弧弧尾尾的的一条弧），称为边（或弧）结点。一条弧），称为边（或弧）结点。2022/12/2024把同一个顶点发出的边链接在同一个边链表中，链表的每一个把同一个顶点发出的边链接在同一个边链表中，链表的每一个把同一个顶点发出的边链接在同一个边链表中，链表的每一个把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做表结点（边结点），邻接点域结点代表一条边，叫做表结点（边结点），邻接点域结点代表一条边，叫做表结点（边结点），邻接点域结点代表一条边，叫做表结点（边结点），邻接点域adjvexadjvex保存与保存与保存与保存与该边相关联的另一顶点的顶点下标该边相关联的另一顶点的顶点下标该边相关联的另一顶点的顶点下标该边相关联的另一顶点的顶点下标，链域链域链域链域nextarcnextarc存放指向同一链存放指向同一链存放指向同一链存放指向同一链表中下一个表结点的指针表中下一个表结点的指针表中下一个表结点的指针表中下一个表结点的指针，数据域，数据域，数据域，数据域infoinfo存放边的权。边链表的表头存放边的权。边链表的表头存放边的权。边链表的表头存放边的权。边链表的表头指针存放在头结点中。指针存放在头结点中。指针存放在头结点中。指针存放在头结点中。头结点以顺序结构存储，其数据域头结点以顺序结构存储，其数据域头结点以顺序结构存储，其数据域头结点以顺序结构存储，其数据域datadata存放存放存放存放顶点信息，链域顶点信息，链域顶点信息，链域顶点信息，链域firstarcfirstarc指向链表中第一个顶点。指向链表中第一个顶点。指向链表中第一个顶点。指向链表中第一个顶点。表结点表结点头结点头结点adjvexnextarcinfodatafirstarc2022/12/2025带权图的边结点中带权图的边结点中带权图的边结点中带权图的边结点中infoinfo保存该边上的权值保存该边上的权值保存该边上的权值保存该边上的权值。顶点顶点顶点顶点 Vi Vi 的边链表的头结点存放在下标为的边链表的头结点存放在下标为的边链表的头结点存放在下标为的边链表的头结点存放在下标为 i i 的顶点数组中。的顶点数组中。的顶点数组中。的顶点数组中。在邻接表的边链表中，各个边结点的链入顺序任意，视边结点在邻接表的边链表中，各个边结点的链入顺序任意，视边结点在邻接表的边链表中，各个边结点的链入顺序任意，视边结点在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。输入次序而定。输入次序而定。输入次序而定。2022/12/2026有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表在有向图的邻接表中，第在有向图的邻接表中，第在有向图的邻接表中，第在有向图的邻接表中，第 i i 个链表中结点的个数是顶点个链表中结点的个数是顶点个链表中结点的个数是顶点个链表中结点的个数是顶点ViVi的出度的出度的出度的出度。在有向图的逆邻接表中，第在有向图的逆邻接表中，第在有向图的逆邻接表中，第在有向图的逆邻接表中，第 i i 个链表中结点的个数是顶点个链表中结点的个数是顶点个链表中结点的个数是顶点个链表中结点的个数是顶点ViVi 的入度。的入度。的入度。的入度。2022/12/2027 图图图图7-77-7为图为图为图为图7-6(7-6(a)a)的的的的的邻接表和逆邻接表的邻接表和逆邻接表的邻接表和逆邻接表的邻接表和逆邻接表图图图图7-77-7有向图的邻接表和逆有向图的邻接表和逆有向图的邻接表和逆有向图的邻接表和逆邻接表邻接表邻接表邻接表7-6(7-6(a)a)(b)41320212310123(c)143213003201232022/12/2028网络网络网络网络(带权图带权图带权图带权图)的邻接表的邻接表的邻接表的邻接表2022/12/2029存储表示存储表示存储表示存储表示typedeftypedef structstruct ArcNodeArcNode intint adjvexadjvex;structstruct ArcNodeArcNode*nextarcnextarc;intintinfo;info;ArcNodeArcNode;/;/边结点类型边结点类型边结点类型边结点类型typedeftypedef structstruct VNodeVNode VertexTypeVertexTypedata;data;ArcNodeArcNode*firstarcfirstarc;VNode,AdjListMAX_VERTEX_NUMVNode,AdjListMAX_VERTEX_NUM;typedeftypedef structstruct AdjListAdjListvertices;/vertices;/邻接表邻接表邻接表邻接表intint vexnum,arcnumvexnum,arcnum;ALGraphALGraph;2022/12/20307.2.37.2.3十字链表十字链表十字链表十字链表 十字链表十字链表十字链表十字链表(OrthogonalList)OrthogonalList)是是是是有向图有向图有向图有向图的另一种链式存储结构。的另一种链式存储结构。的另一种链式存储结构。的另一种链式存储结构。可看作是将有向图的邻接表和逆邻接表结合的一种链表。可看作是将有向图的邻接表和逆邻接表结合的一种链表。可看作是将有向图的邻接表和逆邻接表结合的一种链表。可看作是将有向图的邻接表和逆邻接表结合的一种链表。在十字链表中，为每个顶点在十字链表中，为每个顶点在十字链表中，为每个顶点在十字链表中，为每个顶点v v v vi i i i设置一个结点，它包含数据域设置一个结点，它包含数据域设置一个结点，它包含数据域设置一个结点，它包含数据域datadatadatadata和两个链域和两个链域和两个链域和两个链域firstoutfirstoutfirstoutfirstout、firstinfirstinfirstinfirstin，称为顶点结点。数据域称为顶点结点。数据域称为顶点结点。数据域称为顶点结点。数据域datadatadatadata用于存放顶点用于存放顶点用于存放顶点用于存放顶点v v v vi i i i的有关信息；链域的有关信息；链域的有关信息；链域的有关信息；链域firstinfirstinfirstinfirstin指向以顶点指向以顶点指向以顶点指向以顶点v v v vi i i i为弧头的为弧头的为弧头的为弧头的第一个弧结点；链域第一个弧结点；链域第一个弧结点；链域第一个弧结点；链域firstoutfirstoutfirstoutfirstout指向以顶点指向以顶点指向以顶点指向以顶点v v v vi i i i为弧尾的第一个弧结点。为弧尾的第一个弧结点。为弧尾的第一个弧结点。为弧尾的第一个弧结点。弧结点包括四个域：尾域弧结点包括四个域：尾域弧结点包括四个域：尾域弧结点包括四个域：尾域tailvextailvextailvextailvex、头域头域头域头域headvexheadvexheadvexheadvex，链域链域链域链域hlinkhlinkhlinkhlink和和和和tlinktlinktlinktlink。hlinkhlink指向弧头相同的下一条弧，指向弧头相同的下一条弧，tlinktlink指向弧尾相同的下指向弧尾相同的下一条弧；一条弧；datadata顶点信息，顶点信息，firstinfirstin以该顶点为头的第一个弧结点，以该顶点为头的第一个弧结点，firstoutfirstout以该结点为尾的第一个弧结点以该结点为尾的第一个弧结点headvextailvexhlinktlinkinfofirstindatafirstout顶点结点顶点结点弧结点弧结点2022/12/2031图图图图7-87-8十字链表十字链表十字链表十字链表 图图图图7-87-8为图为图为图为图7-6(7-6(a)a)有向图的十字链表。有向图的十字链表。有向图的十字链表。有向图的十字链表。采采采采用用用用十十十十字字字字链链链链表表表表表表表表示示示示有有有有向向向向图图图图，很很很很容容容容易易易易找找找找到到到到以以以以顶顶顶顶点点点点v vi i为为为为弧弧弧弧尾尾尾尾的的的的弧弧弧弧和和和和以以以以顶顶顶顶点点点点v vi i为为为为弧弧弧弧头头头头的的的的弧弧弧弧，因因因因此此此此顶顶顶顶点点点点的的的的出出出出度度度度、入入入入度度度度都都都都很很很很容容容容易求得。易求得。易求得。易求得。2022/12/2032十字链表的数据类型定义如下：十字链表的数据类型定义如下：十字链表的数据类型定义如下：十字链表的数据类型定义如下：#define MAXV#define MAXV typedeftypedef structstruct /弧结点弧结点弧结点弧结点 intint tailvex,headvextailvex,headvex;/;/弧尾和弧头顶点位置弧尾和弧头顶点位置弧尾和弧头顶点位置弧尾和弧头顶点位置 structstruct ArcNodeArcNode*hlinkhlink,*,*tlinktlink;/弧头相同和弧尾相同的弧的链域弧头相同和弧尾相同的弧的链域弧头相同和弧尾相同的弧的链域弧头相同和弧尾相同的弧的链域 ArcNodeArcNode;typedeftypedef structstruct /顶点结点顶点结点顶点结点顶点结点 VertexTypeVertexType data;/data;/顶点信息顶点信息顶点信息顶点信息 ArcNodeArcNode*firstinfirstin,*,*firstoutfirstout;/分别指向该顶点的第一条入弧和出弧分别指向该顶点的第一条入弧和出弧分别指向该顶点的第一条入弧和出弧分别指向该顶点的第一条入弧和出弧 VexNodeVexNode;2022/12/20337.2.47.2.4邻接多重表邻接多重表邻接多重表邻接多重表 邻邻邻邻接接接接多多多多重重重重表表表表是是是是无无无无向向向向图图图图的的的的另另另另一一一一种种种种链链链链式式式式存存存存储储储储结结结结构构构构。在在在在邻邻邻邻接接接接多多多多重重重重表表表表中中中中设设设设置置置置一一一一个个个个边边边边结结结结点点点点表表表表示示示示图图图图中中中中的的的的一一一一条条条条边边边边。边边边边结结结结点点点点包包包包含含含含五五五五个个个个域域域域，结构如下所示：结构如下所示：结构如下所示：结构如下所示：其中：其中：其中：其中：mark mark mark mark 域域域域 标志域，用于对该边进行标记；标志域，用于对该边进行标记；标志域，用于对该边进行标记；标志域，用于对该边进行标记；ivexivexivexivex 域域域域 存放该边依附的一个顶点存放该边依附的一个顶点存放该边依附的一个顶点存放该边依附的一个顶点v v v vi i i i的位置信息；的位置信息；的位置信息；的位置信息；ilinkilinkilinkilink 域域域域 该链域指向依附于顶点该链域指向依附于顶点该链域指向依附于顶点该链域指向依附于顶点v v v vi i i i的另一条边的边结点；的另一条边的边结点；的另一条边的边结点；的另一条边的边结点；jvexjvexjvexjvex 域域域域 存放该边依附的另一个顶点存放该边依附的另一个顶点存放该边依附的另一个顶点存放该边依附的另一个顶点v v v vj j j j的位置信息；的位置信息；的位置信息；的位置信息；jlinkjlinkjlinkjlink 域域域域 该链域指向依附于顶点该链域指向依附于顶点该链域指向依附于顶点该链域指向依附于顶点v v v vj j j j的另一条边的边结点。的另一条边的边结点。的另一条边的边结点。的另一条边的边结点。邻接多重表为每个顶点设置一个结点，其结构如下：邻接多重表为每个顶点设置一个结点，其结构如下：邻接多重表为每个顶点设置一个结点，其结构如下：邻接多重表为每个顶点设置一个结点，其结构如下：2022/12/2034图图图图7-97-9邻接多重表邻接多重表邻接多重表邻接多重表 图图7-9为图为图7-5(a)无向图的邻接多重表。无向图的邻接多重表。由由由由邻邻邻邻接接接接多多多多重重重重表表表表可可可可以以以以看看看看出出出出，表表表表示示示示边边边边（v vi i，v vj j）的的的的边边边边结结结结点点点点通通通通过过过过链链链链域域域域ilinkilink和和和和jlinkjlink链链链链入入入入了了了了顶顶顶顶点点点点v vi i和和和和顶顶顶顶点点点点v vj j的的的的两两两两个个个个链链链链表表表表中中中中，实实实实现现现现了了了了用用用用一一一一个个个个边边边边结结结结点点点点表表表表示示示示一一一一个个个个边边边边的的的的目目目目的的的的，克克克克服服服服了了了了在在在在邻邻邻邻接接接接表表表表中中中中用用用用两两两两个个个个边边边边结结结结点点点点表表表表示示示示一一一一个个个个边边边边的的的的缺缺缺缺点点点点。因因因因此此此此邻接多重表是无向图的一种很有效的存储结构。邻接多重表是无向图的一种很有效的存储结构。邻接多重表是无向图的一种很有效的存储结构。邻接多重表是无向图的一种很有效的存储结构。2022/12/2035邻接多重表的结点数据类型定义如下：邻接多重表的结点数据类型定义如下：邻接多重表的结点数据类型定义如下：邻接多重表的结点数据类型定义如下：#define MAXV define MAXV typedeftypedef structstruct /边结点类型边结点类型边结点类型边结点类型 intint mark;/mark;/访问标识访问标识访问标识访问标识 intint ivex,jvexivex,jvex;/;/该边的两个顶点位置信息该边的两个顶点位置信息该边的两个顶点位置信息该边的两个顶点位置信息 structstruct EnodeEnode*ilinkilink,*,*jlinkjlink;/分别指向依附这两个顶点的下一条边分别指向依附这两个顶点的下一条边分别指向依附这两个顶点的下一条边分别指向依附这两个顶点的下一条边 EnodeEnode;typedeftypedef structstruct /顶点结点类型顶点结点类型顶点结点类型顶点结点类型 VertexTypeVertexType data;/data;/顶点数据域顶点数据域顶点数据域顶点数据域 ENodeENode*firstedgefirstedge;/;/指向第一条依附该顶点的边指向第一条依附该顶点的边指向第一条依附该顶点的边指向第一条依附该顶点的边 VnodeVnode;2022/12/20367.37.3图的遍历图的遍历图的遍历图的遍历 和和和和树树树树的的的的遍遍遍遍历历历历相相相相似似似似，若若若若从从从从图图图图中中中中某某某某顶顶顶顶点点点点出出出出发发发发访访访访遍遍遍遍图图图图中中中中每每每每个个个个顶顶顶顶点点点点，且且且且每每每每个个个个顶顶顶顶点点点点仅仅仅仅访访访访问问问问一一一一次次次次，此此此此过过过过程程程程称称称称为为为为图图图图的的的的遍遍遍遍历历历历。(TraversingTraversingGraph)Graph)。但但是是，在在图图中中有有回回路路，从从图图中中某某一一顶顶点点出出发发访访问问图图中中其其它它顶顶点点时时，可可能能又又会会回回到到出出发发点点，而而图图中中或或许许还还有有顶顶点点没没有有访访问问到，因此，图的遍历较树的遍历更复杂。到，因此，图的遍历较树的遍历更复杂。图图的的遍遍历历算算法法是是求求解解图图的的连连通通性性问问题题、拓拓扑扑排排序序和和求求关关键键路路径等算法的基础。径等算法的基础。图图的的遍遍历历顺顺序序有有两两种种：深深深深度度度度优优优优先先先先搜搜搜搜索索索索（DFSDFSDFSDFS）和和和和广广广广度度度度优优优优先先先先搜搜搜搜索索索索（BFSBFS）。）。）。）。对每种搜索顺序，访问各顶点的顺序也不是唯一的。对每种搜索顺序，访问各顶点的顺序也不是唯一的。2022/12/20377.3.17.3.1深度优先搜索（深度优先搜索（深度优先搜索（深度优先搜索（DFSDFS）1深度优先搜索思想深度优先搜索思想深深度度优优先先搜搜索索遍遍历历类类似似于于树树的的先先序序遍遍历历。假假定定给给定定图图G的的初初态态是是所所有有顶顶点点均均未未被被访访问问过过，在在G中中任任选选一一个个顶顶点点i作作为为遍遍历历的的初初始始点点，则深度优先搜索则深度优先搜索递归调用包含以下操作：递归调用包含以下操作：（1 1）访问访问搜索到的未被搜索到的未被访问访问的的邻邻接点；接点；（2 2）将此）将此顶顶点的点的visitedvisited数数组组元素元素值值置置1 1；（3 3）搜搜索索该该顶顶点点的的未未被被访访问问的的邻邻接接点点，若若该该邻邻接接点点存存在在，则则从从此此邻接点开始进行同样的访问和搜索。邻接点开始进行同样的访问和搜索。深度深度