圖的遍歷：DFS和BFS演算法- IT閱讀

以上是最基本的dfs演算法實現，事實上，程式碼結構絕不是一成不變的。

例如，應用dfs求一串元素的所有可能的排列，抽象出來的圖的分支就十分龐大。

我們不 ... 圖的遍歷：DFS和BFS演算法 首頁 最新 HTML CSS JavaScript jQuery Python3 Python2 Java C C++ Go SQL 首頁 最新 Search 圖的遍歷：DFS和BFS演算法 2019-02-06254 DFS（深度優先演算法） 1.原理概述 最基本的DFS是用來解決無向圖的遍歷問題的。

無向圖用沿主對角線對稱的鄰接矩陣儲存。

DFS演算法最基本的程式碼實現如下： voiddfs(intcur)//cur是當前所在的頂點編號 { sum++;//每訪問一個頂點，sum+1 if(sum==n)return; for(i=1;i<=n;i++)//從1號頂點到n號頂點依次嘗試，看哪些頂點與當前頂點cur有邊相連 { if(e[cur][i]==1&&book[i]==0) { book[i]=1;//標記頂點i已經訪問過 dfs(i);//從頂點i再出發繼續遍歷 } } } 上面，cur儲存當前正在遍歷的頂點，二維陣列e儲存的是圖的邊（鄰接矩陣），book用來記錄哪些頂點已經訪問過，sum用來記錄已經訪問過的頂點個數，n儲存圖中頂點的總個數。

2.用DFS求所有可能的排列組合 以上是最基本的dfs演算法實現，事實上，程式碼結構絕不是一成不變的。

例如，應用dfs求一串元素的所有可能的排列，抽象出來的圖的分支就十分龐大。

我們不關心對整張圖的全部遍歷，而是希望分別輸出每種可能的完整排列順序。

這就需要將dfs的步驟改成： 定義全域性的用於存放所有解的物件和存放一次解的物件。

在遞迴函式中，確定遞迴終止條件（一般為sum==n），並在終止時將一次完整的解存檔。

在遞迴函式中，若沒有終止，程式碼結構應該是：則先執行動作，呼叫遞迴，再撤銷動作。

一個完整的實現程式碼為： voiddfs(ints,vector&nums){ if(s==nums.size())result.push_back(oneResult); for(inti=0;imin)return; if(cur==n)//如果到達了目標城市 { if(disn) { break; } } //當一個頂點拓展結束後，要將head++，相當於從隊首刪除該頂點 head++; } 2.用BFS解最少轉機問題 假設有當前城市和目標城市，兩者沒有直航，但有和其他城市的航班往來。

希望找到一種最少轉機的方法。

這個問題中，我們不關心兩個城市間的往來時間（邊的權值），如果可以往來，一律視為有權值為1的邊。

我們關心從城市A到B經過的邊的數量最少。

這也是DFS和BFS的不同應用之處。

核心程式碼如下： while(head