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

数据结构1执行上课礼第16讲图的遍历与最小生成树主讲人：陈红丽第七章图2/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉图的遍历图的遍历是从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。图的遍历操作要解决的关键问题因图中可能存在回路，某些顶点可能会被重复访问，如何避免遍历因回路而陷入死循环。解决方案：附设访问标志数组visited[n]图中一个顶点可和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？解决方案：深度优先遍历和广度优先遍历。第七章图3/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉深度优先遍历过程是递归的，在遍历过程中，若某个顶点的所有邻接顶点均被访问过，则需要回溯。V1V2V4V5V8V3V6V7V1V5V2V4V2V8V1V7V3V3V6V3V2V4V1V6V5V8V7与二叉树的先序遍历相类似深度优先遍历第七章图4/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉深度优先遍历从图中某顶点v出发1）访问顶点v，置访问标记visited[v]=1；2）依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历，直到和v有路径相通的顶点都被访问过；3）如果图中还有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问过为止。第七章图5/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉根据图G的邻接矩阵，从顶点V4出发，写出深度优先遍历序列。0110000010011000100001100100000101000001001000100010010000011000V1V2V3V4V5V6V7V8V1V2V3V4V5V6V7V8V6,深度优先遍历序列：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/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉已知某图G的邻接表如下所示，分别写出从顶点0和顶点3出发的DFS序列。以顶点0为起点的DFS序列：0，1，4，3，2以顶点3为起点的DFS序列：3，1，4，2，0第七章图7/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉从图中某个顶点vi出发：1)访问顶点vi，并置访问标志2)访问vi的所有未被访问的邻接点w1,w2,…,wk；3)依次从这些邻接点（在步骤2)中访问的顶点）出发，访问它们的所有未被访问的邻接点；依此类推，直到图中所有访问过的顶点的邻接点都被访问4)如若此时图中尚有顶点未被访问，则需另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。广度优先遍历与二叉树的层次遍历相似V3V2V4V1V6V5V8V7第七章图8/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉0110000010011000100001100100000101000001001000100010010000011000V1V2V3V4V5V6V7V8V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8根据图G的邻接矩阵，从顶点V4出发，写出广度优先遍历序列。V4,V2,V8,V1,V5,V3,V6,V7第七章图9/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉已知邻接表，求以顶点0和顶点3为起点的广度优先遍历序列。以顶点0为起点的BFS序列：0，1，3，4，2以顶点3为起点的BFS序列：3，1，0，4，2第七章图10/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉遍历的应用利用图的遍历运算求解图的连通性问题无向图是否连通、有几个连通分量，求解无向图的所有连通分量深度优先生成树、生成森林广度优先生成树、生成森林有向图是否是强连通、求解其强连通分量求无向网的最小代价生成树第七章图11/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉回顾：连通无向图及其生成树V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5无向图G第七章图12/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉最小生成树生成树的代价：设G=(V，E)是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。最小生成树：在网G的所有生成树中，代价最小的生成树。网Gv1v3v4v2243v1v3v4v22334第七章图13/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉求最小生成树的两个算法：普里姆算法从1个起点0条边出发，不断扩充顶点，直到包括所有顶点为止，适用于求边稠密的网的最小生成树。克鲁斯卡尔算法从n个顶点0条边出发，不断扩充边，直到包括n-1条边为止，适用于求边稀疏的网的最小生成树。第七章图14/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉V4V1V3V2V6V56512665534V1｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)VTV-VTET｛｝V1最小生成树(1)｛V1,V3｝｛V2,V4,V5,V6｝｛(v1,v3)｝V31(2)V3V6｛V1,V3,V6｝｛V2,V4,V5｝｛(v1,v3),(v3,v6)｝V64(3)V4｛V1,V3,V6,V4｝｛V2,V5｝｛(v1,v3),(v3,v6),(v4,v6)｝V42(4)V2｛V1,V3,V6,V4,V2｝｛V5｝｛(v1,v3),(v3,v6),(v4,v6),(v3,v2)｝V25(5)V5｛V1,V3,V6,V4,V2,V5｝｛｝｛(v1,v3),(v3,v6),(v4,v6),(v3,v2),(v2,v5)｝V53Prim算法第七章图15/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉普里姆(Prim)算法设N=(V，E)是连通网，从起点v0出发，构造最小生成树T=(VT,ET)。VT是N上最小生成树中顶点的集合，ET是N上最小生成树中边的集合。算法步骤①初始化VT={v0}，ET={}；②找权值最小的(Vp,Vq),Vp∈VT,Vq∈V-VT;③将(Vp,Vq)并入ET，同时Vq并入VT；④重复②③步骤n-1次。第七章图16/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉V4V1V3V2V6V56512665534V4V1V3V2V6V51234初始化VT={v1,v2,v3,v4,v5,v6}，ET={}ET={(v1,v3)}ET={(v1,v3),(v4,v6)}ET={(v1,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/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉克鲁斯卡尔(Kruskal)算法算法思路①尽可能选择n-1条权值最小的边；②但不能构成回路。算法步骤①初始化VT=V，ET={}，即n个顶点是n个连通分量；②选择权值最小的边(Vp,Vq)；③若Vp、Vq不属于同一连通分量，将(Vp,Vq)并入ET；否则，舍弃。④重复②③，直至选取了n-1条边。第七章图18/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉习题：(1)给出用克鲁斯卡尔算法构造最小生成树的详细过程(2)给出用普里姆算法从顶点a出发构造最小生成树的详细过程adefgbc3498714352892adefgbc314322①②③④⑤⑥解题技巧：先将图中的权值排序：1、2、2、3、3、4、4、5、7、8、8、9、9ae2①d3③f4④g1②b3⑤c2⑥第七章图19/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉AOV网与拓扑排序一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。对工程，人们至少关心如下两类问题：1)工程能否顺利进行，即工程流程是否“合理”为求解工程流程是否“合理”，通常用AOV网表示工程流程2)完成整项工程必须的最短时间，哪些子工程是影响工程进度的关键子工程AOV网(ActivityOnVertexnet)用顶点表示活动，边表示活动的先后关系的有向图称为AOV网。某工程可分为7个子工程，若用顶点表示子工程（也称活动），用弧表示子工程间的顺序关系，工程的施工流程可用如右的AOV网表示。V5V3V2V0V1V4V6AOV网可以出现环路吗？AOV网中不能出现回路。判别有向网中是否存在有向环的一个办法就是对此AOV网进行拓扑排序。第七章图20/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉拓扑有序序列：即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网中所有应存在的前驱和后继关系都能得到满足。拓扑排序：构造一个包含图中所有顶点的“拓扑有序序列”。拓扑序列不唯一。拓扑排序V5V3V2V0V1V4V6可行的施工计划：V0,V1,V2,V4,V3,V6,V5V0,V2,V1,V4,V3,V6,V5……如何安排施工计划？第七章图21/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉拓扑排序方法：1)在有向图中选一个无前趋的顶点v，输出之；2)从有向图中删除v及以v为尾的弧；3)重复1)、2)，直到输出全部顶点或有向图中不存在无前趋的顶点时为止。V5V3V2V0V1V4V6V0V1V2V3V4V5V6V5V3V2V0V1V4V6如何在计算机上实现对有向图的拓扑排序？入度为0的顶点v的邻接顶点入度减1拓扑排序数据结构需要频繁计算入度，选用数组做为入度表；需要频繁搜索弧头，采用邻接表存储图；为了避免每一步选入度为0的顶点时重复扫描入度表，可设置一个栈（或队列）来存储所有入度为0的顶点。第七章图22/22执行上课礼，不迟到、不早退、不旷课课上不吃早点、不玩手机、不睡觉124653写出下图的所有拓扑序列。