圖的遍歷深度優(yōu)先遍歷和廣度優(yōu)先遍歷

《圖的遍歷深度優(yōu)先遍歷和廣度優(yōu)先遍歷》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、數(shù)據(jù)結(jié)構(gòu)與算法---第二十講北方民族大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院王倫津研究員圖的遍歷20、圖的遍歷深度優(yōu)先遍歷和廣度優(yōu)先遍歷掌握?qǐng)D的深度優(yōu)先和廣度優(yōu)先遍歷的性質(zhì)和方法，以及基于鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)的遞歸和非遞歸的算法實(shí)現(xiàn)目錄20.1概述20.2深度優(yōu)先遍歷20.3深度優(yōu)先遍歷的性質(zhì)20.4廣度優(yōu)先遍歷20.5廣度優(yōu)先遍歷的性質(zhì)20、圖的遍歷從這節(jié)起，我們介紹圖的一些重要操作的實(shí)現(xiàn)，包括遍歷、拓?fù)渑判颉㈥P(guān)鍵路徑等。另有一些重要操作，如最短路徑問題、最小生成樹問題，由于主要難點(diǎn)在于算法，所以我們安排在后面的算法設(shè)計(jì)章節(jié)中介紹。圖的遍歷與樹的遍歷一樣具有十分重要的

2、作用，圖的許多其他操作（算法）都與遍歷相關(guān)。20.1概述圖的遍歷的含意是，從圖中某結(jié)點(diǎn)出發(fā)，按某既定方式訪問圖中各個(gè)可訪問到的結(jié)點(diǎn)，使每個(gè)可訪問到的結(jié)點(diǎn)恰被訪問一次。圖的遍歷方式有兩種：深度優(yōu)先與廣度優(yōu)先方式，分別對(duì)應(yīng)于樹的先根遍歷與層序遍歷。樹中不存在回路，但圖中可能有回路。因此，當(dāng)沿回路進(jìn)行掃描時(shí)，一個(gè)結(jié)點(diǎn)可能被掃描到多次，可能導(dǎo)致死循環(huán)。為了避免這種情形，在遍歷中，應(yīng)為每個(gè)結(jié)點(diǎn)設(shè)立一個(gè)訪問標(biāo)志，每掃描到一個(gè)結(jié)點(diǎn)，要檢查它的訪問標(biāo)志，若標(biāo)志為“未訪問”，則按正常方式對(duì)其進(jìn)行處理（如訪問或轉(zhuǎn)到它的鄰接點(diǎn)等），否則放過它，掃描下一個(gè)結(jié)點(diǎn)。訪問標(biāo)志的設(shè)置有兩種

3、方法：①在描述圖結(jié)的記錄中增設(shè)一個(gè)訪問標(biāo)志位。這種方法的優(yōu)點(diǎn)是，訪問“訪問標(biāo)志”的方法與訪問結(jié)點(diǎn)的方法一致。如果訪問標(biāo)志需要與圖結(jié)構(gòu)同生命期，則這種方法比較合適。但是，若訪問標(biāo)志要重復(fù)使用，就必須先重新初始化訪問標(biāo)志。如果圖結(jié)點(diǎn)的存儲(chǔ)不利于順序訪問，這往往也是個(gè)遍歷問題?、诹碓O(shè)一個(gè)“訪問數(shù)組”，令它的每個(gè)元素對(duì)應(yīng)于一個(gè)圖結(jié)點(diǎn)訪問標(biāo)志。這種方法的訪問標(biāo)志很容易多次初始化。從圖中某一結(jié)點(diǎn)出發(fā)，一趟只能遍歷到它所在的極大連通分量中的結(jié)點(diǎn)，要想遍歷到圖中各結(jié)點(diǎn)，需進(jìn)行多趟遍歷（每趟遍歷一個(gè)極大連通分量）。該過程可描述為：for(圖中每個(gè)結(jié)點(diǎn)v)if(v尚未被訪問過)

