圖的深度優先遍歷演算法

⑴ 圖遍歷演算法之DFS/BFS

在計算機科學， 圖遍歷（Tree Traversal，也稱圖搜索）是一系列圖搜索的演算法， 是單次訪問樹結構類型數據（tree data structure)中每個節點以便檢查或更新的一系列機制。圖遍歷演算法可以按照節點訪問順序進行分類，根據訪問目的或使用場景的不同，演算法大致可分為28種：

圖遍歷即以特定方式訪問圖中所有節點，給定節點下有多種可能的搜索路徑。假定以順序方式進行（非並行），還未訪問的節點就需通過堆棧（LIFO）或隊列（FIFO）規則來確定訪問先後。由於樹結構是一種遞歸的數據結構，在清晰的定義下，未訪問節點可存儲在調用堆棧中。本文介紹了圖遍歷領域最流行的廣度優先搜索演算法BFS和深度優先搜索演算法DFS，對其原理、應用及實現進行了闡述。通常意義上而言，深度優先搜索（DFS）通過遞歸調用堆棧比較容易實現，廣義優先搜索通過隊列實現。

深度優先搜索（DFS）是用於遍歷或搜索圖數據結構的演算法，該演算法從根節點開始（圖搜索時可選擇任意節點作為根節點）沿著每個分支進行搜索，分支搜索結束後在進行回溯。在進入下一節點之前，樹的搜索盡可能的加深。
DFS的搜索演算法如下（以二叉樹為例）：假定根節點（圖的任意節點可作為根節點）標記為 ,
(L) : 遞歸遍歷左子樹，並在節點 結束。
(R): 遞歸遍歷右子樹，並在節點 結束。
(N): 訪問節點 。
這些步驟可以以任意次序排列。如果（L）在（R）之前，則該過程稱為從左到右的遍歷；反之，則稱為從右到左的遍歷。根據訪問次序的不同，深度優先搜索可分為 pre-order、in-order、out-order以及post-order遍歷方式。

（a）檢查當前節點是否為空；
（b）展示根節點或當前節點數據；
（c）遞歸調用pre-order函數遍歷左子樹；
（d）遞歸調用pre-order函數遍歷右子樹。
pre-order遍歷屬於拓撲排序後的遍歷，父節點總是在任何子節點之前被訪問。該遍歷方式的圖示如下：

遍歷次序依次為：F -B -A-D- C-E-G- I-H.

（a）檢查當前節點是否為空；
（b）遞歸調用in-order函數遍歷左子樹；
（c）展示根節點或當前節點數據；
（d）遞歸調用in-order函數遍歷右子樹。
在二叉樹搜索中，in-order遍歷以排序順序訪問節點數據。該遍歷方式的圖示如下：

遍歷次序依次為：A -B - C - D - E - F - G -H-I

（a）檢查當前節點是否為空；
（b）遞歸調用out-order函數遍歷右子樹；
（c）展示根節點或當前節點數據；
（d）遞歸調用out-order函數遍歷左子樹。
該遍歷方式與LNR類似，但先遍歷右子樹後遍歷左子樹。仍然以圖2為例，遍歷次序依次為：H- I-G- F- B- E- D- C- A.

（a）檢查當前節點是否為空；
（b）遞歸調用post-order函數遍歷左子樹；
（c）遞歸調用post-order函數遍歷右子樹；
（d）展示根節點或當前節點數據。
post-order遍歷圖示如下：

遍歷次序依次為：A-C-E-D-B-H-I-G-F.

pre-order遍歷方式使用場景：用於創建樹或圖的副本；
in-order遍歷使用場景：二叉樹遍歷；
post-order遍歷使用場景：刪除樹

遍歷追蹤也稱樹的序列化，是所訪問根節點列表。無論是pre-order，in-order或是post-order都無法完整的描述樹特性。給定含有不同元素的樹結構，pre-order或post-order與in-order遍歷方式結合起來使用才可以描述樹的獨特性。

樹或圖形的訪問也可以按照節點所處的級別進行遍歷。在每次訪問下一層級節點之前，遍歷所在高層級的所有節點。BFS從根節點（圖的任意節點可作為根節點）出發，在移動到下一節點之前訪問所有相同深度水平的相鄰節點。

