《DFS及BFS的算法講解(含例題)【教學(xué)類(lèi)別】》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《DFS及BFS的算法講解(含例題)【教學(xué)類(lèi)別】（18頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1 1應(yīng)用應(yīng)用2 2蛋糕2 2應(yīng)用應(yīng)用2 2l圖是一種靈活的數(shù)據(jù)結(jié)構(gòu)，一般作為一種模型用來(lái)定義對(duì)象圖是一種靈活的數(shù)據(jù)結(jié)構(gòu)，一般作為一種模型用來(lái)定義對(duì)象之間的關(guān)系或聯(lián)系。對(duì)象由頂點(diǎn)（之間的關(guān)系或聯(lián)系。對(duì)象由頂點(diǎn)（V）表示，而對(duì)象之間的關(guān)）表示，而對(duì)象之間的關(guān)系或者關(guān)聯(lián)則通過(guò)圖的邊（系或者關(guān)聯(lián)則通過(guò)圖的邊（E）來(lái)表示。圖可以分為有向圖和）來(lái)表示。圖可以分為有向圖和無(wú)向圖，一般用無(wú)向圖，一般用G=(V,E)來(lái)表示圖。經(jīng)常用鄰接矩陣或者鄰接表來(lái)表示圖。經(jīng)常用鄰接矩陣或者鄰接表來(lái)描述一副圖圖的遍歷就是從圖中的某個(gè)頂點(diǎn)出發(fā)，按某種方來(lái)描述一副圖圖的遍歷就是從圖中的某個(gè)頂點(diǎn)出發(fā)，按某種方法對(duì)圖中的所有頂點(diǎn)訪(fǎng)

