【DFS】深度優先搜尋遞迴方式講解- IT閱讀 - ITREAD01.COM ...

Depth First Search英文的縮寫，翻譯過來就是“深度優先搜尋”。

從名字上我們可以大概的看出，DFS主要是一種搜尋演算法，按照深度優先的方式. 深度優先搜尋 ... 【DFS】深度優先搜尋遞迴方式講解 首頁 最新 HTML CSS JavaScript jQuery Python3 Python2 Java C C++ Go SQL 首頁 最新 Search 【DFS】深度優先搜尋遞迴方式講解 2019-01-31254 前言 記得第一次接觸到DFS還是在去年大概三四月份，當時也是在準備比賽的時候聽說DFS很重要（原諒我是個小白），然後就去Google了一波什麼叫做DFS，當時的我剛開始學習C++，還沒有學習資料結構，講道理當時我看懂了演算法原理，但是對於什麼圖呀，樹呀的還真是一竅不通。

後邊學習了資料結構後，對於DFS原理也是相當的瞭解（自我感覺），但從來沒有總結過，今天主要是進行DFS的演算法進行簡單的自我總結，一是準備比賽，二是也應該從現在開始正式的拿起資料結構了（原諒我花了半年時間搞web開發去了）。

———————————————-以上內容不重要（純屬我自己發牢騷） 初識DFS 什麼是DFS？DepthFirstSearch英文的縮寫，翻譯過來就是“深度優先搜尋”。

從名字上我們可以大概的看出，DFS主要是一種搜尋演算法，按照深度優先的方式 深度優先搜尋演算法（英語：Depth-First-Search，簡稱DFS）是一種用於遍歷或搜尋樹或圖的演算法。

沿著樹的深度遍歷樹的節點，儘可能深的搜尋樹的分支。

當節點v的所在邊都己被探尋過，搜尋將回溯到發現節點v的那條邊的起始節點。

這一過程一直進行到已發現從源節點可達的所有節點為止。

如果還存在未被發現的節點，則選擇其中一個作為源節點並重復以上過程，整個程序反覆進行直到所有節點都被訪問為止。

屬於盲目搜尋。

主要思想：不撞南牆不回頭。

深度優先遍歷的主要思想就是：首先以一個未被訪問過的頂點作為起始頂點，沿當前頂點的邊走到未訪問過的頂點；當沒有未訪問過的頂點時，則回到上一個頂點，繼續試探訪問別的頂點，直到所有的頂點都被訪問。

沿著某條路徑遍歷直到末端，然後回溯，再沿著另一條進行同樣的遍歷，直到所有的頂點都被訪問過為止。

