解决图的编程问题.ppt

解决图的编程问题 数据结构 C 语言版 目标 在本章中 你将学到 在图中存储数据图的深度优先搜索和广度优先搜索算法最小生成树图的最短路径 学习情境 用图高速公路交通网的编程 问题描述 一个地区由许多城市组成 为实现城市间的高速运输 需要在这些城市间铺设高速公路 以达到任意两个城市间高速运输的目的 经过考察和预算 铺设的高速公路交通网如图9 1所示 其中每个顶点代表一个城市 顶点间的连线代表两个城市间铺设的高速公路 而线上的数字表示两个城市间的距离 单位 公理 如图所示 请根据上面的描述 解决下面的问题 用C 编写一程序来存储该高速公路交通网的信息 从任何一个城市出发 访问所有的城市 给出访问城市的顺序 如果想从一个城市到另一个城市旅行 给出最短的旅行路线 图是一系列顶点 结点 和描述顶点之间的关系边 弧 组成 图是数据元素的集合 这些数据元素被相互连接以形成网络 其形式化定义为 G V E V Vi Vi 某个数据元素集合 E Vi Vj Vi Vj V P Vi Vj 认识图 图的定义和术语 1 图的定义 其中 G表示图 V是顶点的集合 E是边或弧的集合 在集合E中 P Vi Vj 表示顶点Vi和顶点Vj之间有边或弧相连 认识图 图的定义和术语 2 图的术语 顶点集 图中具有相同特性的数据元素的集合称为顶点集边 弧 边是一对顶点间的路径 通常带箭头的边称为弧弧头 每条箭头线的头顶点表示构成弧的有序对中的后一个弧尾 每条箭头线的尾顶点表示构成弧的有序对中的前一个顶点 称为弧尾或始点 度 在无向图中的顶点的度是指连那个顶点的边的数量 在有向图中 每个顶点有两种类的的度 出度和入度 入度 顶点的入度是指向那个顶点的边的数量 出度 顶点的出度是由那个顶点出发的边的数量 权 有些图的边 或弧 附带有一些数据信息 这些数据信息称为边 或弧 的权 weigh 认识图 图的定义和术语 3 图的分类 有向图 在一个图中 如果任意两顶点构成的偶对 Vi Vj 是有序的 那么称该图为有向图 这里Vi是弧尾 Vj是弧头 这表示有一个从顶点Vi到顶点Vj的路径 但是从Vj到Vi是不可能的无向图 在一个图中 如果有任意两顶点构成的边 Vi Vj Vi Vj 和 Vj Vi 是相同的在一个无向图中 如果任意两个顶点之间都有边相连 则称该图为无向完全图 无向完全图又称完全图在一个有向图 如果任意两个顶点之间都是弧相连 则称该图为有向完全图 有很少条边或弧的图称为稀疏图 反之称为稠密图 SetNode 在图中增加一个新的顶点GetNode 获取图中指定顶点SetEdge 在两个顶点之间添加指定权值的边或弧GetEdge 获取两个顶点之间的边DelEdge 删除两个顶点之间的边或弧GetNumOfVertex 获取邻接矩阵顶点数GetNumOfEdge 获取邻接矩阵边或弧的数目GetIndex 获取指定顶点在数组中的索引IsEdge 判断两个顶点之间是否存在边或弧IsNode 判断指定结点是否是图的顶点 认识图 识别图的基本操作 图的基本操作有以下几种 邻接矩阵 AdjacentcyMatrix 是用两个数组来表示图 一个数组是一维数组 存储图中的顶点信息 一个数组是二维数组 即矩阵 存储顶点之间相邻的信息 也就是边 或弧 的信息 如果图中有n个顶点 你需要大小为n n的二维数组来表示图 用C 语言表示邻接矩阵的代码参见P190页 用邻接矩阵解决图的编程问题 用邻接矩阵表示图 对邻接矩阵进行操作参见P191页代码 邻接表的存储方法是一种顺序存储与链式存储相结合的存储方法 顺序存储部分用来保存图中顶点的信息 链式存储部分用来保存图中边 或弧 的信息 具体的做法是 使用一个一维数组 其中每个数组元素包含两个域 其结构如右图所示 其中顶点域 data 存放与顶点有关的信息 头指针域 firstadj 存放与该顶点相邻接的所有顶点组成的单链表的头指针 用邻接表解决图的编程问题 用邻接表表示图 邻接单链表中每个结点表示依附于该顶点的一条边 称作边结点 边结点的结构如右图所示 其中邻接点域 adjvex 指示与顶点邻接点在图中的位置 对应着一维数组中的序号 对于有向图 存放的是该边结点所表示的弧的弧头顶点在一维数组中的序号 数据域 info 存储边或弧相关的信息 如权值等 当图中边 或弧 不含有信息时 该域可以省略 链域 nextadj 指向依附于该顶点的下一个边结点的指针 无向图邻接表的邻接表结点类的代码参见P197页 用邻接表解决图的编程问题 用邻接表表示图 举例 对邻接表进行操作的代码参见P199页 9 4解决图的遍历问题 深度优先搜索 1 理解深度优先搜索算法 从图的某一顶点x出发 访问x 然后遍历任何一个与x相邻的未被访问的顶点y 再遍历任何一个与y相邻的未被访问的顶点z 如此下去 直到到达一个所有邻接点都被访问的顶点为止 然后依次回退到尚有邻接点未被访问过的顶点 重复上述过程 直到图中的全部顶点都被访问过为止 对图进行深度优先遍历 深度优先遍历背后基于堆栈 有2种形式 第一种是程序中显示构造堆栈 利用压栈出栈操作实现 第二种是利用递归函数调用 基于递归程序栈实现 本章介绍压栈和出栈的操作 v1 将起始顶点v1压入栈 9 4解决图的遍历问题 深度优先搜索 v1 将顶点v1弹出栈访问v1在栈中压入所有与v1相邻接的未访问顶点 v1 Visited 9 4解决图的遍历问题 深度优先搜索 v4 从栈中弹出顶点v1访问v1在栈中压入所有与v1相邻接的未访问顶点 v1 Visited v2 9 4解决图的遍历问题 深度优先搜索 Visited 从栈中弹出顶点v2访问v2在栈中压入所有与v2相邻接的未访问顶点 v1 v2 v4 v2 9 4解决图的遍历问题 深度优先搜索 Visited 从栈中弹出顶点v2访问v2在栈中压入所有与v2相邻接的未访问顶点 v1 v2 v3 v6 v4 9 4解决图的遍历问题 深度优先搜索 Visited 从栈中弹出顶点v3访问v3在栈中压入所有与v3相邻接的未访问顶点 v1 v2 v3 有与v3相邻接的未访问顶点 v6 v3 v4 9 4解决图的遍历问题 深度优先搜索 Visited 从栈中弹出顶点v3访问v3在栈中压入所有与v3相邻接的未访问顶点 v1 v2 v3 有与v3相邻接的未访问顶点 v6 v5 v4 9 4解决图的遍历问题 深度优先搜索 Visited 从栈中弹出顶点v5访问v5在栈中压入所有与v5相邻接的未访问顶点 v1 v2 v3 v5 v6 v4 9 4解决图的遍历问题 深度优先搜索 v5 Visited 从栈中弹出顶点v6访问v6在栈中压入所有与v6相邻接的未访问顶点 v1 v2 v3 v5 v6 v6 v4 9 4解决图的遍历问题 深度优先搜索 Visited 从栈中弹出顶点v4访问v4在栈中压入所有与v4相邻接的未访问顶点 v1 v2 v3 v5 v6 v4 v4 9 4解决图的遍历问题 深度优先搜索 Visited 栈现在是空的因此 遍历完成 v1 v2 v3 v5 v6 v4 9 4解决图的遍历问题 深度优先搜索 尽管上述算法提供了一个简单和常用的方法来遍历图 但是 如果图不是连接的 算法将不能正确工作 在这样的情况下 你将不能够从单个起始顶点开始遍历所有顶点 9 4解决图的遍历问题 深度优先搜索 为了解决这个问题 你需要对图中所有未访问顶点重复执行上述算法 对图中每个顶点v重复步骤2如果v未被访问 a 调用DFS v 9 4解决图的遍历问题 深度优先搜索 9 4解决图的遍历问题 广度优先搜索 2 理解广度优先搜索算法 图的广度优先搜索是从图的某个顶点x出发 访问x 然后访问与x相邻接的所有未被访问的顶点x1 x2 xn 接着再依次访问与x1 x2 xn相邻接的未被访问过的所有顶点 依此类推 直至图的每个顶点都被访问 访问v1将v1插入队列 v1 v1 9 4解决图的遍历问题 广度优先搜索 从队列中删除顶点v1访问与v1相邻接的所有未访问顶点并将它们插入队列 v1 v1 Visited 9 4解决图的遍历问题 广度优先搜索 从队列中删除顶点v1访问与v1相邻接的所有未访问顶点并将它们插入队列 v2 v1 v2 v4 v4 9 4解决图的遍历问题 广度优先搜索 从队列中删除顶点v2访问与v2相邻接的所有未访问顶点并将它们插入队列 v2 v1 v2 v4 v4 9 4解决图的遍历问题 广度优先搜索 从队列中删除顶点v4访问与v4相邻接的所有未访问顶点并将它们插入队列 v1 v2 v4 v4 v3 v3 v6 v6 v5 v5 9 4解决图的遍历问题 广度优先搜索 从队列中删除顶点v3访问与v3相邻接的所有未访问顶点并将它们插入队列 v1 v2 v4 v3 v3 v6 v6 v5 v5 v3没有任何未访问的邻接顶点 9 4解决图的遍历问题 广度优先搜索 从队列中删除顶点v6访问与v6相邻接的所有未访问顶点并将它们插入队列 v1 v2 v4 v3 v6 v6 v5 v5 v3没有任何未访问的邻接顶点 9 4解决图的遍历问题 广度优先搜索 从队列中删除顶点v5访问与v5相邻接的所有未访问顶点并将它们插入队列 v1 v2 v4 v3 v6 v5 v5 v6没有任何未访问的邻接顶点 9 4解决图的遍历问题 广度优先搜索 队列现在是空的因此 遍历完成 v1 v2 v4 v3 v6 v5 v5没有任何未访问的邻接顶点 9 4解决图的遍历问题 广度优先搜索 尽管上述算法提供了一个简单和方便的遍历图的方法 但是 如果图不是连接的 算法将不能正确工作 在这样的情况中 你将不能从单个开始顶点遍历所有顶点 9 4解决图的遍历问题 广度优先搜索 为了解决这个问题 你需要对图中的未访问顶点重复执行这个算法 为图中每个顶点V重复步骤2 如果v未被访问 a 调用BFS v 9 4解决图的遍历问题 广度优先搜索 图的最短路径问题 Dijkstra算法的引入 Dijkstra算法的基本思想是 设置两个顶点集合T和S 集合S中存放己经找到最短路径的顶点 集合T中存放当前还未找到最短路径的顶点 初始状态时 集合S中只包含源点v0 然后不断从集合T中选取到源点v0路径长度最短的顶点w加入集合S 集合S中每加入一个新的顶点w 都要修改顶点v0到集合T中剩余顶点的最短路径长度值 集合T中各顶点新的最短路径长度值为原来最短路径长度值与顶点w的最短路径长度加上w到该顶点的路径长度值中的较小值 此过程不断重复 直到集合T的顶点全部加入集合S为止 图的最短路径问题 分析高速公路交通网的最短路径 下面用Dijkstra算法解决高速公路最短路径的问题 现在假设高速公路交通网采用邻接矩阵作为存储结构 若邻接矩阵为matrix 并规定 用Dijkstra算法来确定从城市A到其他城市的最短践离 Dijkstra算法的步骤参见教材P212页 final distance 1 1 0 0 0 0 0 90 150 180 图的最短路径问题 分析高速公路交通网的最短路径 A B C D E F 0 1 2 3 4 5 final distance 1 1 0 0 0 0 0 90 150 140 180 图的最短路径问题 分析高速公路交通网的最短路径 A B C D E F 0 1 2 3 4 5 final distance 1 1 0 1 0 0 0 90 150 140 180 图的最短路径问题 分析高速公路交通网的最短路径 A B C D E F 0 1 2 3 4 5 final distance 1 1 0 1 0 0 0 90 150 140 250 180 图的最短路径问题 分析高速公路交通网的最短路径 A B C D E F 0 1 2 3 4 5 final distance 1 1 1 1 0 0 0 90 150 140 250 180 图的最短路径问题 分析高速公路交通网的最短路径 A B C D E F 0 1 2 3 4 5 final distance 1 1 1 1 0 0 0 90 150 140 250 180 图的最短路径问题 分析高速公路交通网的最短路径 A B C D E F 0 1 2 3 4 5 final distance 1 1 1 1 0 1 0 90 150 140 250 180 图的最短路径问题 分析高速公路交通网的最短路径 A B C D E F 0 1 2 3 4 5 final distance 1 1 1 1 0 1 0 90 150 140 210 180 图的最短路径问题 分析高速公路交通网的最短路径 A B C D E F 0 1 2 3