北京大学：《数据结构与算法》课程教学资源（实验班讲义）第六章 图

有向图G7的邻接多重表 N2边w,v 邻接多重表不太常用 N[2NN边(w,v 在以处理图的边为主,要求每条 N[2边v,v 边处理一次的实际应用中可能有 N[4L边v,v 用 N[边(.vs N□22xL边v NT4边wv 64图的周游 森林的周游 ◇6.4.1深度优先搜索 ■按深度方向周游 64.2广度优先搜索 先根次序 643拓扑排序 后根次序 ■按广度方向周游 宽度优先周游 层次周游 亡 权新有,轴彩光 64图的周游( graph traversaL) 图周游的考虑 给出一个图G和其中任意一个顶 ■从一个顶点出发,试探性访问其余 点v 顶点,同时必须考虑到下列情况: ■从v出发系统地访问G中所有的 从一顶点出发,可能不能到达所有其 顶点,每个顶点访问一次 它的顶点,如非连通图; ■也有可能会陷入死循环,如存在回路 的图。 值惠单 6

6 北京大学信息学院 ©版权所有，转载或翻印必究 Page 31 有向图G7的邻接多重表 北京大学信息学院 ©版权所有，转载或翻印必究 Page 32 „ 邻接多重表不太常用 „ 在以处理图的边为主，要求每条 边处理一次的实际应用中可能有 用 北京大学信息学院 ©版权所有，转载或翻印必究 Page 33 6.4 图的周游 „ 6.4.1 深度优先搜索 „ 6.4.2 广度优先搜索 „ 6.4.3 拓扑排序 北京大学信息学院 ©版权所有，转载或翻印必究 Page 34 森林的周游 „ 按深度方向周游 „ 先根次序 „ 后根次序 „ 按广度方向周游 „ 宽度优先周游 „ 层次周游 北京大学信息学院 ©版权所有，转载或翻印必究 Page 35 6.4 图的周游（graph traversal） „ 给出一个图G和其中任意一个顶 点V0 „ 从V0出发系统地访问G中所有的 顶点，每个顶点访问一次 北京大学信息学院 ©版权所有，转载或翻印必究 Page 36 图周游的考虑 „ 从一个顶点出发，试探性访问其余 顶点，同时必须考虑到下列情况： „ 从一顶点出发，可能不能到达所有其 它的顶点，如非连通图； „ 也有可能会陷入死循环，如存在回路 的图

士 图的周游算法框架 解决办法 //图的周游算法的实现 Graph& G ■为图的每个顶点保留一个标志位 //对图所有顶点的标志位进行初始化 (mark bit)i ■算法开始时,所有顶点的标志位置 /检查图的所有项点是否被标记过,如果未被标记, 则从该未被标记的顶点开始继续周游 在周游的过程中,当某个顶点被访问 / do traverse函数用湅度优先或者广度优先 for(int i=O;i<G. VerticesNum(; i++) 时,其标志位就被标记为已访问。 if(G. Mark[O]== UNVISITED) o_traverse(G, i); 盟hm 图的生成树 641深度优先搜索 图的所有顶点加上周游过程中经 浮度y签慈想 pth-first searc,向称 过的边所构成的子图称作图的生 莴的卖应V,然后访间该顶点邻热到的未被访 成树 再从v出发递归地按照深度优先的方式周游 图的生成森林 通,百楚牌帮蔑言闻 再从W出发遵归地按照深度优先的方式周游 项着舒何蔑譆的顶点都没有本被访间的 深度优先搜家树( depth- first search tree) 亡 权新有,轴量 从一个顶点出发的深度优先搜索 void dfs( Graph& G, int V)∥/深度优先搜索算法实现 G. Mark[v= VISITED;//访问顶点v,并标记其标志位 /访问V邻接到的未被访问过的顶点,并递归地按照 G. Mark[G. ToVerticese)]== UNVISITED DFS(G, G. ToVertices(e)); Postvisit(G, V //访问 深度优先搜索的顺序是a,b,c,f,d,e,g

7 北京大学信息学院 ©版权所有，转载或翻印必究 Page 37 „ 解决办法 „ 为图的每个顶点保留一个标志位 （mark bit）； „ 算法开始时，所有顶点的标志位置 零； „ 在周游的过程中，当某个顶点被访问 时，其标志位就被标记为已访问。 北京大学信息学院 ©版权所有，转载或翻印必究 Page 38 图的周游算法框架 //图的周游算法的实现 void graph_traverse(Graph& G){ //对图所有顶点的标志位进行初始化 for(int i=0;i<G.VerticesNum();i++) G.Mark[i]=UNVISITED; //检查图的所有顶点是否被标记过，如果未被标记， //则从该未被标记的顶点开始继续周游 //do_traverse函数用深度优先或者广度优先 for(int i=0;i<G.VerticesNum();i++) if(G.Mark[i]== UNVISITED) do_traverse(G, i); } 北京大学信息学院 ©版权所有，转载或翻印必究 Page 39 图的生成树 „ 图的所有顶点加上周游过程中经 过的边所构成的子图称作图的生 成树 „ 图的生成森林 北京大学信息学院 ©版权所有，转载或翻印必究 Page 40 6.4.1 深度优先搜索 „ 深度优先搜索（depth-first search，简称 DFS）基本思想 „ 访问一个顶点V，然后访问该顶点邻接到的未被访 问过的顶点V’ „ 再从V’出发递归地按照深度优先的方式周游 „ 当遇到一个所有邻接于它的顶点都被访问过了的顶 点U时，则回到已访问顶点序列中最后一个拥有未 被访问的相邻顶点的顶点W „ 再从W出发递归地按照深度优先的方式周游 „ 最后，当任何已被访问过的顶点都没有未被访问的 相邻顶点时，则周游结束 „ 深度优先搜索树（depth-first search tree） 北京大学信息学院 ©版权所有，转载或翻印必究 Page 41 深度优先搜索的顺序是a，b，c，f，d，e，g 北京大学信息学院 ©版权所有，转载或翻印必究 Page 42 从一个顶点出发的深度优先搜索 void DFS(Graph& G, int V){ //深度优先搜索算法实现 G.Mark[V]= VISITED; //访问顶点V，并标记其标志位 PreVisit(G, V); //访问V for(Edge e=G. FirstEdge(V); G.IsEdge(e); e=G. NextEdge(e)) //访问V邻接到的未被访问过的顶点，并递归地按照 //深度优先的方式进行周游 if(G.Mark[G. ToVertices(e)]== UNVISITED) DFS(G, G. ToVertices(e)); PostVisit(G, V); //访问V }