第16讲 图遍历与最小生成树

1、数据结构 1执行上课礼执行上课礼第16讲 图的遍历与 最小生成树主讲人：陈红丽第七章 图 2执行上课礼，不迟到、不早退、不旷课执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉课上不吃早点、不玩手机、不睡觉图的遍历图的遍历图的遍历是从图中是从图中某某一顶点出发，对图中所一顶点出发，对图中所有有顶点访问一次且仅顶点访问一次且仅访问访问一次。一次。 图的遍历操作要解决的关键问题图的遍历操作要解决的关键问题因图中可能存在回路，某些顶点可能会被重复访因图中可能存在回路，某些顶点可能会被重复访问，如何避免遍历因回路而陷入死循环。问，如何避免遍历因回路而陷入死循环。p解决方案：附设访问标志数

2、组解决方案：附设访问标志数组visitedn图中一个顶点可和其它多个顶点相连，当这样的图中一个顶点可和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？顶点访问过后，如何选取下一个要访问的顶点？p解决方案：深度优先遍历和广度优先遍历。解决方案：深度优先遍历和广度优先遍历。第七章 图 3执行上课礼，不迟到、不早退、不旷课执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉课上不吃早点、不玩手机、不睡觉q深度优先遍历过程是递归的，在遍历过程中，若某个顶点的所有邻接顶点均被访问过，则需要回溯。V1V2V4V5V8V3V6V7V1V5V2V4V2V8V1V7V3V3V6V

3、3V2V4V1V6V5V8V7与二叉树的先序遍历相类似与二叉树的先序遍历相类似深度优先遍历深度优先遍历第七章 图 4执行上课礼，不迟到、不早退、不旷课执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉课上不吃早点、不玩手机、不睡觉深度优先遍历深度优先遍历从图中某顶点v出发 1）访问顶点 v，置访问标记 visitedv = 1； 2）依次从 v 的未被访问的邻接点未被访问的邻接点出发，继续对图进行深度优先遍历深度优先遍历，直到和v有路径相通的顶点都被访问过； 3）如果图中还有顶点未被访问，则另选图中一个未被访问的顶点作起点未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访

4、问过为止。第七章 图 5执行上课礼，不迟到、不早退、不旷课执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉课上不吃早点、不玩手机、不睡觉l根据图G的邻接矩阵，从顶点V4出发，写出深度优先遍历序列。0 1 1 0 0 0 0 00 1 1 0 0 0 0 00 0 1 1 0 0 00 0 1 1 0 0 01 0 0 0 0 1 1 1 0 0 0 0 1 1 0 00 1 0 0 0 0 0 0 1 0 0 0 0 0 1 10 1 0 0 0 0 0 0 1 0 0 0 0 0 1 10 0 1 0 0 0 1 0 0 1 0 0 0 1 0 00 0 1 0 0 1 0

5、0 0 1 0 0 1 0 0 01 10 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0V1 V2 V3 V4 V5 V6 V7 V8V1V2V3V4V5V6V7V8V6,深度优先遍历序列： V1,V2,V4,V8,V5,V3,V6,V7或V1,V2,V5,V8,V4,V3,V7,V6或V2,V5,V8, V4, V1,V3,V7,V6 .V1V2V4V5V3V7V6V8图G的逻辑结构图图G的邻接矩阵？的邻接矩阵？V4,V2,V1, V3,V7,V5,V8第七章 图 6执行上课礼，不迟到、不早退、不旷课执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉课上不吃早点、

6、不玩手机、不睡觉l已知某图G的邻接表如下所示，分别写出从顶点0和顶点3出发的DFS序列。以顶点0为起点的DFS序列：0，1，4，3，2以顶点3为起点的DFS序列：3，1，4，2，0 第七章 图 7执行上课礼，不迟到、不早退、不旷课执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉课上不吃早点、不玩手机、不睡觉从图中某个顶点vi出发： 1)访问顶点vi，并置访问标志 2)访问vi的所有未被访问的邻接点w1,w2,wk； 3)依次从这些邻接点（在步骤2)中访问的顶点）出发，访问它们的所有未被访问的邻接点；依此类推，直到图中所有访问过的顶点的邻接点都被访问 4)如若此时图中尚有顶点未被

