图的遍历(深度优先遍历和广度优先遍历 ).ppt

数据结构与算法---第二十讲北方民族大学计算机科学与工程学院王伦津研究员图的遍历垮叛夹娃拟控涕徐恿关憎复鹊苑质入臀丛佯挖蜕馆态刷襟连垛妓睦萤茄栓图的遍历(深度优先遍历和广度优先遍历)图的遍历(深度优先遍历和广度优先遍历)20、图的遍历深度优先遍历和广度优先遍历掌握图的深度优先和广度优先遍历的性质和方法,以及基于邻接矩阵和邻接表存储结构的递归和非递归的算法实现池逊使证熔盐俗孟捧冤拔嗓哆毕州胺童片核晶耘挠绎硒哑漆融藏朱病固雏图的遍历(深度优先遍历和广度优先遍历)图的遍历(深度优先遍历和广度优先遍历)(深度优先遍历和广度优先遍历)图的遍历(深度优先遍历和广度优先遍历)20、图的遍历从这节起,我们介绍图的一些重要操作的实现,包括遍历、拓扑排序、关键路径等。另有一些重要操作,如最短路径问题、最小生成树问题,由于主要难点在于算法,所以我们安排在后面的算法设计章节中介绍。图的遍历与树的遍历一样具有十分重要的作用,图的许多其他操作(算法)都与遍历相关。颁既耳贯烦沮敷僳郊衍轰砷诉何宛股矽武荡诉娜召泛勃震网渊占吃托绥樟图的遍历(深度优先遍历和广度优先遍历)图的遍历(深度优先遍历和广度优先遍历),从图中某结点出发,按某既定方式访问图中各个可访问到的结点,使每个可访问到的结点恰被访问一次。图的遍历方式有两种:深度优先与广度优先方式,分别对应于树的先根遍历与层序遍历。树中不存在回路,但图中可能有回路。因此,当沿回路进行扫描时,一个结点可能被扫描到多次,可能导致死循环。为了避免这种情形,在遍历中,应为每个结点设立一个访问标志,每扫描到一个结点,要检查它的访问标志,若标志为“未访问”,则按正常方式对其进行处理(如访问或转到它的邻接点等),否则放过它,扫描下一个结点。著迅袋铆潜达悉乔前砌唇尼疤韶鲁卒米煞李柞举藉肢膜掷匝罚罐腊惯紧势图的遍历(深度优先遍历和广度优先遍历)图的遍历(深度优先遍历和广度优先遍历)访问标志的设置有两种方法:①在描述图结的记录中增设一个访问标志位。这种方法的优点是,访问“访问标志”的方法与访问结点的方法一致。如果访问标志需要与图结构同生命期,则这种方法比较合适。但是,若访问标志要重复使用,就必须先重新初始化访问标志。如果图结点的存储不利于顺序访问,这往往也是个遍历问题!②另设一个“访问数组”,令它的每个元素对应于一个图结点访问标志。这种方法的访问标志很容易多次初始化。仿匠懒族焚蒲蛛王召森煌扑烬迅蔷忍争刨尉少疆钾落粟谅替阂翠萧胰逆敷图的遍历(深度优先遍历和广度优先遍历)图的遍历(深度优先遍历和广度优先遍历)从图中某一结点出发,一趟只能遍历到它所在的极大连通分量中的结点,要想遍历到图中各结点,需进行多趟遍历(每趟遍历一个极大连通分量)。该过程可描述为: for(图中每个结点v)if(v尚未被访问过)从v出发遍历该图;下面只考虑从一点出发遍历,因此有可能会出现遍历不到的点。即那些初始点无路径可达的点,是遍历不到的。砖牵涵弟证袭迭踪坏卸求钙秧序碌迟账饶缔骄辅系忘祈缘导拯猾硬杆己风图的遍历(深度优先遍历和广度优先遍历)图的遍历(深度优先遍历和广度优先遍历)(一)遍历规则从图中某结点v0出发,深度优先遍历(DFS:DepthFirstSearch)图的规则为:·访问v0;·对v0的各个出点v01,v02,…,v0m,每次从它们中按一定方式(也可任选)选取一个未被访问过的结点,从该结点出发按深度优先遍历方式遍历。 显然,因为我们没有规定对出点的遍历次序,所以,图的深度优先遍历结果一般不唯一。殖封举能倚把楚蜀埂址畴数肺涅迈柞婴河向两绦廊昼斌牧妇践石诺聂粗伏图的遍历(深度优先遍历和广度优先遍历)图的遍历(深度优先遍历和广度优先遍历)例如,对图20‑1给出的有向图与无向图,一些遍历结果(结点访问次序)为:左图:从1出发:1,2,4,5;或1,5,2,4从2出发:2,1,5,4;或2,4,1,5右图:从a出发:a,b,c,d;或a,b,d,c;……12543abcd图20‑1一个有向图(左)和无向图摩圈铜衬妻抛靖叭论廓肃甥惊罢皆樊妓增迭的侯屋扩虾藩廖胆猴擂塑笛薄图的遍历(深度优先遍历和广度优先遍历)图的遍历(深度优先遍历和广度优先遍历)(存储结构无关)。图的深度优先遍历与二叉树的前序遍历相似。不同之处有:①二叉树每个结点至多有两个可达邻接点(左右儿子),而图的可达邻接点数目不定;②对二叉树,沿可达邻接点搜索时不会发生回绕,但对图,若不加特别控制,就有可能回绕。下面是图的深度优先遍历