【以上引用來自維基百科】 小結： 深度優先搜尋——類似於樹的先根遍歷，是樹的先根遍歷的推廣 簡述演算法過程 1、任選一頂點作始點v，訪問該頂點 2、沿深度方向，依次遍歷v的未訪問鄰接點——直到本次遍歷結束 3、一次遍歷完時，若有未訪問頂點：任選一個未訪問頂點作起始點，GOTO第二步 演算法演示 遞迴虛擬碼演示 DFS(dep,、、、）//dep代表目前DFS的深度 { if(找到解||走不下去){ 、、、//在此處進行相應的操作 return; } 列舉下一種情況，DFS（dep+1,、、、） } 遞迴虛擬碼演示（稍微詳細點，其實都是一樣的） boolvisited[MAXNODE];//頂點的訪問標識陣列 voidDFSInit(GraphG){ for(i=0;iv } w=NextAdj(G,v,w);//返回：v的在鄰接點w後的鄰接點，0表示不存在 } } DFS遍歷——圖解過程 注： 儲存結構不確定，遍歷結果不唯一 其中一種DFS序列：DFS(G,v1)=(v1,v2,v3,v6,v5,v7,v4,v8,v9) 小結 從圖解和虛擬碼中我們可以看出，DFS其實就是找準一條路徑（我們可以暫且這樣認為），一直走下去（深度優先），直到滿足條件（這屬於運氣好了）或者走投無路、走不下去（撞南牆了）。

如果沒有找到相應的結果狀態，那麼就回退一步（回溯），再進行下一步找路徑，再撞再回溯，一直到找到目標狀態或者所有情況都遍歷完，程式結束 DFS遞迴演算法框架 /* 該DFS框架以2D座標範圍為例，來體現DFS演算法的實現思想。

*/ #include #include #include usingnamespacestd; constintmaxn=100; boolvst[maxn][maxn];//訪問標記 intmap[maxn][maxn];//座標範圍 intdir[4][2]={0,1,0,-1,1,0,-1,0};//方向向量，(x,y)周圍的四個方向 boolCheckEdge(intx,inty)//邊界條件和約束條件的判斷 { if(!vst[x][y]&&...)//滿足條件 return1; else//與約束條件衝突 return0; } voiddfs(intx,inty) { vst[x][y]=1;//標記該節點被訪問過 if(map[x][y]==G)//出現目標態G { ......//做相應處理 return; } for(inti=0;i<4;i++) { if(CheckEdge(x+dir[i][0],y+dir[i][1]))//按照規則生成下一個節點 dfs(x+dir[i][0],y+dir[i][1]); } return;//沒有下層搜尋節點，回溯 } intmain() { ...... return0; } DFS遞迴演算法例項講解 我一直都認為，對於我們學習技術的學生來說，想要了解一門技術或者一個知識點的，最好的方法是“在理解了理論知識的基礎上進行實踐”，實踐才是檢驗真理的唯一標準，同時這種實踐的方式學習知識點，才是印象最深刻，同時也是提高學習激情和慾望的有效方式。

話不多說，我們進入實戰階段。

原題我記不清了，這邊就簡單的說下題意 【題目】在給定的一個二維陣列中找尋從起點（0，0）開始走，能到達哪些區域（真不記得題意了，大家自行腦補吧） 00110 10011 11000 10011 00100 我們假設上邊就是輸入資料（嘻嘻，將就一下），‘0’代表能夠走的，‘1’代表不能走的，可以理解為牆，同時只能在所給的地圖上走，也就是不能跳出去再調回來，求解區域 相信大家對於這個問題其實已經很明確了，其實就和“八連塊”問題是一個道理的 【分析】我們從起點開始走，一直沿著一條路走，一直走到最後走不動的時候，進行回溯，再找尋下一條路線，直到最後沒有路走，回到了起點位置（大家可以想想為什麼會回到起點位置）結束。

我們走過的地方其實就是題目的答案 原始碼 我建議先自己實現一波後再來看喲。

#include #include #defineN10 usingnamespacestd; intdir[4][2]={0,1,0,-1,1,0,-1,0}; intvst[N][N];//標記陣列 intmap[N][N];//給定圖 boolcheckEdge(intx,inty); voiddfs(intx,inty); intmain(){ intn; cin>>n; memset(vst,0,sizeof(vst));//初始化 memset(map,-1,sizeof(map)); for(inti=0;i>map[i][j];//輸入圖 } } dfs(0,0);//進行DFS for(inti=0;i=0&&x<55&&y>=0&&y<5){ returntrue; } returnfalse; } voiddfs(intx,inty){ vst[x][y]=6; for(inti=0;i<4;i++){ if(checkEdge(x+dir[i][0],y+dir[i][1])){ dfs(x+dir[i][0],y+dir[i][1]); } } return; } 參考 相關文章 【DFS】深度優先搜尋遞迴方式講解 算法系列—圖的深度優先搜尋（遞迴）/C++ DFS（深度優先搜尋樹）遞迴非遞迴實現 DFS（深度優先搜尋）的非遞迴實現 DFS深度優先搜尋(入門) DFS深度優先搜尋(1)--poj3984(基本模板題) 基於鄰接表實現的DFS深度優先搜尋 DFS（深度優先搜尋）,BFS（廣度優先搜尋）小總結 搜尋_DFS(深度優先搜尋)_演算法分析 DFS深度優先搜尋入門（1） 二叉樹深度優先搜尋、廣度優先搜尋遞迴及非遞迴實現 DFS深度優先搜尋 對於深度優先搜尋演算法的理解 深度優先搜尋DFS(遞迴+非遞迴) 深度優先搜尋（DFS）遞迴與非遞迴實現邏輯詳解 分類導航 HTML/CSS HTML教程 HTML5教程 CSS教程 CSS3教程 JavaScript JavaScript教程 jQuery教程 Node.js教程 服務端 Python教程 Python3教程 Linux教程 Docker教程 Ruby教程 Java教程 JSP教程 C教程 C++教程 Perl教程 Go教程 PHP教程 正則表達式 資料庫 SQL教程 MySQL教程 PostgreSQL教程 SQLite教程 MongoDB教程 Redis教程 Memcached教程 行動端 IOS教程 Swift教程 Advertisement 三度辭典 Copyright©2016-2021IT閱讀  Itread01.comAllRightsReserved. 0.001291036605835