《数据结构》课程教学资源：第七章 图（7.3-7.6）

《数据结构》 第七章下)

《 数据结构》 第七章(下)

数据结构 第七章图 71图的定义和术语 72图的存储结构 721数组表示法 7.2.2邻接表 73图的遍历 73.1深度优先搜索 7.3.2广度优先搜索 74图的连通性问题 74.3最小生成树 75有向无环图及其应用 7.5.1拓扑排序 7.6最短路径 761从某个源点到其余各顶点的最短路径 76.2每一对顶点之间的最短路径

数据结构 tjm 第七章 图 7.1 图的定义和术语 7.2 图的存储结构 7.2.1 数组表示法 7.2.2 邻接表 7.3 图的遍历 7.3.1 深度优先搜索 7.3.2 广度优先搜索 7.4 图的连通性问题 7.4.3 最小生成树 7.5 有向无环图及其应用 7.5.1 拓扑排序 7.6 最短路径 7.6.1 从某个源点到其余各顶点的最短路径 7.6.2 每一对顶点之间的最短路径

数据结构 73的遍历 73.1深度优先搜索 方法:从图的某一顶点vo出发,访问此项点; 然后依次从v0的未被访问的邻接点出发,深度 优先遍历图,直至图中所有和V0相通的顶点都 被访问到; 若此时图中尚有顶点未被访问,则另选图中一个 未被访问的顶点作起点重复上述过程,直至图 中所有顶点都被访问为止

数据结构 tjm 7.3 图的遍历 7.3.1 深度优先搜索 方法：从图的某一顶点V0出发，访问此顶点； 然后依次从V0的未被访问的邻接点出发，深度 优先遍历图，直至图中所有和V0相通的顶点都 被访问到； 若此时图中尚有顶点未被访问，则另选图中一个 未被访问的顶点作起点,重复上述过程，直至图 中所有顶点都被访问为止

数据结构 深度优先遍历算法(递归算法)参见P169。 例 深度遍历:Ⅵ1→V2→V4→V8→V5→V3→V6→V7 3 v8 V5 深度优先生成树

数据结构 tjm V1 V2 V4 V5 V3 V6 V7 V8 例： 深度遍历：V1 V2 V4  V8 V5 V3 V6 V7 深度优先遍历算法（递归算法）参见P169。 V1 V2 V4 V5 V3 V7 V6 V8 深度优先生成树 V1 V2 V4 V5 V3 V6 V7 V8

数据结构 例: s97 v8 vexdata firstarc adtvexnexta 2345678 2345678 35788765 24622334 深度遍历:V1→V3→V7→V6→V2→V5→V8→V4

数据结构 tjm V1 V2 V4 V5 V3 V6 V7 V8 例： 1 2 3 4 1 3 4 2 vexdata firstarc 2 7 8 3 ^ ^ ^ adjvexnextarc 5 5 6 5 4 1 ^ 1 2 8 2 ^ 6 7 8 6 7 8 7 3 6 3 5 4 ^ ^ ^ 深度遍历：V1V3 V7 V6 V2 V5 V8 V4

数据结构 732广度优先案 方法:从图的某一顶点v0出发,访问此顶点后 依次访问v0的各个未曾访问过的邻接点;然后 分别从这些邻接点出发,广度优先遍历图,直 至图中所有已被访问的顶点的邻接点都被访问 到 若此时图中尚有顶点未被访问,则另选图中 个未被访问的顶点作起点,重复上述过程,直 至图中所有顶点都被访问为止

数据结构 tjm 7.3.2 广度优先搜索 方法：从图的某一顶点V0出发，访问此顶点后， 依次访问V0的各个未曾访问过的邻接点；然后 分别从这些邻接点出发，广度优先遍历图，直 至图中所有已被访问的顶点的邻接点都被访问 到； 若此时图中尚有顶点未被访问，则另选图中一 个未被访问的顶点作起点，重复上述过程，直 至图中所有顶点都被访问为止

数据结构 广度优先遍历算法参见P170 例:X N45N0(7 广度遍历:V1→V2→V3→V4→V5→V6→VⅥ→V8 4567 8 广度优先生成树

数据结构 tjm V1 V2 V4 V5 V3 V6 V7 V8 例: 广度遍历：V1 V2 V3  V4 V5 V6 V7 V8 广度优先遍历算法参见P170。 V1 V2 V4 V5 V3 V6 V7 V8 广度优先生成树 V1 V2 V4 V5 V3 V6 V7 V8

数据结构 例 exdata firstarc adivexnextarc 3 2 12345 12345 45554 1 2 广度遍历序列:14325 2

数据结构 tjm 例: 1 2 3 4 5 1 2 3 4 1 3 4 2 vexdata firstarc 5 5 4 3 ^ ^ ^ adjvexnextarc 5 5 5 1 ^ 1 1 4 3 ^ 2 2 广度遍历序列：1 4 3 2 5

数据结构 74图的连通性间题 7.43最小生成树 问题提出:要在η个城市间建立通信联络网,用 顶点表示城市;权表示城市间建立通信线路所需 花费代价。希望找到一棵生成树,它的每条边上 的权值之和(即建立该通信网所需花费的总代价) 最小最小代价)生成肉 13′9 6)24 10 3

数据结构 tjm 7.4 图的连通性问题 问题提出：要在n个城市间建立通信联络网，用 顶点表示城市；权表示城市间建立通信线路所需 花费代价。希望找到一棵生成树，它的每条边上 的权值之和（即建立该通信网所需花费的总代价） 最小——最小(代价)生成树。 1 5 6 3 4 2 7 13 17 9 18 12 7 5 24 10 7.4.3 最小生成树

数据结构 构造最小生成树的方法 方法一:普里烟(Prim算法 算法思想:设N=(V{E}是连通网,TE是N上 最小生成树中边的集合 初始令U={0}u0∈V),TE=Φ。 在所有u∈U,v∈V-U的边(uv)∈E中,找一条代 价最小的边(uovO) 将(uo,v0)并入集合TE,同时v0并入U 重复上述操作直至U=V为止,则T=(VTE}) 为N的最小生成树

数据结构 tjm 算法思想：设N=(V,{E})是连通网，TE是N上 最小生成树中边的集合。 初始令U={u0},(u0V), TE=。 在所有uU,vV-U的边(u,v)E中，找一条代 价最小的边(u0,v0)。 将(u0,v0)并入集合TE，同时v0并入U。 重复上述操作直至U=V为止，则T=(V,{TE}) 为N的最小生成树。 方法一：普里姆(Prim)算法 构造最小生成树的方法