BFS的遍歷方法圖示如下：

遍歷次序依次為： F-B-G-A-D-I-C-E-H.

圖演算法相關的R包為igraph，主要包括圖的生成、圖計算等一系列演算法的實現。

使用方法：

參數說明：

示例：

結果展示：

DFS R輸出節點排序：

使用方法：

參數含義同dfs
示例：

結果展示：

BFS R輸出節點排序：

以尋找兩點之間的路徑為例，分別展示BFS及DFS的實現。圖示例如下：

示例：

輸出結果：

示例：

輸出結果：

[1] 維基網路： https://en.wikipedia.org/wiki/Tree_traversal
[2] GeeksforGeeks: https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
[3] http://webdocs.cs.ualberta.ca/~holte/T26/tree-traversal.html
[4]Martin Broadhurst, Graph Algorithm: http://www.martinbroadhurst.com/Graph-algorithms.html#section_1_1
[5]igraph: https://igraph.org/r/doc/dfs.html
[6]igraph: https://igraph.org/r/doc/bfs.html
[7] Depth-First Search and Breadth-First Search in python: https://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/

⑵ 基本演算法——深度優先搜索（DFS）和廣度優先搜索（BFS）

        深度優先搜索和廣度優先搜索，都是圖形搜索演算法，它兩相似，又卻不同，在應用上也被用到不同的地方。這里拿一起討論，方便比較。

一、深度優先搜索

        深度優先搜索屬於圖演算法的一種，是一個針對圖和樹的遍歷演算法，英文縮寫為DFS即Depth First Search。深度優先搜索是圖論中的經典演算法，利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。一般用堆數據結構來輔助實現DFS演算法。其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次。

基本步奏

（1）對於下面的樹而言，DFS方法首先從根節點1開始，其搜索節點順序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中優先選擇左分枝）。

（2）從stack中訪問棧頂的點；

（3）找出與此點鄰接的且尚未遍歷的點，進行標記，然後放入stack中，依次進行；

（4）如果此點沒有尚未遍歷的鄰接點，則將此點從stack中彈出，再按照（3）依次進行；

（5）直到遍歷完整個樹，stack里的元素都將彈出，最後棧為空，DFS遍歷完成。

二、廣度優先搜索

        廣度優先搜索（也稱寬度優先搜索，縮寫BFS，以下採用廣度來描述）是連通圖的一種遍歷演算法這一演算法也是很多重要的圖的演算法的原型。Dijkstra單源最短路徑演算法和Prim最小生成樹演算法都採用了和寬度優先搜索類似的思想。其別名又叫BFS，屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。基本過程，BFS是從根節點開始，沿著樹(圖)的寬度遍歷樹(圖)的節點。如果所有節點均被訪問，則演算法中止。一般用隊列數據結構來輔助實現BFS演算法。

基本步奏

（1）給出一連通圖，如圖，初始化全是白色（未訪問）；

（2）搜索起點V1（灰色）；

（3）已搜索V1（黑色），即將搜索V2，V3，V4（標灰）；

（4）對V2，V3，V4重復以上操作；

（5）直到終點V7被染灰，終止；

（6）最短路徑為V1，V4，V7.

⑶ 圖遍歷的演算法

