棧實現深度優先遍歷演算法

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

使用棧來實現演算法。

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

擴展材料：

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

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

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

參考資料來源：

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

⑵ 基本演算法——深度優先搜索（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.

⑶ 數據結構問題：圖的深度優先遍歷中有遞歸的應用，要用到棧，圖中頂點是如何出棧進棧的是進棧時訪問還是

首先你得明白函數調用本身就是通過棧來實現的。 調用函數是入棧，而函數返回是出棧。
為什麼是棧， 你要知道棧的特性是 「後進先出」或者是「先進後出」， 而對於函數調用來說， 一定會有最先調用的函數，最後才返回。 舉個例子： 函數a,b,c,d的調用關系是a調用b，b又調用c，c又調用d， 那麼當d函數執行完後，它會返回到c，同時c執行完成後返回到b，最後返回到a。
所以函數調用的順序是a->b->c->d
函數返回的順序是d->c->b->a
很明顯 想要實現這種效果就要依靠棧。
因此函數調用過程是有一個叫做「調用棧」來實現的。
遞歸函數同理，只不過上邊的a,b,c,d全變成同一個函數a->a->a->a，為了人為能區分清楚，不防給a函數加上角標，來標記是第幾層調用a1->a2->a3->a4 ，返回時a4->a3->a2->a1 這就是遞歸函數調用返回過程。
接下來 深度優先搜索（dfs）本身就是靠函數遞歸調用實現的。
對於一個圖來說，是由結點和邊構成的， 在存儲時就需要用到
struct node {
int data;
struct node * next[CNT];
}
上邊只是一種簡單的定義，對一個結點來說主要就是2部分， 一為它所存的數據是什麼（數據域），二為它能指向哪些其它的邊（指針域）。
你問了這樣的問題：這些頂點怎麼進出棧？又是如何訪問的？
這里我要解釋下訪問的意義， 訪問應該是對節點的數據域進行某種操作， 一定要理解這句話，是對數據域進行某種操作， 對於上邊定義的結構 data就是數據域， 我需要對data進行某種操作，比如調用printf輸出data， 這就是一種操作， 而只有對data進行了printf之後才能說「訪問了這個結點」， 否則，單純的使用了節點的指針域不能說訪問了節點。
因此，如何訪問節點的， 什麼時候訪問的，就要由你來定，
如果是下面這樣的寫法：
void dfs(struct node* n)
{
if (n->next[0] == NULL) {
return ;
}
for (int i = 0; n->next[i] != NULL; i++) {
dfs(n->next[i]);

}
printf ("%d\n", n->data);
}
你可以看到，printf是在 dfs函數遞歸調用 「返回」的時候才會被調用，換句話說， 圖中所有節點在從開始走到不能再往下走的一個節點時(某個節點沒有指向其它指點的邊了），返回，同時輸出該節點的data。 這種情況下是「出棧時訪問」
而當printf換到if語句前頭時，則是「入棧時訪問」。
這如同二叉數的三種順序遍歷，前、中、後序遍歷區別在於 何時訪問節點
如下是前序遍歷
void preorder(node* n)
{
printf(n->data);

preorder(n->left);
preorder(n->right);

}
如下是後序遍歷
void afterorder(node* n)
{
afterorder(n->left);
afterorder(n->right);

printf(n->data);
}
如下是中序遍歷
void inorder(node* n)
{
inorder(n->left);
printf(n->data);
inorder(n->right);
}

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

簡述深度優先搜索遍歷的方法？深度優先搜索演算法(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個方向遞歸。