2、問(wèn)且僅訪(fǎng)問(wèn)一次。為了保證圖中的頂點(diǎn)法對(duì)圖中的所有頂點(diǎn)訪(fǎng)問(wèn)且僅訪(fǎng)問(wèn)一次。為了保證圖中的頂點(diǎn)在遍歷過(guò)程中僅訪(fǎng)問(wèn)一次，要為每一個(gè)頂點(diǎn)設(shè)置一個(gè)訪(fǎng)問(wèn)標(biāo)志在遍歷過(guò)程中僅訪(fǎng)問(wèn)一次，要為每一個(gè)頂點(diǎn)設(shè)置一個(gè)訪(fǎng)問(wèn)標(biāo)志。通常有兩種方法：深度優(yōu)先搜索。通常有兩種方法：深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索和廣度優(yōu)先搜索(BFS)3 3應(yīng)用應(yīng)用2 24 4應(yīng)用應(yīng)用2 2再舉一例完全二叉樹(shù)再舉一例完全二叉樹(shù) 練習(xí)三序遍練習(xí)三序遍歷歷5 5應(yīng)用應(yīng)用2 2基本步驟：基本步驟：6 6應(yīng)用應(yīng)用2 2基本框架void void DFSDFS(PointPoint P)P)for(for(所有所有P P的鄰接點(diǎn)的鄰接點(diǎn)K)K)if(K

3、 if(K未被訪(fǎng)問(wèn)未被訪(fǎng)問(wèn))if(k=e)if(k=e)returnreturn true;true;標(biāo)記標(biāo)記K;K;dfs(dfs(k);k);每次遞歸到一個(gè)點(diǎn)，則檢查每次遞歸到一個(gè)點(diǎn)，則檢查是否存在與它相鄰，而且未是否存在與它相鄰，而且未被訪(fǎng)問(wèn)的點(diǎn)，有則被訪(fǎng)問(wèn)的點(diǎn)，有則遞歸遞歸訪(fǎng)問(wèn)訪(fǎng)問(wèn)這個(gè)點(diǎn)，無(wú)則返回上一層。這個(gè)點(diǎn)，無(wú)則返回上一層。7 7應(yīng)用應(yīng)用2 28 8應(yīng)用應(yīng)用2 29 9應(yīng)用應(yīng)用2 2基本框架通常用隊(duì)列通常用隊(duì)列(先進(jìn)先出先進(jìn)先出,FIFOFIFO)實(shí)現(xiàn)實(shí)現(xiàn)初始化隊(duì)列初始化隊(duì)列Q.Q.Q=Q=起點(diǎn)起點(diǎn)s;s;標(biāo)記標(biāo)記s s為己訪(fǎng)問(wèn)為己訪(fǎng)問(wèn);whilewhile(Q(Q非空非空)取取Q

4、 Q隊(duì)首元素隊(duì)首元素u;uu;u出隊(duì)出隊(duì);if if(u=(u=目標(biāo)狀態(tài)目標(biāo)狀態(tài))所有與所有與u u相鄰且未被訪(fǎng)問(wèn)的點(diǎn)進(jìn)入隊(duì)列相鄰且未被訪(fǎng)問(wèn)的點(diǎn)進(jìn)入隊(duì)列;標(biāo)記與標(biāo)記與u u相鄰的點(diǎn)為已訪(fǎng)問(wèn)相鄰的點(diǎn)為已訪(fǎng)問(wèn);1010應(yīng)用應(yīng)用2 2DFS類(lèi)似于樹(shù)的先根遍歷，優(yōu)先訪(fǎng)問(wèn)的是沒(méi)有訪(fǎng)問(wèn)過(guò)的子節(jié)點(diǎn)；BFS類(lèi)似于樹(shù)的層次遍歷，一層一層來(lái)訪(fǎng)問(wèn)，所以適合有目標(biāo)求最短路的步數(shù)；DFS/BFS多用于解決連通性問(wèn)題及最短路問(wèn)題;多數(shù)情況下運(yùn)行BFS所需的內(nèi)存會(huì)大于DFS需要的內(nèi)存(DFS一次訪(fǎng)問(wèn)一條路，BFS一次訪(fǎng)問(wèn)多條路)，但DFS容易爆，BFS通過(guò)控制隊(duì)列可以很好解決爆隊(duì)列風(fēng)險(xiǎn)1111應(yīng)用應(yīng)用2 2出棧次序 X星球

5、特別講究秩序，所有道路都是單行線(xiàn)。一個(gè)甲殼蟲(chóng)車(chē)隊(duì)，共16輛車(chē)，按照編號(hào)先后發(fā)車(chē)，夾在其它車(chē)流中，緩緩前行。路邊有個(gè)死胡同，只能容一輛車(chē)通過(guò)，是臨時(shí)的檢查站，如圖【p1.png】所示。X星球太死板，要求每輛路過(guò)的車(chē)必須進(jìn)入檢查站，也可能不檢查就放行，也可能仔細(xì)檢查。如果車(chē)輛進(jìn)入檢查站和離開(kāi)的次序可以任意交錯(cuò)。那么，該車(chē)隊(duì)再次上路后，可能的次序有多少種？為了方便起見(jiàn)，假設(shè)檢查站可容納任意數(shù)量的汽車(chē)。顯然，如果車(chē)隊(duì)只有1輛車(chē)，可能次序1種；2輛車(chē)可能次序2種；3輛車(chē)可能次序5種?，F(xiàn)在足足有16輛車(chē)啊，親！需要你計(jì)算出可能次序的數(shù)目這是一個(gè)整數(shù)，請(qǐng)通過(guò)瀏覽器提交答案，不要填寫(xiě)任何多余的內(nèi)容（比如說(shuō)明性

6、文字）。1212應(yīng)用應(yīng)用2 21313應(yīng)用應(yīng)用2 2輸入一個(gè)m行n列的字符矩陣，統(tǒng)計(jì)字符“”組成多少個(gè)八連塊。如果兩個(gè)字符“”所在的格子相鄰（八個(gè)方向），就說(shuō)明他們屬于同一個(gè)八連塊。如圖，有兩個(gè)八連塊 *1414應(yīng)用應(yīng)用2 2方格填數(shù) 如下的10個(gè)格子,填入09的數(shù)字。要求：連續(xù)的兩個(gè)數(shù)字不能相鄰。（左右、上下、對(duì)角都算相鄰）一共有多少種可能的填數(shù)方案？請(qǐng)?zhí)顚?xiě)表示方案數(shù)目的整數(shù)。1515應(yīng)用應(yīng)用2 2方格分割 6x6的方格，沿著格子的邊線(xiàn)剪開(kāi)成兩部分。要求這兩部分的形狀完全相同。如圖：p1.png,p2.png,p3.png 就是可行的分割法。試計(jì)算：包括這3種分法在內(nèi)，一共有多少種不同的分割方法。注意：旋轉(zhuǎn)對(duì)稱(chēng)的屬于同一種分割法。請(qǐng)?zhí)峤辉撜麛?shù)，不要填寫(xiě)任何多余的內(nèi)容或說(shuō)明文字。1616應(yīng)用應(yīng)用2 2如【圖1.jpg】,有12張連在一起的12生肖的郵票。現(xiàn)在你要從中剪下5張來(lái)，要求必須是連著的。（僅僅連接一個(gè)角不算相連）比如，【圖2.jpg】，【圖3.jpg】中，粉紅色所示部分就是合格的剪取。請(qǐng)你計(jì)算，一共有多少種不同的剪取方法。1717應(yīng)用應(yīng)用2 21818應(yīng)用應(yīng)用2 2