圖的遍歷方法目前有深度優先搜索法和廣度（寬度）優先搜索法兩種演算法。 深度優先搜索法是樹的先根遍歷的推廣，它的基本思想是：從圖G的某個頂點v0出發，訪問v0，然後選擇一個與v0相鄰且沒被訪問過的頂點vi訪問，再從vi出發選擇一個與vi相鄰且未被訪問的頂點vj進行訪問，依次繼續。如果當前被訪問過的頂點的所有鄰接頂點都已被訪問，則退回到已被訪問的頂點序列中最後一個擁有未被訪問的相鄰頂點的頂點w，從w出發按同樣的方法向前遍歷，直到圖中所有頂點都被訪問。其遞歸演算法如下：
Boolean visited[MAX_VERTEX_NUM]; //訪問標志數組
Status (*VisitFunc)(int v); //VisitFunc是訪問函數，對圖的每個頂點調用該函數
void DFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum; ++v)
visited[v] = FALSE; //訪問標志數組初始化
for(v=0; v<G.vexnum; ++v)
if(!visited[v])
DFS(G, v); //對尚未訪問的頂點調用DFS
}
void DFS(Graph G, int v){ //從第v個頂點出發遞歸地深度優先遍歷圖G
visited[v]=TRUE; VisitFunc(v); //訪問第v個頂點
for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))
//FirstAdjVex返回v的第一個鄰接頂點，若頂點在G中沒有鄰接頂點，則返回空（0）。
//若w是v的鄰接頂點，NextAdjVex返回v的（相對於w的）下一個鄰接頂點。
//若w是v的最後一個鄰接點，則返回空（0）。
if(!visited[w])
DFS(G, w); //對v的尚未訪問的鄰接頂點w調用DFS
} 圖的廣度優先搜索是樹的按層次遍歷的推廣，它的基本思想是：首先訪問初始點vi，並將其標記為已訪問過，接著訪問vi的所有未被訪問過的鄰接點vi1,vi2,…, vi t，並均標記已訪問過，然後再按照vi1,vi2,…, vi t的次序，訪問每一個頂點的所有未被訪問過的鄰接點，並均標記為已訪問過，依次類推，直到圖中所有和初始點vi有路徑相通的頂點都被訪問過為止。其非遞歸演算法如下：
Boolean visited[MAX_VERTEX_NUM]; //訪問標志數組
Status (*VisitFunc)(int v); //VisitFunc是訪問函數，對圖的每個頂點調用該函數
void BFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum, ++v)
visited[v] = FALSE;
initQueue(Q); //置空輔助隊列Q
for(v=0; v<G.vexnum; ++v)
if(!visited[v]){
visited[v]=TRUE; VisitFunc(v);
EnQueue(Q, v); //v入隊列
while(!QueueEmpty(Q)){
DeQueue(Q, u); //隊頭元素出隊並置為u
for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))
if(!Visited[w]){ //w為u的尚未訪問的鄰接頂點
Visited[w]=TRUE; VisitFunc(w);
EnQueue(Q, w);
}
}
}
}

⑷ 簡述深度優先搜索遍歷的方法。

簡述深度優先搜索遍歷的方法？深度優先搜索演算法(Depth-First-Search, DFS)，最初是一種用於遍歷或搜索樹和圖的演算法，在LeetCode中很常見，雖然感覺不難，但是理解起來還是有點難度的。

簡要概括，深度優先的主要思想就是「不撞南牆不回頭」，「一條路走到黑」，如果遇到「牆」或者「無路可走」時再去走下一條路。

思路
假如對樹進行遍歷，沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支，當達到邊際時回溯上一個節點再進行搜索。如下圖的一個二叉樹。


首先給出這個二叉樹的深度優先遍歷的結果(假定先走左子樹)：1->2->4->5->3->6->7

那是怎樣得到這樣的結果呢？
根據深度優先遍歷的概念：沿著這樹的某一分支向下遍歷到不能再深入為止，之後進行回溯再褲罩搭選定新的分支。

定義節點

class TreeNode{
int val;
TreeNode left;
TreeNode right;
}
遞歸的方式

分別對左右子樹進行遞歸，一直到底才進行回溯。如果不了解遞歸可以參考我的博客你真胡拿的懂悶褲遞歸嗎？。

class Solution{
public void (TreeNode root){
if(root == null){
return;
}
System.out.print(root.val +"->");
(root.left);
(root.right);
}
}
迭代的方式

上面實現了遞歸方式的深度優先遍歷，也可以利用棧把遞歸轉換為迭代的方式。

但是為了保證出棧的順序，需要先壓入右節點，再壓左節點。

class Solution{
public void (TreeNode root){
if(root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
System.out.print(node.val + "->");
if(node.right != null){
stack.push(node.right);
}
if(node.left != null){
stack.push(node.left);
}
}
}
}
接著再列舉個利用深度優先遍歷的方式的題目

掃雷
給定一個表示游戲板的二維字元矩陣，'M'表示一個未挖出的地雷，'E'表示一個未挖出的空方塊，'B' 代表沒有相鄰（上，下，左，右，和所有4個對角線）地雷的已挖出的空白方塊，數字（'1' 到 '8'）表示有多少地雷與這塊已挖出的方塊相鄰，'X' 則表示一個已挖出的地雷。

