第+7+章+图.ppt

数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中1、图的基本概念；、图的基本概念；2、图的存储结构（邻接矩阵、邻接表及有向图十字邻接表）；、图的存储结构（邻接矩阵、邻接表及有向图十字邻接表）；3、图的遍历（深度优先搜索、广度优先搜索）；、图的遍历（深度优先搜索、广度优先搜索）；4、最小生成树（、最小生成树（kruskul算法、算法、prim算法）；算法）；5、最短路径（、最短路径（dijkstra算法、算法、floyd算法）；算法）；6、AOV网络与拓扑排序；网络与拓扑排序；7、AOE网络与关键路径。网络与关键路径。教学内容教学内容 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中图的特点图的特点 顶点的前驱和后继个数无限制顶点的前驱和后继个数无限制 图的应用图的应用顶点之间的关系是任意的顶点之间的关系是任意的 图中任意两个顶点之间都可能相关图中任意两个顶点之间都可能相关 图（图（Graph）是一种）是一种非线性结构非线性结构。语语 言言 学学逻逻 辑辑 学学物物 理理化化 学学电信工程电信工程 数数 学学 计算机科学计算机科学 多对多多对多多对多多对多 北京北京 西安西安 南京南京 杭州杭州 开封开封 洛阳洛阳 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中7.1 图的定义和术语图的定义和术语 定义：定义：图图是一种：是一种：数据元素间存在多对多关系的数据结构数据元素间存在多对多关系的数据结构 加上一组基本操作构成的加上一组基本操作构成的抽象数据类型抽象数据类型。ADT Graph 数据对象：数据对象：V 是具有相同特性的数据元素的集合，称为顶点集。是具有相同特性的数据元素的集合，称为顶点集。数据关系：数据关系：R=VR VR=|v,wV 且且 P(v,w),表示从表示从 v 到到 w 的弧，的弧，谓词谓词 P(v,w)定义了弧定义了弧 的意义或信息的意义或信息 基本操作：基本操作：数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中 定义：定义：图图(Graph)是是一种复杂的非线性数据结构，由一种复杂的非线性数据结构，由 顶点集合及顶点间的关系（也称弧或边）集合组成。顶点集合及顶点间的关系（也称弧或边）集合组成。可以表示为：可以表示为：G(V,VR)其中其中 V 是是顶点顶点的有穷非空集合；的有穷非空集合；VR 是是顶点之间关系顶点之间关系 的有穷集合，也叫做的有穷集合，也叫做弧弧或或边边集合。弧集合。弧是顶点的有序对，是顶点的有序对，边是顶点的无序对边是顶点的无序对。数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中基本操作：基本操作：结构初始化结构初始化CreateGraph(&G,V,VR);初始条件：初始条件：V 是图的顶点集，是图的顶点集，VR 是图中弧的集合。是图中弧的集合。操作结果：操作结果：按按 V 和和 VR 的定义构造图的定义构造图 G。销毁结构销毁结构DestroyGraph(&G);初始条件：初始条件：图图 G 存在。存在。操作结果：操作结果：销毁图销毁图 G。数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中引用型操作引用型操作LocateVex(G,u);初始条件：初始条件：图图 G 存在，存在，u 和和 G 中顶点有相同特征。中顶点有相同特征。操作结果：操作结果：若若 G 中存在和中存在和 u 相同的顶点，则返回该顶点在图相同的顶点，则返回该顶点在图 中中位置位置位置位置；否则返回其它信息。；否则返回其它信息。GetVex(G,v);初始条件：初始条件：图图 G 存在，存在，v 是是 G 中某个顶点。中某个顶点。操作结果：操作结果：返回返回 v 的值。的值。FirstAdjVex(G,v);初始条件：初始条件：图图 G 存在，存在，v 是是 G 中某个顶点。中某个顶点。操作结果：操作结果：返回返回 v 的第一个的第一个邻接点邻接点邻接点邻接点。若该顶点在。若该顶点在 G 中没有邻中没有邻 接点，则返回接点，则返回“空空”。顶点在图中的顶点在图中的“位置位置”指指 的是，在图的存储结构中顶的是，在图的存储结构中顶 点之间自然形成的相对位置。点之间自然形成的相对位置。若若G，则，则 称称 w 为为 v 的邻接点，的邻接点，若若(v,w)G，则称，则称 w 和和 v 互为邻接点。互为邻接点。数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中NextAdjVex(G,v,w);初始条件：初始条件：图图 G 存在，存在，v 是是 G 中某个顶点，中某个顶点，w 是是 v 的邻接顶点。的邻接顶点。操作结果：操作结果：返回返回 v 的（相对于的（相对于 w 的）的）下一个下一个下一个下一个邻接点。若邻接点。若 w 是是 v 的最后一个邻接点，则返回的最后一个邻接点，则返回“空空”。若若 v 有多个邻接有多个邻接 点，则在图的存储点，则在图的存储结结 构建立之后，其邻构建立之后，其邻接接 点之间的相对次序点之间的相对次序也也 就自然形成了。就自然形成了。加工型操作加工型操作PutVex(&G,v,value);初始条件：初始条件：图图 G 存在，存在，v 是是 G 中某个顶点。中某个顶点。操作结果：操作结果：对对 v 赋值赋值 value。InsertVex(&G,v);初始条件：初始条件：图图 G 存在，存在，v 和图中顶点有相同特征。和图中顶点有相同特征。操作结果：操作结果：在图在图 G 中增添新顶点中增添新顶点 v。数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中DeleteVex(&G,v);初始条件：初始条件：图图 G 存在，存在，v 是是 G 中某个顶点。中某个顶点。操作结果：操作结果：删除删除 G 中顶点中顶点 v 及其相关的弧。及其相关的弧。InsertArc(&G,v,w);初始条件：初始条件：图图 G 存在，存在，v 和和 w 是是 G 中两个顶点。中两个顶点。操作结果：操作结果：在在 G 中增添弧中增添弧，若，若 G 是无向的，则还增添是无向的，则还增添 对称弧对称弧。DeleteArc(&G,v,w);初始条件：初始条件：图图 G 存在，存在，v 和和 w 是是 G 中两个顶点。中两个顶点。操作结果：操作结果：在在 G 中删除弧中删除弧，若，若 G 是无向的，则还删除是无向的，则还删除 对称弧对称弧。数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中DFSTraverse(G,Visit();初始条件：初始条件：图图 G 存在，存在，Visit 是顶点的访问函数。是顶点的访问函数。操作结果：操作结果：对图对图 G 进行进行深度优先遍历深度优先遍历。遍历过程中对每个顶。遍历过程中对每个顶 点调用函数点调用函数 Visit 一次且仅一次。一旦一次且仅一次。一旦 visit()失败，失败，则操作失败。则操作失败。BFSTraverse(G,Visit();初始条件：初始条件：图图 G 存在，存在，Visit 是顶点的访问函数。是顶点的访问函数。操作结果：操作结果：对图对图 G 进行进行广度优先遍历广度优先遍历。遍历过程中对每个顶。遍历过程中对每个顶 点调用函数点调用函数 Visit 一次且仅一次。一旦一次且仅一次。一旦 visit()失败，失败，则操作失败。则操作失败。ADT Graph 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中 基本术语：基本术语：有向图有向图 无向图无向图 顶点：顶点：顶点：顶点：图中的数据元素。图中的数据元素。v2 v1 v3 v4 G1 v2 v1 v3 v4 v5 G2 弧：弧：弧：弧：若若 VR，则则 表示从表示从 v 到到 w 的的 一条弧，且称一条弧，且称 v 为为弧尾弧尾弧尾弧尾，称，称 w 为为弧头弧头弧头弧头，此时的图称此时的图称 为为有向图有向图有向图有向图。G1=(V1,A1)V1=v1,v2,v3,v4 A1=,边边边边：若若 VR 必有必有VR，则以无序则以无序 对对(v,w)代表这两个有序对，表示代表这两个有序对，表示 v 和和 w 之间的一条之间的一条 边，此时的图称为边，此时的图称为无向图无向图无向图无向图。G2=(V2,E2)V2=v1,v2,v3,v4,v5 E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中例：例：两个城市两个城市 A 和和 B，如果如果 A 和和 B 之间的连线的涵义是表示两之间的连线的涵义是表示两 个城市的距离，则个城市的距离，则 和和 是相同的，用是相同的，用(A,B)表示。表示。如果如果 A 和和 B 之间的连线的涵义是表示两城市之间人口流动之间的连线的涵义是表示两城市之间人口流动 的情况，则的情况，则 和和 是不同的。是不同的。北北 京京 上上 海海 北北 京京 上上 海海 (北京，上海北京，上海)数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中 无向图中边的取值范围：无向图中边的取值范围：0en(n-1)/2。（用用 n 表示图中顶点数目，用表示图中顶点数目，用 e 表示边的数目。且不表示边的数目。且不 考虑顶点到其自身的边。）考虑顶点到其自身的边。）完全图：完全图：完全图：完全图：有有 n(n-1)/2 条边的无向图（即：无向图条边的无向图（即：无向图 中每两个顶点之间都存在着一条边中每两个顶点之间都存在着一条边)称为称为完全图完全图完全图完全图。有向完全图：有向完全图：有向完全图：有向完全图：有有 n(n-1)条弧的有向图（即：有向条弧的有向图（即：有向 图中每两个顶点之间都存在着方向相反的两条弧）称图中每两个顶点之间都存在着方向相反的两条弧）称 为为有向完全图有向完全图有向完全图有向完全图。v2 v1 v3 v4 v5 有向图中弧的取值范围：有向图中弧的取值范围：0en(n-1)。（用用 n 表示图中顶点数目，用表示图中顶点数目，用 e 表示弧的数目。且不表示弧的数目。且不 考虑顶点到其自身的弧。）考虑顶点到其自身的弧。）v2 v1 v3 v4 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中 稀疏图：稀疏图：稀疏图：稀疏图：含有很少条边或弧的图。含有很少条边或弧的图。稠密图：稠密图：稠密图：稠密图：含有很多条边或弧的接近完全图的图。含有很多条边或弧的接近完全图的图。权：权：权：权：与图的与图的边边边边或或弧弧弧弧相关的数，这些数可以表示从一个顶点到相关的数，这些数可以表示从一个顶点到 另一个顶点的距离或耗费。另一个顶点的距离或耗费。网：网：网：网：带权的图。带权的图。北北 京京 上上 海海 12000 15000 北北 京京 上上 海海 1785 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中v3 v4 v5 子图：子图：子图：子图：如果图如果图 G=(V,E)和和 G=(V,E)，满足：满足：V V 且且 E E，则，则称称 G为为G 的子图的子图。v2 v1 v3 v4 v2 v1 v3 v4 v5 v1 v1 v3 v2 v1 v4 v2 v1 v5 v2 v1 v4 v5 v2 v1 v5 邻接点：邻接点：邻接点：邻接点：若若(v,v)是一条边，则称顶点是一条边，则称顶点 v 和和 v互为邻接点互为邻接点，或称或称 v 和和 v相邻接；称边相邻接；称边(v,v)依附依附依附依附于顶点于顶点 v 和和 v，或称，或称(v,v)与顶点与顶点 v 和和 v 相关联相关联相关联相关联。若若 是一条弧是一条弧，则称顶点则称顶点 v 邻接邻接到到到到 v，顶点，顶点 v 邻接邻接自自自自 顶点顶点 v。并称弧并称弧 与顶点与顶点 v 和和 v 相关联相关联相关联相关联。v2 v1 v4 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中 度：度：度：度：无向图无向图中顶点中顶点 v 的度是和的度是和 v 相关联的边的数目，记为：相关联的边的数目，记为：TD(v)。v2 v1 v3 v4 v5 入度：入度：入度：入度：有向图有向图中以顶点中以顶点 v 为头的弧的数目称为为头的弧的数目称为 v 的入度的入度，记记 为：为：ID(v)。出度：出度：出度：出度：有向图有向图中以顶点中以顶点 v 为尾的弧的数目称为为尾的弧的数目称为 v 的出度的出度，记记 为：为：OD(v)。度：度：度：度：入度和出度之和，即：入度和出度之和，即：TD(v)=ID(v)+OD(v)。v2 v1 v3 v4 如果顶点如果顶点 vi 的度为的度为 TD(vi)，则一个有则一个有 n 个顶点个顶点 e 条边（弧）条边（弧）的图，满足如下关系：的图，满足如下关系：数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中 路径：路径：路径：路径：从顶点从顶点 v 到到 v 的路径是一个顶点序列的路径是一个顶点序列(v=vi,0,vi,1,vi,m=v)，满足满足(vi,j-1,vi,j)VR 或或 VR，(1 j m)。对于有向图，路径也是有向的。对于有向图，路径也是有向的。v2 v1 v3 v4 v5 v2 v1 v3 v4 路径长度：路径长度：路径长度：路径长度：路径上边或弧的数目。路径上边或弧的数目。回路（环）：回路（环）：回路（环）：回路（环）：第一个顶点和最后一个顶点相同的路径。第一个顶点和最后一个顶点相同的路径。简单路径：简单路径：简单路径：简单路径：序列中顶点（两序列中顶点（两端点除外端点除外）不重复出现的路径。）不重复出现的路径。简单回路（简单环）：简单回路（简单环）：简单回路（简单环）：简单回路（简单环）：前后两端点相同的简单路径。前后两端点相同的简单路径。连通：连通：连通：连通：从顶点从顶点 v 到到 v 有路径，则说有路径，则说 v 和和 v 是连通的是连通的。连通图：连通图：连通图：连通图：图中任意两个顶点都是连通的。图中任意两个顶点都是连通的。v2 v1 v3 v4 v5 非连通图：非连通图：非连通图：非连通图：有有 n 个顶点和小于个顶点和小于 n-1 条边的图。条边的图。数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中 连通分量：连通分量：连通分量：连通分量：无向图的极大连通子图（无向图的极大连通子图（不存在包含它的更大的不存在包含它的更大的 连通子图连通子图）；任何连通图的连通分量只有一个，即其本身；非连；任何连通图的连通分量只有一个，即其本身；非连 通图有多个连通分量（通图有多个连通分量（非连通图的每一个连通部分非连通图的每一个连通部分）。）。v2 v1 v3 v4 v5 v2 v1 v3 v4 v5 强连通图：强连通图：强连通图：强连通图：任意两个顶点都连通的有向图。任意两个顶点都连通的有向图。v2 v1 v3 v4 强连通分量：强连通分量：强连通分量：强连通分量：有向图的极大强连通子图；任何强连通图的强有向图的极大强连通子图；任何强连通图的强 连通分量只有一个，即其本身；非强连通图有多个强连通分量。连通分量只有一个，即其本身；非强连通图有多个强连通分量。v2 v1 v3 v4 v2 v1 v3 v4 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中 生成树：生成树：生成树：生成树：所有顶点均由边连接在一起，但不存在回路的图。所有顶点均由边连接在一起，但不存在回路的图。v2 v1 v3 v4 v5 v2 v1 v3 v4 v5 v2 v1 v3 v4 v5 v2 v1 v3 v4 v5 v 一个图可以有许多棵不同的生成树。一个图可以有许多棵不同的生成树。注注v 所有生成树具有以下共同特点：所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同；生成树的顶点个数与图的顶点个数相同；生成树是图的极小连通子图；生成树是图的极小连通子图；一个有一个有 n 个顶点的连通图的生成树有个顶点的连通图的生成树有 n-1 条边；条边；生成树中任意两个顶点间的路径是唯一的；生成树中任意两个顶点间的路径是唯一的；在生成树中再加一条边必然形成回路。在生成树中再加一条边必然形成回路。v 含含 n 个顶点个顶点 n-1 条边的图不一定是生成树。条边的图不一定是生成树。v2 v1 v3 v4 v5 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中 生成森林：生成森林：生成森林：生成森林：对于非连通图，其每个连通分量可以构造一棵生对于非连通图，其每个连通分量可以构造一棵生 成树，合成起来就是一个生成森林。成树，合成起来就是一个生成森林。有向树：有向树：有向树：有向树：如果一个有向图恰有一个顶点的入度为如果一个有向图恰有一个顶点的入度为 0，其余顶，其余顶 点的入度均为点的入度均为 1，则是一棵有向树。，则是一棵有向树。有向图的生成森林有向图的生成森林有向图的生成森林有向图的生成森林：由若干棵有向树组成，含有图中全部顶由若干棵有向树组成，含有图中全部顶 点，但只有足以构成若干棵不相交的有向树的弧。点，但只有足以构成若干棵不相交的有向树的弧。B A CF ED B A DF EC 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中7.2 图的存储结构图的存储结构 多重链表多重链表 v1v2 v4 v3 v1 v2 v4 v5 v3 v2 v1 v3 v4 G1 v2 v1 v3 v4 v5 G2 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中7.2.1 数组表示法（邻接矩阵表示法）数组表示法（邻接矩阵表示法）对于一个具有对于一个具有 n 个顶点的图，可用两个数组存储。其中一个个顶点的图，可用两个数组存储。其中一个 一维数组一维数组存储数据元素（存储数据元素（顶点顶点）的信息，另一个）的信息，另一个二维数组二维数组二维数组二维数组（图的（图的 邻接矩阵邻接矩阵邻接矩阵邻接矩阵）存储数据元素之间的关系（）存储数据元素之间的关系（边或弧边或弧边或弧边或弧）的信息。）的信息。邻接矩阵：邻接矩阵：邻接矩阵：邻接矩阵：设设 G=(V,VR)是具有是具有 n 个顶点的图，顶点的顺个顶点的图，顶点的顺 序依次为序依次为 v1,v2,vn，则则 G 的邻接矩阵是具有如下性质的的邻接矩阵是具有如下性质的 n 阶阶 方阵：方阵：数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中v2 v1 v3 v4 G1 v2 v1 v3 v4 v5 G2 v1 v2 v3 v4 v1 v2 v3 v4 v5 v1 v2 v3 v4 v1 v2 v3 v4 v5 特点：特点：无向图的邻接矩阵对称，可压缩存储；有无向图的邻接矩阵对称，可压缩存储；有 n 个顶点的无向图需个顶点的无向图需 存储空间为存储空间为 n(n-1)/2。有向图邻接矩阵不一定对称；有有向图邻接矩阵不一定对称；有 n 个顶点的有向图需存储空间个顶点的有向图需存储空间 为为 n，空间复杂度为空间复杂度为 O(n2)，用于稀疏图时空间浪费严重。用于稀疏图时空间浪费严重。无向图中顶点无向图中顶点 vi 的度的度 TD(vi)是邻接矩阵中第是邻接矩阵中第 i 行行 1 的个数。的个数。有向图中有向图中 顶点顶点 vi 的的出度出度出度出度是邻接矩阵中第是邻接矩阵中第 i 行行行行 1 的个数。的个数。顶点顶点 vi 的的入入入入度度度度是邻接矩阵中第是邻接矩阵中第 i 列列列列 1 的个数。的个数。数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中网的邻接矩阵可定义为：网的邻接矩阵可定义为：v2 v1 v3 v4 v5 v6 5 4 8 9 7 5 5 6 1 3 v1 v2 v3 v4 v5 v6 v1 v2 v3 v4 v5 v6 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中图的数组（邻接矩阵）存储表示：图的数组（邻接矩阵）存储表示：#define INFINITY INT_MAX/最大值最大值#define MAX_VERTEX_NUM 20/最大顶点个数最大顶点个数 typedef enum DG,DN,AG,AN GraphKind;/有向图有向图,有向网有向网,无向图无向图,无向网无向网 typedef struct ArcCell VRType adj;/VRType是顶点关系类型。对无权图，用是顶点关系类型。对无权图，用 1 或或 0 表示相邻否；表示相邻否；/对带权图，则为权值类型。对带权图，则为权值类型。InfoType *info;/该弧相关信息的指针该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM;/顶点向量顶点向量 AdjMatrix arcs;/邻接矩阵邻接矩阵 int vexnum,arcnum;/图的当前顶点数和弧图的当前顶点数和弧(边边)数数 GraphKind kind;/图的种类标志图的种类标志 MGraph;数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中7.2.2 邻接表（邻接表（类似于树的孩子链表表示法类似于树的孩子链表表示法）头结点头结点 data firstarc 表结点表结点 adjvex nextarc info v2 v1 v3 v4 v5 G2 v1 v3 v4 v2 v5 0 1 2 3 4 3 1 4 2 0 4 3 1 2 0 2 1 链域链域链域链域，指示下一条边或弧。，指示下一条边或弧。特点：特点：若无向图中有若无向图中有 n 个顶点、个顶点、e 条边，则其邻接表需条边，则其邻接表需 n 个头结点和个头结点和 2e 个个表结点。适宜存储稀疏图表结点。适宜存储稀疏图。无向图中顶点无向图中顶点 vi 的度为第的度为第 i 个单链表中的结点数。个单链表中的结点数。邻接点域邻接点域邻接点域邻接点域，存放与，存放与 vi 邻接的邻接的 顶顶点在表头数组中的位置。点在表头数组中的位置。数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中v2 v1 v3 v4 G1 0 1 2 3 2 1 3 0 v1 v3 v4 v2 0 1 2 3 3 0 2 v1 v3 v4 v2 0 邻接表邻接表 逆邻接表逆邻接表 顶点顶点 vi 的的出度出度出度出度为第为第 i 个单链个单链 表中的结点个数。表中的结点个数。特点：特点：顶点顶点 vi 的的入度入度入度入度为整个为整个单链表单链表 中邻接点域值是中邻接点域值是 i-1 的结点的结点 个数个数。找出度易，找入度难。找出度易，找入度难。找入度易，找出度难。找入度易，找出度难。顶点顶点 vi 的的入度入度入度入度为第为第 i 个单链个单链 表中的结点个数。表中的结点个数。顶点顶点 vi 的的出度出度出度出度为整个为整个单链表单链表 中邻接点域值是中邻接点域值是 i-1 的结点的结点 个数个数。数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中图的邻接表存储表示：图的邻接表存储表示：#define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置该弧所指向的顶点的位置 struct ArcNode *nextarc;/指向下一条弧的指针指向下一条弧的指针 InfoType *info;/该弧相关信息的指针该弧相关信息的指针 ArcNode;typedef struct VNode VertexType data;/顶点信息顶点信息 ArcNode *firstarc;/指向第一条依附该顶点的弧指向第一条依附该顶点的弧 VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数图的当前顶点数和弧数 int kind;/图的种类标志图的种类标志 ALGraph;数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中弧结点弧结点 第一条入弧第一条入弧 第一条出弧第一条出弧 弧尾位置弧尾位置 弧头位置弧头位置 弧头相同的下一条弧弧头相同的下一条弧 弧尾相同的下一条弧弧尾相同的下一条弧 a b c d 01237.2.3 十字链表十字链表 0 12 00 2 3 0 3 1 3 2 2 3 bdactailvex headvex hlink tlinkdata firstin firstout顶点结点顶点结点 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中#define MAX_VERTEX_NUM 20 typedef struct ArcBox int tailvex,headvex;/该弧的尾和头顶点的位置该弧的尾和头顶点的位置 struct ArcBox *hlink,*tlink;/分别指向下一个弧头相同和弧尾相同的弧的指针域分别指向下一个弧头相同和弧尾相同的弧的指针域 InfoType*info;/该弧相关信息的指针该弧相关信息的指针 ArcBox;typedef struct VexNode VertexType data;ArcBox *firstin,*firstout;/分别指向该顶点第一条入弧和出弧分别指向该顶点第一条入弧和出弧 VexNode;typedef struct VexNode xlistMAX_VERTEX_NUM;/表头向量表头向量 int vexnum,arcnum;/有向图的当前顶点数和弧数有向图的当前顶点数和弧数 OLGraph;有向图的十字链表存储表示：有向图的十字链表存储表示：数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中 指向依附于指向依附于 ivex 的下一条边的下一条边 7.2.3 邻接多重表（无向图的另一种链式存储结构）邻接多重表（无向图的另一种链式存储结构）邻接表优点：邻接表优点：容易求得顶点和边的信息。容易求得顶点和边的信息。缺点：缺点：某些操作不方便（如：删除一条边需找表示此某些操作不方便（如：删除一条边需找表示此 边的两个结点）。边的两个结点）。邻接多重表：邻接多重表：每条边用一个结点表示。每条边用一个结点表示。其结点结构如下：其结点结构如下：指向依附于指向依附于 jvex 的下一条边的下一条边 mark ivex ilink jvex jlink info 边结点边结点 data firstedge 顶点结点顶点结点 存与顶点有关的信息存与顶点有关的信息指向第一条依附于该顶点的边指向第一条依附于该顶点的边 标志域标志域 标记此边是标记此边是 否被搜索过否被搜索过 该边依附的两个顶点在表头数组中位置该边依附的两个顶点在表头数组中位置 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中 0 3 0 1 2 3 4 v2 v1 v3 v4 v5 G2 v1 v2 v3 v4 v5 0 1 2 3 2 1 2 4 4 1 指向依附于指向依附于 ivex 的下一条边的下一条边 指向依附于指向依附于 jvex 的下一条边的下一条边 mark ivex ilink jvex jlink info 边结点边结点 标志域标志域 标记此边是标记此边是 否被搜索过否被搜索过 该边依附的两个顶点在表头数组中位置该边依附的两个顶点在表头数组中位置 data firstedge 顶点结点顶点结点 存与顶点有关的信息存与顶点有关的信息指向第一条依附于该顶点的边指向第一条依附于该顶点的边数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中#define MAX_VERTEX_NUM 20 typedef emnu unvisited,visited VisitIf;typedef struct Ebox VisitIf mark;/访问标记访问标记 int ivex,jvex;/该边依附的两个顶点的位置该边依附的两个顶点的位置 struct EBox *ilink,*jlink;/分别指向依附这两个顶点的下一条边分别指向依附这两个顶点的下一条边 InfoType *info;/该边信息指针该边信息指针 EBox;typedef struct VexBox VertexType data;EBox *firstedge;/指向第一条依附该顶点的边指向第一条依附该顶点的边 VexBox;typedef struct VexBox adjmulistMAX_VERTEX_NUM;int vexnum,edgenum;/无向图的当前顶点数和边数无向图的当前顶点数和边数 AMLGraph;无向图的邻接多重表存储表示：无向图的邻接多重表存储表示：数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中7.3 图的遍历图的遍历 从图的任意指定顶点出发，依照某种规则去访问图中所有顶从图的任意指定顶点出发，依照某种规则去访问图中所有顶 点，且每个顶点仅被访问一次，这一过程叫做点，且每个顶点仅被访问一次，这一过程叫做图的遍历图的遍历图的遍历图的遍历。图的遍历按照深度优先和广度优先规则去实施，通常有图的遍历按照深度优先和广度优先规则去实施，通常有深度深度深度深度 优先遍历法优先遍历法优先遍历法优先遍历法（Depth_First SearchDFS）和和 广度优先遍历法广度优先遍历法广度优先遍历法广度优先遍历法（Breadth_Frist SearchBFS）两种。两种。V1V2V4V5V3V7V6V8数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中7.3.1 深度优先遍历（深度优先遍历（DFS）方法：方法：方法：方法：1、访问指定的起始顶点；访问指定的起始顶点；2、若、若当前访问的顶点当前访问的顶点的邻接顶点有的邻接顶点有未被访问的未被访问的未被访问的未被访问的，则任选，则任选 一个访问之；反之，一个访问之；反之，退回退回退回退回到最近访问过的顶点；直到到最近访问过的顶点；直到 与起始顶点相通的全部顶点都访问完毕；与起始顶点相通的全部顶点都访问完毕；3、若此时图中尚有顶点未被访问，则再选其中一个顶点若此时图中尚有顶点未被访问，则再选其中一个顶点 作为起始顶点并访问之，转作为起始顶点并访问之，转 2；反之，遍历结束。反之，遍历结束。例：例：V1 V1V2V4V5V3V7V6V8顶点访问次序：顶点访问次序：V2 V4 V8 V5 V3 V6 V7 V1 V2 V5 V8 V4 V3 V6 V7 V1 V2 V4 V8 V5 V3 V7 V6 V1 V2 V5 V8 V4 V3 V7 V6 V1 V3 V6 V7 V2 V4 V8 V5 连通图的深度优先遍历类似于树的先根遍历连通图的深度优先遍历类似于树的先根遍历 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中abchdekfga c h dfke b g顶点访问次序顶点访问次序:例：例：a c h dfke g ba c h fked b g解决办法：解决办法：为每个顶点设立一个为每个顶点设立一个“访问标志访问标志”。如何判别如何判别V的邻接点是否被访问？的邻接点是否被访问？首先将图中每个顶点的访问标志设为首先将图中每个顶点的访问标志设为 FALSE,之后搜索图之后搜索图 中每个顶点，如果未被访问，则以该顶点为起始点，进行深度中每个顶点，如果未被访问，则以该顶点为起始点，进行深度 优先遍历，否则继续检查下一顶点。优先遍历，否则继续检查下一顶点。数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中 1 3 7 4 0 V1 V2 V4 V8 V5 V3 实现：实现：V1V2V4V5V3V7V6V80 1 2 3 4 5 6 7 V1 V2 V3 V4 V5 V6 V7 V8 2 1 0 1 0 1 2 2 3 3 5 4 6 7 7 6 5 4 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 2 V6 5 V7 6 1 1 1 1 1 1 1 1 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中 1 3 7 0 V1 V2 V4 V8 V5 V3 0 1 2 3 4 5 6 7 V1 V2 V3 V4 V5 V6 V7 V8 2 1 3 1 5 6 7 7 6 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 2 V6 5 V7 6 V1V2V4V5V3V7V6V84 1 1 1 1 1 1 1 1 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中7.3.2 广度优先遍历（广度优先遍历（BFS）方法：方法：方法：方法：从图的某一结点出发，首先依次访问该结点的所有邻从图的某一结点出发，首先依次访问该结点的所有邻 接顶点接顶点 Vi1,Vi2,Vin 再按这些顶点被访问的先后次序依次访问再按这些顶点被访问的先后次序依次访问 与它们相邻接的所有未被访问的顶点，重复此过程，直至所有顶与它们相邻接的所有未被访问的顶点，重复此过程，直至所有顶 点均被访问为止。点均被访问为止。例：例：V1V2V4V5V3V7V6V8广度优先遍历：广度优先遍历：V1 V2 V3 V4 V5 V6 V7 V8 V1 V3 V2 V7 V6 V5 V4 V8 V1 V2 V3 V5 V4 V7 V6 V8 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中abchdekfga c d e fh k bg顶点访问次序顶点访问次序:例：例：a c d e fh k gb数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中 1 3 4 0 V1 V2 V3 V4 V5 V6 实现：实现：V1V2V4V5V3V7V6V80 1 2 3 4 5 6 7 V1 V2 V3 V4 V5 V6 V7 V8 2 1 0 1 0 1 2 2 3 3 5 4 6 7 7 6 5 4 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 2 V7 5 V8 F R R F R R F R R F 6 7 F F F F F R R R 1 1 1 1 1 1 1 1 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中开始开始访问访问V0，置置标志标志求求V邻接点邻接点ww存在吗存在吗V下一邻接点下一邻接点ww访问过访问过结束结束NYNYBFS初始化队列初始化队列V0入队入队队列空吗队列空吗队头队头V出队出队访问访问w，置置标志标志w入队入队NY数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中7.4 图的连通性问题图的连通性问题 7.4.1 无向图的连通分量和生成树无向图的连通分量和生成树 V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8 设图设图 G=(V,E)是个连通图，当从图任一顶点出发遍历图是个连通图，当从图任一顶点出发遍历图 G 时，将边集时，将边集 E(G)分成两个集合分成两个集合 T(G)和和 B(G)。其中。其中 T(G)是遍历图时所经过的边的集合，是遍历图时所经过的边的集合，B(G)是遍历图时未经过的边是遍历图时未经过的边 的