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

数据结构 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)算法 构造最小生成树的方法