根據以下規則，返回相應位置被點擊後對應的面板：

如果一個地雷（'M'）被挖出，游戲就結束了- 把它改為'X'。
如果一個沒有相鄰地雷的空方塊（'E'）被挖出，修改它為（'B'），並且所有和其相鄰的方塊都應該被遞歸地揭露。
如果一個至少與一個地雷相鄰的空方塊（'E'）被挖出，修改它為數字（'1'到'8'），表示相鄰地雷的數量。
如果在此次點擊中，若無更多方塊可被揭露，則返回面板。
示例

輸入:

[['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'M', 'E', 'E'],
['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

輸出:

[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
思路：根據給定的規則，當給定一個Click坐標，當不為雷的時候以此坐標為基點向四周8個方向進行深度遍歷，把空格E填充為B，並且把與地雷M相連的空方塊標記相鄰地雷的數量。

注意 ：



在這個題中可以沿著8個方向遞歸遍歷，所有要注意程序中，採用了兩個for循環可以實現向8個方向遞歸。

⑸ Python演算法系列—深度優先遍歷演算法

一、什麼是深度優先遍歷
深度優先遍歷演算法是經典的圖論演算法。從某個節點v出發開始進行搜索。不斷搜索直到該節點所有的邊都被遍歷完，當節點v所有的邊都被遍歷完以後，深度優先遍歷演算法則需要回溯到v以前驅節點來繼續搜索這個節點。
注意：深度優先遍歷問題一定要按照規則嘗試所有的可能才行。

二、二叉樹

2.二叉樹類型
二叉樹類型：空二叉樹、滿二叉樹、完全二叉樹、完美二叉樹、平衡二叉樹。

空二叉樹：有零個節點
完美二叉樹：每一層節點都是滿的二叉樹（如1中舉例的圖）
滿二叉樹：每一個節點都有零個或者兩個子節點
完全二叉樹：出最後一層外，每一層節點都是滿的，並且最後一層節點全部從左排列
平衡二叉樹：每個節點的兩個子樹的深度相差不超過1.

註：國內對完美二叉樹和滿二叉樹定義相同
3.二叉樹相關術語
術語 解釋
度 節點的度為節點的子樹個數
葉子節點 度為零的節點
分支節點 度不為零的節點
孩子節點 節點下的兩個子節點
雙親節點 節點上一層的源節點
兄弟節點 擁有同一雙親節點的節點
根 二叉樹的源頭節點
深度 二叉樹中節點的層的數量

DLR（先序）：
LDR（中序）：
LRD(後序）：
注意：L代表左子樹R代表右子樹；D代表根

6.深度優先遍歷和廣度優先遍歷
深度優先遍歷：前序、中序和後序都是深度優先遍歷
從根節點出發直奔最遠節點，
廣度優先遍歷：首先訪問舉例根節點最近的節點，按層次遞進，以廣度優先遍歷上圖的順序為：1-2-3-4-5-6-7
三、面試題+勵志
企鵝運維面試題：
1.二叉樹遍歷順序：看上文
2.用你熟悉的語言說說怎麼創建二叉樹？ python看上文

⑹ 用鄰接表表示圖進行深度優先遍歷時，通常採用（）來實現演算法

使用棧來實現演算法。

用鄰接表表示圖進行深度優先遍歷時，通常採用棧來實現演算法，廣度遍歷使用隊列。

擴展材料：

深度優先遍歷：類似與樹的前序遍歷。從圖中的某個頂點v出發，訪問此頂點，然後從v的未被訪問到的鄰接點進行遍歷，直到圖中所有和v有路徑相通的頂點都被訪問到

註：優先訪問外層節點，訪問到無新頂點時，會進行回退，訪問未被訪問過的分支頂點。

廣度優先遍歷：類似於樹的層序遍歷。從圖中的某個頂點w出發，讓頂點w入隊，然後頂點w再出隊，並讓所有和頂點w相連的頂點入隊，然後再出隊一個頂點t，並讓所有和t相連但未被訪問過的頂點入隊……由此循環，指定圖中所有元素都出隊。

參考資料來源：

知網論文-數據結構中圖的遍歷演算法研究