4、從v出發(fā)遍歷該圖;下面只考慮從一點(diǎn)出發(fā)遍歷，因此有可能會(huì)出現(xiàn)遍歷不到的點(diǎn)。即那些初始點(diǎn)無路徑可達(dá)的點(diǎn)，是遍歷不到的。20.2深度優(yōu)先遍歷(一)遍歷規(guī)則從圖中某結(jié)點(diǎn)v0出發(fā)，深度優(yōu)先遍歷（DFS:DepthFirstSearch）圖的規(guī)則為：·訪問v0；·對(duì)v0的各個(gè)出點(diǎn)v01，v02，…，v0m，每次從它們中按一定方式（也可任選）選取一個(gè)未被訪問過的結(jié)點(diǎn)，從該結(jié)點(diǎn)出發(fā)按深度優(yōu)先遍歷方式遍歷。顯然，因?yàn)槲覀儧]有規(guī)定對(duì)出點(diǎn)的遍歷次序，所以，圖的深度優(yōu)先遍歷結(jié)果一般不唯一。例如，對(duì)圖20?1給出的有向圖與無向圖，一些遍歷結(jié)果（結(jié)點(diǎn)訪問次序）為：左圖：從1出發(fā)：1，

5、2，4，5；或1，5，2，4從2出發(fā)：2，1，5，4；或2，4，1，5右圖：從a出發(fā)：a，b，c，d；或a，b，d，c;……12543abcd圖20?1一個(gè)有向圖（左）和無向圖1.一般算法下面考慮深度優(yōu)先遍歷的遞歸實(shí)現(xiàn)的一般方法（存儲(chǔ)結(jié)構(gòu)無關(guān)）。圖的深度優(yōu)先遍歷與二叉樹的前序遍歷相似。不同之處有：①二叉樹每個(gè)結(jié)點(diǎn)至多有兩個(gè)可達(dá)鄰接點(diǎn)（左右兒子），而圖的可達(dá)鄰接點(diǎn)數(shù)目不定；②對(duì)二叉樹，沿可達(dá)鄰接點(diǎn)搜索時(shí)不會(huì)發(fā)生回繞，但對(duì)圖，若不加特別控制，就有可能回繞。下面是圖的深度優(yōu)先遍歷遞歸算法的一般性描述。如果要另設(shè)一個(gè)數(shù)組作為訪問標(biāo)志，則該數(shù)組要在遞歸過程（函數(shù)）之外

6、初始化為“未訪問”。（二）遞歸實(shí)現(xiàn)方法longDFS(圖g，結(jié)點(diǎn)v0){//圖深度優(yōu)先遍歷遞歸算法。從結(jié)點(diǎn)v0出發(fā)，深度優(yōu)先遍歷圖g，返回訪問到的結(jié)點(diǎn)總數(shù)intnNodes;//寄存訪問到的結(jié)點(diǎn)數(shù)目訪問v0;為v0置已訪問標(biāo)志;nNodes=1;求出v0的第1個(gè)可達(dá)鄰接點(diǎn)v;while(v存在){if(v未被訪問過)nNodes=nNodes+DFS(g,v);求出v0的下個(gè)可達(dá)鄰接點(diǎn)v;}returnnNodes;}1254312345101001210010300001410000500000所示圖的鄰接矩陣g1121304151圖20?1有向圖訪問標(biāo)識(shí)

7、數(shù)組visited1245輸出數(shù)組resu例如從1點(diǎn)深度優(yōu)先遍歷，先把1設(shè)置訪問標(biāo)志，并置入輸出數(shù)組resu，然后從鄰接矩陣的第一行，掃描各列，找到最近的鄰接點(diǎn)2，將其設(shè)置訪問標(biāo)志，并進(jìn)入輸出數(shù)組，接著從鄰接矩陣的2行掃描，找到第一個(gè)構(gòu)成邊的點(diǎn)是1，檢查訪問標(biāo)識(shí)數(shù)組，發(fā)現(xiàn)1已經(jīng)訪問過，跳過，找第二個(gè)構(gòu)成邊的點(diǎn)4，設(shè)置訪問標(biāo)識(shí)，進(jìn)入輸出數(shù)組，再從鄰接矩陣的第4行掃描，尋找構(gòu)成邊的點(diǎn)，除1外在無其他點(diǎn)，返回2行，繼續(xù)尋找，也無新點(diǎn)，返回1，找到5，將5置訪問標(biāo)志，進(jìn)入輸出數(shù)組，1行再無其他新點(diǎn)，遍歷結(jié)束，返回遍歷元素個(gè)數(shù)為4。2．鄰接矩陣實(shí)現(xiàn)這里我們?yōu)榱送怀鲋黝}

8、、簡(jiǎn)化問題，假定圖是用一般的鄰接矩陣存儲(chǔ)，鄰接矩陣用