DFS及BFS的算法講解(含例題)【教學(xué)類別】

1 1應(yīng)用應(yīng)用2 2蛋糕2 2應(yīng)用應(yīng)用2 2l圖是一種靈活的數(shù)據(jù)結(jié)構(gòu)，一般作為一種模型用來定義對象圖是一種靈活的數(shù)據(jù)結(jié)構(gòu)，一般作為一種模型用來定義對象之間的關(guān)系或聯(lián)系。對象由頂點（之間的關(guān)系或聯(lián)系。對象由頂點（V）表示，而對象之間的關(guān)）表示，而對象之間的關(guān)系或者關(guān)聯(lián)則通過圖的邊（系或者關(guān)聯(lián)則通過圖的邊（E）來表示。圖可以分為有向圖和）來表示。圖可以分為有向圖和無向圖，一般用無向圖，一般用G=(V,E)來表示圖。經(jīng)常用鄰接矩陣或者鄰接表來表示圖。經(jīng)常用鄰接矩陣或者鄰接表來描述一副圖圖的遍歷就是從圖中的某個頂點出發(fā)，按某種方來描述一副圖圖的遍歷就是從圖中的某個頂點出發(fā)，按某種方法對圖中的所有頂點訪問且僅訪問一次。為了保證圖中的頂點法對圖中的所有頂點訪問且僅訪問一次。為了保證圖中的頂點在遍歷過程中僅訪問一次，要為每一個頂點設(shè)置一個訪問標(biāo)志在遍歷過程中僅訪問一次，要為每一個頂點設(shè)置一個訪問標(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的鄰接點的鄰接點K)K)if(K if(K未被訪問未被訪問)if(k=e)if(k=e)returnreturn true;true;標(biāo)記標(biāo)記K;K;dfs(dfs(k);k);每次遞歸到一個點，則檢查每次遞歸到一個點，則檢查是否存在與它相鄰，而且未是否存在與它相鄰，而且未被訪問的點，有則被訪問的點，有則遞歸遞歸訪問訪問這個點，無則返回上一層。這個點，無則返回上一層。7 7應(yīng)用應(yīng)用2 28 8應(yīng)用應(yīng)用2 29 9應(yīng)用應(yīng)用2 2基本框架通常用隊列通常用隊列(先進(jìn)先出先進(jìn)先出,FIFOFIFO)實現(xiàn)實現(xiàn)初始化隊列初始化隊列Q.Q.Q=Q=起點起點s;s;標(biāo)記標(biāo)記s s為己訪問為己訪問;whilewhile(Q(Q非空非空)取取Q Q隊首元素隊首元素u;uu;u出隊出隊;if if(u=(u=目標(biāo)狀態(tài)目標(biāo)狀態(tài))所有與所有與u u相鄰且未被訪問的點進(jìn)入隊列相鄰且未被訪問的點進(jìn)入隊列;標(biāo)記與標(biāo)記與u u相鄰的點為已訪問相鄰的點為已訪問;1010應(yīng)用應(yīng)用2 2DFS類似于樹的先根遍歷，優(yōu)先訪問的是沒有訪問過的子節(jié)點；BFS類似于樹的層次遍歷，一層一層來訪問，所以適合有目標(biāo)求最短路的步數(shù)；DFS/BFS多用于解決連通性問題及最短路問題;多數(shù)情況下運(yùn)行BFS所需的內(nèi)存會大于DFS需要的內(nèi)存(DFS一次訪問一條路，BFS一次訪問多條路)，但DFS容易爆，BFS通過控制隊列可以很好解決爆隊列風(fēng)險1111應(yīng)用應(yīng)用2 2出棧次序 X星球特別講究秩序，所有道路都是單行線。一個甲殼蟲車隊，共16輛車，按照編號先后發(fā)車，夾在其它車流中，緩緩前行。路邊有個死胡同，只能容一輛車通過，是臨時的檢查站，如圖【p1.png】所示。X星球太死板，要求每輛路過的車必須進(jìn)入檢查站，也可能不檢查就放行，也可能仔細(xì)檢查。如果車輛進(jìn)入檢查站和離開的次序可以任意交錯。那么，該車隊再次上路后，可能的次序有多少種？為了方便起見，假設(shè)檢查站可容納任意數(shù)量的汽車。顯然，如果車隊只有1輛車，可能次序1種；2輛車可能次序2種；3輛車可能次序5種?，F(xiàn)在足足有16輛車啊，親！需要你計算出可能次序的數(shù)目這是一個整數(shù)，請通過瀏覽器提交答案，不要填寫任何多余的內(nèi)容（比如說明性文字）。1212應(yīng)用應(yīng)用2 21313應(yīng)用應(yīng)用2 2輸入一個m行n列的字符矩陣，統(tǒng)計字符“”組成多少個八連塊。如果兩個字符“”所在的格子相鄰（八個方向），就說明他們屬于同一個八連塊。如圖，有兩個八連塊 *1414應(yīng)用應(yīng)用2 2方格填數(shù) 如下的10個格子,填入09的數(shù)字。要求：連續(xù)的兩個數(shù)字不能相鄰。（左右、上下、對角都算相鄰）一共有多少種可能的填數(shù)方案？請?zhí)顚懕硎痉桨笖?shù)目的整數(shù)。1515應(yīng)用應(yīng)用2 2方格分割 6x6的方格，沿著格子的邊線剪開成兩部分。要求這兩部分的形狀完全相同。如圖：p1.png,p2.png,p3.png 就是可行的分割法。試計算：包括這3種分法在內(nèi)，一共有多少種不同的分割方法。注意：旋轉(zhuǎn)對稱的屬于同一種分割法。請?zhí)峤辉撜麛?shù)，不要填寫任何多余的內(nèi)容或說明文字。1616應(yīng)用應(yīng)用2 2如【圖1.jpg】,有12張連在一起的12生肖的郵票?，F(xiàn)在你要從中剪下5張來，要求必須是連著的。（僅僅連接一個角不算相連）比如，【圖2.jpg】，【圖3.jpg】中，粉紅色所示部分就是合格的剪取。請你計算，一共有多少種不同的剪取方法。1717應(yīng)用應(yīng)用2 21818應(yīng)用應(yīng)用2 2