数据结构图总结.ppt

数据结构数据结构 第七章第七章 图图7.1 图的定义和术语图的定义和术语 定义：定义： 图图 (Graph) 是一种复杂的非线性数据结构，由顶是一种复杂的非线性数据结构，由顶 点集合及顶点间的关系（也称弧或边）集合组成。可点集合及顶点间的关系（也称弧或边）集合组成。可 以表示为：以表示为：G(V, VR) 其中其中 V 是是顶点顶点的有穷非空集合；的有穷非空集合； VR 是是顶点之间关系顶点之间关系 的有穷集合，也叫做的有穷集合，也叫做弧弧或或边边集合。弧集合。弧是顶点的有序对，是顶点的有序对， 边是顶点的无序对边是顶点的无序对。数据结构数据结构 第七章第七章 图图 所有顶点均由边连接在一起，但不存在回路的图。所有顶点均由边连接在一起，但不存在回路的图。 v 一个图可以有许多棵不同的生成树。一个图可以有许多棵不同的生成树。 注注v 所有生成树具有以下共同特点：所有生成树具有以下共同特点： 生成树的顶点个数与图的顶点个数相同；生成树的顶点个数与图的顶点个数相同； 生成树是图的极小连通子图；生成树是图的极小连通子图； 一个有一个有 n 个顶点的连通图的生成树有个顶点的连通图的生成树有 n-1 条边；条边； 生成树中任意两个顶点间的路径是唯一的；生成树中任意两个顶点间的路径是唯一的； 在生成树中再加一条边必然形成回路。在生成树中再加一条边必然形成回路。 v 含含 n 个顶点个顶点 n-1 条边的图不一定是生成树。条边的图不一定是生成树。 数据结构数据结构 第七章第七章 图图7.2 图的存储结构图的存储结构 7.2.1 数组表示法（邻接矩阵表示法）数组表示法（邻接矩阵表示法） 特点：特点： 无向图的邻接矩阵对称，可压缩存储；有无向图的邻接矩阵对称，可压缩存储；有 n 个顶点的无向图个顶点的无向图 需存储空间为需存储空间为 n(n-1)/2。 有向图邻接矩阵不一定对称；有有向图邻接矩阵不一定对称；有 n 个顶点的有向图需存储空个顶点的有向图需存储空 间为间为n，空间复杂度为，空间复杂度为O(n2)，用于稀疏图时空间浪费严重。，用于稀疏图时空间浪费严重。 无向图中顶点无向图中顶点 vi 的度的度 TD(vi) 是邻接矩阵中第是邻接矩阵中第 i 行行 1 的个数。的个数。 有向图中有向图中 顶点顶点 vi 的的是邻接矩阵中第是邻接矩阵中第 i 1 的个数。的个数。 顶点顶点 vi 的的是邻接矩阵中第是邻接矩阵中第 i 1 的个数。的个数。 数据结构数据结构 第七章第七章 图图7.2.2 邻接表（邻接表（类似于树的孩子链表表示法类似于树的孩子链表表示法） 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 个单链表中的结点数。个单链表中的结点数。 数据结构数据结构 第七章第七章 图图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 的结点的结点 个数个数。 数据结构数据结构 第七章第七章 图图弧结点弧结点 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顶点结点顶点结点 数据结构数据结构 第七章第七章 图图 指向依附于指向依附于 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 mark ivex ilink jvex jlink info 边结点边结点 data firstedge 顶点结点顶点结点 7.2.3 邻接多重表（无向图的另一种链式存储结构）邻接多重表（无向图的另一种链式存储结构） 数据结构数据结构 第七章第七章 图图7.3 图的遍历图的遍历 深度优先遍历深度优先遍历（Depth_First SearchDFS ） 广度优先遍历广度优先遍历（Breadth_Frist SearchBFS）7.4.3 最小生成树最小生成树 构造最小生成树方法：构造最小生成树方法： 方法一：普里姆方法一：普里姆 (Prim) 算法。算法。 方法二：克鲁斯卡尔方法二：克鲁斯卡尔 (Kruskal) 算法。算法。 最小生成树最小生成树 可能不惟一可能不惟一 V1V6V5V4V3V26513566425数据结构数据结构 第七章第七章 图图 在有向图中选一个没有前驱的顶点且输出之。在有向图中选一个没有前驱的顶点且输出之。 从图中删除该顶点和所有以它为尾的弧。从图中删除该顶点和所有以它为尾的弧。 重复上述两步，直至全部顶点均已输出；或者当图中重复上述两步，直至全部顶点均已输出；或者当图中 不存在无前驱的顶点为止不存在无前驱的顶点为止 一个一个AOV网的拓扑序列不是唯一的网的拓扑序列不是唯一的 数据结构数据结构 第七章第七章 图图7.5.2 关键路径关键路径 把工程计划表示为有向图，用把工程计划表示为有向图，用顶点顶点表示表示事件事件，弧弧表示表示活活 动动，弧的弧的权权表示表示活动持续时间活动持续时间。每个事件表示在它之前的活。每个事件表示在它之前的活 动已经完成，在它之后的活动可以开始。称这种有向图为动已经完成，在它之后的活动可以开始。称这种有向图为络，简称为络，简称为。 对于对于AOE网，我们关心两个问题：网，我们关心两个问题： (1) 完成整项工程至少需要完成整项工程至少需要 多少时间？多少时间？ (2) 求关键路径步骤：求关键路径步骤： 求求 ve(i)、vl(j) 求求 e(i)、l(i) 计算计算 l(i) - e(i)数据结构数据结构 第七章第七章 图图7.6 最短路径最短路径 7.6.1 单源点最短路径（单源点最短路径（从某个源点到其余各顶点的最短路径从某个源点到其余各顶点的最短路径） 迪杰斯特拉（迪杰斯特拉（Dijkstra）算法：）算法： 按路径长度递增次序产生各顶点的最短路径。按路径长度递增次序产生各顶点的最短路径。 7.6.2 每一对顶点之间的最短路径每一对顶点之间的最短路径 方法一：方法一：每次以一个顶点为源点，每次以一个顶点为源点， 重复执行重复执行 Dijkstra 算法算法 n 次次。 方法二：方法二：弗洛伊德弗洛伊德 (Floyd) 算法算法 算法思想：算法思想：逐个顶点试探，从逐个顶点试探，从 vi 到到 vj 的所有可能存在的所有可能存在 的路径中，选出一条长度最短的路径。的路径中，选出一条长度最短的路径。