7、访问，则需另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。广度优先遍历与二叉树的层次遍历相似与二叉树的层次遍历相似V3V2V4V1V6V5V8V7第七章 图 8执行上课礼，不迟到、不早退、不旷课执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉课上不吃早点、不玩手机、不睡觉0 1 1 0 0 0 0 00 1 1 0 0 0 0 00 0 1 1 0 0 00 0 1 1 0 0 01 0 0 0 0 1 1 1 0 0 0 0 1 1 0 00 1 0 0 0 0 0 0 1 0 0 0 0 0 1 10 1 0 0 0 0 0 0 1

8、0 0 0 0 0 1 10 0 1 0 0 0 1 0 0 1 0 0 0 1 0 00 0 1 0 0 1 0 0 0 1 0 0 1 0 0 01 10 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0V1 V2 V3 V4 V5 V6 V7 V8V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8l根据图G的邻接矩阵，从顶点V4出发，写出广度优先遍历序列。V4,V2,V8,V1, V5,V3,V6,V7第七章 图 9执行上课礼，不迟到、不早退、不旷课执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉课上不吃早点、不玩手机、不睡觉l已知邻接表，求以顶点

9、0和顶点3为起点的广度优先遍历序列。以顶点0为起点的BFS序列：0，1，3，4，2以顶点3为起点的BFS序列：3，1，0，4，2 第七章 图 10执行上课礼，不迟到、不早退、不旷课执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉课上不吃早点、不玩手机、不睡觉遍历的应用q利用图的遍历运算求解图的连通性问题F无向图是否连通、有几个连通分量，求解无向图的所有连通分量深度优先生成树、生成森林广度优先生成树、生成森林F有向图是否是强连通、求解其强连通分量q求无向网的最小代价生成树无向网的最小代价生成树第七章 图 11执行上课礼，不迟到、不早退、不旷课执行上课礼，不迟到、不早退、不旷课课上

10、不吃早点、不玩手机、不睡觉课上不吃早点、不玩手机、不睡觉回顾：连通无向图及其生成树V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5无向图G第七章 图 12执行上课礼，不迟到、不早退、不旷课执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉课上不吃早点、不玩手机、不睡觉最小生成树l生成树的代价：生成树的代价：设设G=(V，E)是一个无向连通网，是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。生成树上各边的权值之和称为该生成树的代价。l最小生成树：最小生成树：在网在网G的所有生成树中，代价最小的的所有生成树中，代价最小的生成树。生成树。网Gv1v3

11、v4v2243v1v3v4v22334第七章 图 13执行上课礼，不迟到、不早退、不旷课执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉课上不吃早点、不玩手机、不睡觉求最小生成树的两个算法：求最小生成树的两个算法：l普里姆算法普里姆算法从从1个起点个起点0条边条边出发，不断出发，不断扩充顶点扩充顶点，直到包括直到包括所有顶点所有顶点为止，适用于求为止，适用于求边稠边稠密密的网的最小生成树。的网的最小生成树。l克鲁斯卡尔算法克鲁斯卡尔算法从从n个顶点个顶点0条边条边出发，不断出发，不断扩充边扩充边，直，直到包括到包括n-1条边条边为止，适用于求为止，适用于求边稀疏边稀疏的的网的最

12、小生成树。网的最小生成树。第七章 图 14执行上课礼，不迟到、不早退、不旷课执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉课上不吃早点、不玩手机、不睡觉V4V1V3V2V6V56512665534V1V1 V2 ,V3 ,V4 , V5 ,V6 步骤步骤(0)VTV-VTET V1最最小小生生成成树树(1)V1 , V3 V2 , V4 , V5 ,V6 (v1,v3) V31(2)V3V6V1 , V3,V6 V2 , V4 , V5 (v1,v3) ,(v3,v6) V64(3)V4V1 , V3 , V6 , V4 V2, V5 (v1,v3) ,(v3,v6) ,(v

13、4,v6) V42(4)V2V1 , V3 , V6 , V4 , V2 V5 (v1,v3) ,(v3,v6) ,(v4,v6) ,(v3,v2) V25(5)V5V1 , V3 , V6 , V4 , V2 , V5 (v1,v3) ,(v3,v6) ,(v4,v6) ,(v3,v2) ,(v2,v5) V53Prim算法算法第七章 图 15执行上课礼，不迟到、不早退、不旷课执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉课上不吃早点、不玩手机、不睡觉普里姆(Prim)算法q设N=(V，E)是连通网，从起点v0出发，构造最小生成树T=(VT, ET)。VT是N上最小生成树中

