《DFS及BFS的算法講解(含例題)【教學(xué)類別】》由會(huì)員分享，可在線閱讀，更多相關(guān)《DFS及BFS的算法講解(含例題)【教學(xué)類別】（18頁珍藏版）》請(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)，一般作為一種模型用來定義對(duì)象圖是一種靈活的數(shù)據(jù)結(jié)構(gòu)，一般作為一種模型用來定義對(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ān)聯(lián)則通過圖的邊（E）來表示。圖可以分為有向圖和）來表示。圖可以分為有向圖和無向圖，一般用無向圖，一般用G=(V,E)來表示圖。經(jīng)常用鄰接矩陣或者鄰接表來表示圖。經(jīng)常用鄰接矩陣或者鄰接表來描述一副圖圖的遍歷就是從圖中的某個(gè)頂點(diǎn)出發(fā)，按某種方來描述一副圖圖的遍歷就是從圖中的某個(gè)頂點(diǎn)出發(fā)，按某種方法對(duì)圖中的所有頂點(diǎn)訪

2、問且僅訪問一次。為了保證圖中的頂點(diǎn)法對(duì)圖中的所有頂點(diǎn)訪問且僅訪問一次。為了保證圖中的頂點(diǎn)在遍歷過程中僅訪問一次，要為每一個(gè)頂點(diǎn)設(shè)置一個(gè)訪問標(biāo)志在遍歷過程中僅訪問一次，要為每一個(gè)頂點(diǎn)設(shè)置一個(gè)訪問標(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再舉一例完全二叉樹再舉一例完全二叉樹 練習(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未被訪問未被訪問)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)，則檢查是否存在與它相鄰，而且未是否存在與它相鄰，而且未被訪問的點(diǎn)，有則被訪問的點(diǎn)，有則遞歸遞歸訪問訪問這個(gè)點(diǎn)，無則返回上一層。這個(gè)點(diǎn)，無則返回上一層。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為己訪問為己訪問;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相鄰且未被訪問的點(diǎn)進(jìn)入隊(duì)列相鄰且未被訪問的點(diǎn)進(jìn)入隊(duì)列;標(biāo)記與標(biāo)記與u u相鄰的點(diǎn)為已訪問相鄰的點(diǎn)為已訪問;1010應(yīng)用應(yīng)用2 2DFS類似于樹的先根遍歷，優(yōu)先訪問的是沒有訪問過的子節(jié)點(diǎn)；BFS類似于樹的層次遍歷，一層一層來訪問，所以適合有目標(biāo)求最短路的步數(shù)；DFS/BFS多用于解決連通性問題及最短路問題;多數(shù)情況下運(yùn)行BFS所需的內(nèi)存會(huì)大于DFS需要的內(nèi)存(DFS一次訪問一條路，BFS一次訪問多條路)，但DFS容易爆，BFS通過控制隊(duì)列可以很好解決爆隊(duì)列風(fēng)險(xiǎn)1111應(yīng)用應(yīng)用2 2出棧次序 X星球

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

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