DFS及BFS的算法講解含例題

DFS及BFS的算法講解含例題演示文稿當(dāng)前1頁，總共17頁。蛋糕當(dāng)前2頁，總共17頁。相關(guān)理論-圖的遍歷圖是一種靈活的數(shù)據(jù)結(jié)構(gòu)，一般作為一種模型用來定義對象之間的關(guān)系或聯(lián)系。對象由頂點(diǎn)（V）表示，而對象之間的關(guān)系或者關(guān)聯(lián)則通過圖的邊（E）來表示。圖可以分為有向圖和無向圖，一般用G=(V,E)來表示圖。經(jīng)常用鄰接矩陣或者鄰接表來描述一副圖圖的遍歷就是從圖中的某個頂點(diǎn)出發(fā)，按某種方法對圖中的所有頂點(diǎn)訪問且僅訪問一次。為了保證圖中的頂點(diǎn)在遍歷過程中僅訪問一次，要為每一個頂點(diǎn)設(shè)置一個訪問標(biāo)志。通常有兩種方法：深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)當(dāng)前3頁，總共17頁。當(dāng)前4頁，總共17頁。再舉一例完全二叉樹練習(xí)三序遍歷當(dāng)前5頁，總共17頁。DFS基本思想基本步驟：1.從圖中某個頂點(diǎn)v0出發(fā)，首先訪問v0;2.訪問結(jié)點(diǎn)v0的第一個鄰接點(diǎn)，以這個鄰接點(diǎn)vt作為一個新節(jié)點(diǎn)，訪問vt所有鄰接點(diǎn)。直到以vt出發(fā)的所有節(jié)點(diǎn)都被訪問到，回溯到v0的下一個未被訪問過的鄰接點(diǎn)，以這個鄰結(jié)點(diǎn)為新節(jié)點(diǎn)，重復(fù)上述步驟。直到圖中所有與v0相通的所有節(jié)點(diǎn)都被訪問到。3.若此時圖中仍有未被訪問的結(jié)點(diǎn)，則另選圖中的一個未被訪問的頂點(diǎn)作為起始點(diǎn)。重復(fù)深度優(yōu)先搜索過程，直到圖中的所有節(jié)點(diǎn)均被訪問過。當(dāng)前6頁，總共17頁。DFS的實(shí)現(xiàn)

基本框架voidDFS(PointP){for(所有P的鄰接點(diǎn)K){if(K未被訪問){ if(k==e) returntrue;標(biāo)記K;dfs(k);}}}每次遞歸到一個點(diǎn)，則檢查是否存在與它相鄰，而且未被訪問的點(diǎn)，有則遞歸訪問這個點(diǎn)，無則返回上一層。當(dāng)前7頁，總共17頁。當(dāng)前8頁，總共17頁。BFS基本思想當(dāng)前9頁，總共17頁。BFS基本思想基本框架通常用隊(duì)列(先進(jìn)先出,FIFO)實(shí)現(xiàn) 初始化隊(duì)列Q. Q={起點(diǎn)s};標(biāo)記s為己訪問; while(Q非空){ 取Q隊(duì)首元素u;u出隊(duì); if(u==目標(biāo)狀態(tài)){…} 所有與u相鄰且未被訪問的點(diǎn)進(jìn)入隊(duì)列; 標(biāo)記與u相鄰的點(diǎn)為已訪問; }當(dāng)前10頁，總共17頁。兩者比較DFS類似于樹的先根遍歷，優(yōu)先訪問的是沒有訪問過的子節(jié)點(diǎn)；BFS類似于樹的層次遍歷，一層一層來訪問，所以適合有目標(biāo)求最短路的步數(shù)；DFS/BFS多用于解決連通性問題及最短路問題;多數(shù)情況下運(yùn)行BFS所需的內(nèi)存會大于DFS需要的內(nèi)存(DFS一次訪問一條路，BFS一次訪問多條路)，但DFS容易爆，BFS通過控制隊(duì)列可以很好解決"爆隊(duì)列"風(fēng)險當(dāng)前11頁，總共17頁。出棧次序X星球特別講究秩序，所有道路都是單行線。一個甲殼蟲車隊(duì)，共16輛車，按照編號先后發(fā)車，夾在其它車流中，緩緩前行。

路邊有個死胡同，只能容一輛車通過，是臨時的檢查站，如圖【p1.png】所示。

X星球太死板，要求每輛路過的車必須進(jìn)入檢查站，也可能不檢查就放行，也可能仔細(xì)檢查。

如果車輛進(jìn)入檢查站和離開的次序可以任意交錯。那么，該車隊(duì)再次上路后，可能的次序有多少種？

為了方便起見，假設(shè)檢查站可容納任意數(shù)量的汽車。

顯然，如果車隊(duì)只有1輛車，可能次序1種；2輛車可能次序2種；3輛車可能次序5種。

現(xiàn)在足足有16輛車啊，親！需要你計(jì)算出可能次序的數(shù)目

這是一個整數(shù)，請通過瀏覽器提交答案，不要填寫任何多余的內(nèi)容（比如說明性文字）。

當(dāng)前12頁，總共17頁。典型例題：p1.png當(dāng)前13頁，總共17頁。油田輸入一個m行n列的字符矩陣，統(tǒng)計(jì)字符“@”組成多少個八連塊。如果兩個字符“@”所在的格子相鄰（八個方向），就說明他們屬于同一個八連塊。如圖，有兩個八連塊****@*@@*@

*@**@@@@*@@@**@當(dāng)前14頁，總共17頁。典型例題

方格填數(shù)如下的10個格子,填入0~9的數(shù)字。要求：連續(xù)的兩個數(shù)字不能相鄰。（左右、上下、對角都算相鄰）一共有多少種可能的填數(shù)方案？請?zhí)顚懕硎痉桨笖?shù)目的整數(shù)。

當(dāng)前15頁，總共17頁。DFS：圖的遍歷方格分割6x6的方格，沿著格子的邊線剪開成兩部分。要求這兩部分的形狀完全相同。如圖：p1.png,p2.png,p3.png就是可行的分割法。試計(jì)算：包括這3種分法在內(nèi)，一共有多少種不同的分割方法。注意：旋轉(zhuǎn)對稱的屬于同一種分割法。請?zhí)峤辉撜麛?shù)，不要填寫任何多余的內(nèi)容或說明文字。當(dāng)前16頁，總共17頁。剪郵票

如【圖1.jpg】,有12張連在一起的12生肖的