14、顶点的集合，ET是N上最小生成树中边的集合。q算法步骤初始化初始化VT=v v0 0，ET= ；找权值最小的找权值最小的(Vp,Vq), VpVT, VqV-VT;将将(Vp,Vq)并入并入ET，同时，同时Vq并入并入VT；重复重复步骤步骤n-1次。次。第七章 图 16执行上课礼，不迟到、不早退、不旷课执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉课上不吃早点、不玩手机、不睡觉V4V1V3V2V6V56512665534V4V1V3V2V6V51234初始化VT=v1,v2,v3, v4,v5,v6，ET=ET=(v1,v3)ET=(v1,v3), (v4,v6)ET=(v1

15、,v3), (v4,v6),(v2,v5)ET=(v1,v3), (v4,v6),(v2,v5),(v3,v6)ET=(v1,v3), (v4,v6),(v2,v5),(v3,v6) ,(v2,v3)5依附在同一依附在同一个连通分量个连通分量Kruskal算法第七章 图 17执行上课礼，不迟到、不早退、不旷课执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉课上不吃早点、不玩手机、不睡觉克鲁斯卡尔(Kruskal)算法l算法思路算法思路 尽可能选择n-1条权值最小的边； 但不能构成回路不能构成回路。 l算法步骤算法步骤 初始化VT=V，ET=，即n个顶点是n个连通分量； 选择权值

16、最小的边选择权值最小的边(Vp,Vq)； 若若Vp、Vq不属于同一连通分量，将不属于同一连通分量，将(Vp,Vq)并入并入ET；否则，舍弃。否则，舍弃。 重复重复，直至选取了，直至选取了n-1条边。条边。第七章 图 18执行上课礼，不迟到、不早退、不旷课执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉课上不吃早点、不玩手机、不睡觉习题：(1)给出用克鲁斯卡尔算法构造最小生成树的详细过程(2) 给出用普里姆算法从顶点a出发构造最小生成树的详细过程adefgbc3498714352892adefgbc314322解题技巧：先将图中的权值排序：1、2、2、3、3、4、4、5、7、8、

17、8、9、9ae2d3 f4g1 b3c2第七章 图 19执行上课礼，不迟到、不早退、不旷课执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉课上不吃早点、不玩手机、不睡觉AOV网与拓扑排序网与拓扑排序 一般都把工程分为若干个叫做一般都把工程分为若干个叫做“活动活动”的子工程的子工程。完成了这些活动，这个工程就可以完成了。完成了这些活动，这个工程就可以完成了。q 对工程，人们至少关心如下两类问题：对工程，人们至少关心如下两类问题：q 工程能否顺利进行，即工程流程是否工程能否顺利进行，即工程流程是否“合理合理”为求解工程流程是否为求解工程流程是否“合理合理”，通常用，通常用AOV网表

18、示工网表示工程流程程流程q 完成整项工程必须的最短时间，哪些子工程是影响工完成整项工程必须的最短时间，哪些子工程是影响工程进度的关键子工程程进度的关键子工程q AOVAOV网网(Activity On Vertex net )(Activity On Vertex net )F用顶点表示用顶点表示活动活动，边表示边表示活动的先后关系活动的先后关系的有向图的有向图称为称为AOVAOV网。网。 某工程可分为某工程可分为7 7个子工个子工程，若用程，若用顶点表示子工程（顶点表示子工程（也称活动），也称活动）， 用弧表示子用弧表示子工程间的顺序关系，工程间的顺序关系，工程的工程的施工流程可用如右的施工

19、流程可用如右的AOVAOV网网表示。表示。 V5V5 V3V3 V2V2 V0V0 V1V1 V4V4 V6V6AOV网可以出现环路吗？网可以出现环路吗？ AOV网中不能出现回路。网中不能出现回路。判别有向网中是否存在有向判别有向网中是否存在有向环的一个办法就是对此环的一个办法就是对此AOV网进行网进行拓扑排序拓扑排序。第七章 图 20执行上课礼，不迟到、不早退、不旷课执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉课上不吃早点、不玩手机、不睡觉拓扑有序序列：拓扑有序序列：即将即将各个顶点各个顶点 (代表各个活动代表各个活动) 排列成一个线性有序的排列成一个线性有序的序列，使得序列，使得AOV网中所网中所有应存在的前驱和后继有应存在的前驱和后继关系都能得到满足。关系都能得到满足。拓扑排序：拓扑排序：构造一个包构造一个包含图中所有顶点的含图中所有顶点的“拓拓扑有序序列扑有序序列”。拓扑序列不唯一。拓扑序列不唯一。拓扑排序 V5V5 V3V3 V2V2 V0V0 V1V1 V4V4 V6V6q 可行的施工计划：可行的施工计划： V0, V1,