数据结构第章 图ppt课件.ppt

7 1图的类型定义 7 2图的存储结构 7 3图的遍历 7 4最小生成树 7 5有向无环图及其应用 7 6最短路径 7 3图的遍历 图的遍历 从图中某个顶点出发游历图 访遍图中其余顶点 并且使图中的每个顶点仅被访问一次的过程 在图中 访问部分顶点后 可能又沿着其他边回到已被访问过的顶点 为保证每一个顶点只被访问一次 必须对顶点进行标记 一般用一个辅助数组visit 0 n 1 作为对顶点的标记 当顶点vi未被访问 visit i 值为0 当vi已被访问 则visit i 值为1 通常 有两种遍历图的路径 深度优先搜索和广度优先搜索 对无向图和有向图都适用 图的两种遍历方法 1 深度优先搜索图的深度优先遍历类似于树的先根遍历 采用的搜索方法的特点是尽可能先对纵深方向进行搜索 这种搜索方法称为深度优先搜索 Depth FirstSearch 相应地 用此方法遍历图就称之为图的深度优先遍历 2 广度优先搜索广度优先遍历类似于树的按层次遍历 采用的搜索方法的特点是尽可能先对横向进行搜索 故称其为广度优先搜索 Breadth FirstSearch 相应的遍历就称为广度优先遍历 1 深度优先搜索DFS 基本思想 选择图中某个 强 连通分量中某个顶点v出发 访问顶点v 并将其访问标记置为访问过 即visited v 1 依次从v的未被访问的邻接点出发 继续对图进行深度优先遍历 直到 强 连通分量中和v有路径相通的顶点都被访问过 如果图中还有顶点未被访问 则另选图中其余 强 连通分量中一个未被访问的顶点作起点 重复上述过程 直至图中所有顶点都被访问过为止 强 连通分量的遍历 W1 W2和W3均为V的邻接点 SG1为从W1出发可以访问到的顶点集 SG2为从W2出发可以访问到的顶点集 SG3为从W3出发可以访问到的顶点集 访问顺序 SG1 SG2 SG3 交集部分只访问一次 T T T T T T T T T a c h d k f e b g a c h k f e d b g 访问标志 访问次序 例如 h k voidDFSTraverse GraphG 深度优先遍历for v 1 v G vexnum v visited v FALSE 访问标志数组初始化for v 1 v G vexnum v if visited v DFS G v Visit voidDFS GraphG intv Status Visit intv 从顶点v出发 深度优先搜索遍历连通分量visited v TRUE Visit v 尚未访问的邻接顶点递归调用for w FirstAdjVex G v w 0 w NextAdjVex G v w if visited w DFS G w Visit DFS 深度优先遍历的递归算法 例1 深度优先遍历图G 并写出深度优先遍历序列 序列1 V1 V2 V4 V8 V5 V3 V6 V7序列2 V1 V2 V5 V8 V4 V3 V7 V6 注意 由于没有规定访问邻接点的顺序 深度优先序列不是唯一的 例2 深度优先遍历图G 并写出深度优先遍历序列 深度优先遍历序列 V1 V2 V4 V8 V5 V6 V3 V7 V1 V2 V5 V8 V4 V6 V3 V7 V1 V3 V7 V8 V6 V5 V2 V4 深度优先遍历序列对图进行深度优先遍历时 按访问顶点的先后次序得到的顶点序列称为该图的深度优先遍历序列 或DFS序列 一个图的DFS序列不一定惟一 源点和存储结构的内容均已确定的图的DFS序列惟一 邻接矩阵表示的图确定源点后 DFS序列惟一 只有给出了邻接表的内容及初始出发点 才能惟一确定其DFS序列 例3 已知图的邻接表如下 求从顶点0出发的深度优先遍历序列 深度优先遍历序列 0 1 2 3 4 深度优先遍历序列 0 1 2 3 40 1 2 4 30 1 4 2 30 3 2 1 40 3 2 4 1 例4 已知图的邻接矩阵 求从顶点0出发的深度优先遍历序列 深度优先遍历序列 0 1 3 4 2 5 6 例5 已知图的邻接表如下 求从顶点0出发的深度优先遍历序列 深度优先遍历序列 0 1 2 3 2 广度优先搜索BFS 选择 强 连通分量中的某个顶点vi出发 访问顶点vi 并将其访问标志置为已被访问 即visited vi 1 访问vi的所有未被访问的邻接点w1 w2 wk 依次从这些邻接点出发 访问它们的所有未被访问的邻接点 直到 强 连通分量的所有顶点都被访问 重复上述步骤 直到图中所有的顶点都被访问 对连通图 从起点V到其余各顶点必定存在路径 其中 V w1 V w2 V w5的路径长度为1 V w3 V w6 V w8的路径长度为2 V w4 V w7的路径长度为3 各顶点和起点之间存在 远近 关系 就是按照 由近到远 的顺序进行遍历 voidBFSTraverse GraphG Status Visit intv 广度优先非递归遍历 使用辅助队列Q和访问标志数组visited for v 1 v G vexnum v visited v FALSE InitQueue Q 置空的辅助队列Qfor v 1 v G vexnum v if visited v v尚未访问visited v TRUE Visit v 访问起点EnQueue Q v v入队列while QueueEmpty Q DeQueue Q u 队头元素出队并置为u 下页 for w FirstAdjVex G u w 0 w NextAdjVex G u w 访问邻接点if visited w u的尚未访问的邻接顶点w入队列Qvisited w TRUE Visit w EnQueue Q w if while BFSTraverse 例1 广度优先遍历图G 并写出广度优先遍历序列 广度优先遍历序列 V1 V2 V3 V4 V5 V6 V7 V8 例2 广度优先遍历图G 并写出广度优先遍历序列 广度优先遍历序列 V1 V2 V3 V4 V5 V6 V7 V8 图的广度优先遍历序列广度优先遍历图所得的顶点序列 定义为图的广度优先遍历序列 简称BFS序列 一个图的BFS序列不一定是惟一的 给定了源点及图的存储结构时 BFS序列就是惟一的 例3 已知图的邻接表如下 求从顶点0出发的广度优先遍历序列 广度优先遍历序列 0 1 3 2 4 广度优先遍历序列 0 1 3 2 40 1 3 4 20 3 1 2 4 例4 已知图的邻接矩阵 求从顶点0出发的广度优先遍历序列 0 1 2 3 4 6 5 广度优先遍历序列 例5 已知图的邻接表如下 求从顶点0出发的广度优先遍历序列 例6 画出该网的邻接矩阵 根据画出的邻接矩阵存储结构 从顶点1出发 分别进行深度优先遍历和广度优先遍历 123456 123456 深度优先 1 2 5 4 6 3广度优先 1 2 3 5 6 4 极大连通子图 该子图是无向图D的连通子图 将D的任何不在该子图中的顶点加入 子图不再是连通的 极小连通子图 该子图是G的连通子图 在该子图中删除任何一条边 子图不再连通 若T是G的生成树当且仅当T满足如下条件 1 T是G的连通子图2 T包含G的所有顶点3 T中无回路 7 4最小生成树 7 4最小生成树 假设要在n个城市之间建立通讯联络网 如何在最节省经费的前提下建立这个通讯网 问题 分析 首先 该网必须是连通网 其次 网中的线路必须最少 最后 考虑所有线路的长度之和最小 最小生成树满足上述要求 上述问题等价于 构造网的一棵最小生成树 即 在e条带权的边中选取n 1条边 不构成回路 使 权值之和 最小 求最小生成树的两个算法 普里姆算法 适用于求边稠密的网的最小生成树 克鲁斯卡尔算法 适用于求边稀疏的网的最小生成树 假设有连通网N V E 求N的最小生成树T TV TE 算法的基本思想 一 普里姆 Prim 算法 令TV v TE 从一个顶点v开始TE min v u TV u 其中 v TV u V TV 重复步骤2 直到TV V 取图中任意一个顶点v作为生成树的根 之后往生成树上添加新的顶点w 在添加的顶点w和已经在生成树上的顶点v之间必定存在一条边 并且该边的权值在所有连通顶点v和w之间的边中取值最小 之后继续往生成树上添加顶点 直至生成树上含有n个顶点为止 普里姆算法的基本思想 步骤 1 初始时 U v0 边集合TE 2 在所有v0 U w V U的边中选择一条权值最小的边 设这条边为 v0 w 3 将边 v0 w 加入TE 同时将w加入U中 而把w从V U中删掉 4 重复 2 3 直到U V为止 1 普里姆算法举例 例1使用普里姆算法为图G构造最小生成树 设最小生成树为 T U TE 图G V E 构造步骤如下 步骤1 初始状态 U v1 TE V U v2 v3 v4 v5 v6 1 普里姆算法举例 步骤2 U v1 v3 V U v2 v4 v5 v6 1 普里姆算法举例 步骤3 U v1 v3 v6 V U v2 v4 v5 1 普里姆算法举例 步骤4 U v1 v3 v6 v4 V U v2 v5 1 普里姆算法举例 步骤5 U v1 v3 v6 v4 v2 V U v5 1 普里姆算法举例 步骤6 U v1 v2 v3 v4 v5 v6 U V 结束 1 普里姆算法举例 在算法实现中设置一个辅助数组closedege 对当前V U集合中的每个顶点 记录和顶点集U中顶点相连接的代价最小的边 struct VertexTypeadjvex U集中的相邻顶点序号VRTypelowcost 边的权值 closedge MAX VERTEX NUM 例如 所得生成树权值和 14 8 3 5 16 21 67 a e d c b a a a 19 14 18 14 例如 e 12 e e 8 16 8 d 3 d d 7 21 3 c 5 5 所得生成树权值和 14 8 3 5 16 21 67 例2 a e d c b g f 14 8 5 3 16 21 所得生成树权值和 14 8 3 5 16 21 67 voidMiniSpanTree P MGraphG VertexTypeu 用Prim算法从顶点u出发构造网G的最小生成树 网G用邻接矩阵表示k LocateVex G u max 100 for j 0 j G vexnum j 辅助数组初始化if j k closedge j u G arcs k j adj closedge k lowcost 0 初始 TV u for i 1 i G vexnum i for n 1 n G vexnum i if closedge n lowcast max 下页 printf c c closedge k adjvex G vexs k 输出最小生成树的一条边closedge k lowcost 0 k顶点并入TV集for j 0 j G vexnum j 修改顶点的lowcastif G arcs k j adj closedge j lowcost closedge j G vexs k G arcs k j adj for MiniSpanTree P 练习题1使用普里姆算法为图G构造一棵最小生成树 练习题2使用普里姆算法为图G构造一棵最小生成树 算法的基本思想 二 克鲁斯卡尔 Kruskal 算法 假设有连通网N V E 求N的最小生成树T TV TE 令TV V TE 包含所有顶点TE min v u v u 是顶点v u之间的唯一路径 重复步骤2 直到TE中边的条数为n 1 算法的基本思想 考虑问题的出发点 为使生成树上边的权值之和达到最小 则应使生成树中每一条边的权值尽可能地小 具体做法 先构造一个只含n个顶点的子图SG 然后从权值最小的边开始 若它的添加不使SG中产生回路 则在SG上加上这条边 如此重复 直至加上n 1条边为止 步骤 1 最小生成树的初始状态为只有n个顶点而无边的非连通图T V 2 在E中选取代价最小的边 若该边依附的顶点落在T中不同的连通分量上 则将此边加入到T中 否则 舍去此边 选取下一条代价最小的边 3 依此类推 直至T中所有顶点都在同一连通分量上为止 例2用克鲁斯卡尔算法构造图G最的小生成树 2 克鲁斯卡尔算法 设最小生成树为 T U TE 构造步骤如下 步骤1 初始状态 T中只有n个顶点 无边 2 克鲁斯卡尔算法 图G V E 步骤2 T中有n个顶点 1条边 2 克鲁斯卡尔