深度優先演算法遍歷
A. 簡述深度優先搜索遍歷的方法。
簡述深度優先搜索遍歷的方法？深度優先搜索演算法(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個方向遞歸。
B. 用鄰接表表示圖進行深度優先遍歷時，通常採用（）來實現演算法
使用棧來實現演算法。
用鄰接表表示圖進行深度優先遍歷時，通常採用棧來實現演算法，廣度遍歷使用隊列。
擴展材料：
深度優先遍歷：類似與樹的前序遍歷。從圖中的某個頂點v出發，訪問此頂點，然後從v的未被訪問到的鄰接點進行遍歷，直到圖中所有和v有路徑相通的頂點都被訪問到
註：優先訪問外層節點，訪問到無新頂點時，會進行回退，訪問未被訪問過的分支頂點。
廣度優先遍歷：類似於樹的層序遍歷。從圖中的某個頂點w出發，讓頂點w入隊，然後頂點w再出隊，並讓所有和頂點w相連的頂點入隊，然後再出隊一個頂點t，並讓所有和t相連但未被訪問過的頂點入隊……由此循環，指定圖中所有元素都出隊。
參考資料來源：
知網論文-數據結構中圖的遍歷演算法研究
C. 深度優先遍歷怎麼修改為廣度優先遍歷
假設初始狀態是圖中所有頂點均未被訪問
從某個頂點出發，然後依次從它的各個未被訪問的鄰接點出發深度優先搜索遍歷圖，直至圖中所有和v有路徑相通的頂點都被訪問到。
若此時尚有其他頂點未被訪問到，則另選一個未被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。
實現深度優先遍歷的關鍵在於回溯。所謂「回溯」，就是自後往前，追溯曾經走過的路徑。
演算法特點
深度優先搜索是一個遞歸的過程。
首先，選定一個出發點後進行遍歷，如果有鄰接的未被訪問過的節點則繼續前進。
若不能繼續前進，則回退一步再前進
若回退一步仍然不能前進，則連續回退至可以前進的位置為止。
重復此過程，直到所有與選定點相通的所有頂點都被遍歷。
深度優先搜索是遞歸過程，帶有回退操作，因此需要使用棧存儲訪問的路徑信息。當訪問到的當前頂點沒有可以前進的鄰接頂點時，需要進行出棧操作，將當前位置回退至出棧元素位置。
圖解過程
無向圖的深度優先遍歷
以下圖所示無向圖說明深度優先搜索遍歷過程。
實例一
在這里插入圖片描述
假設我們從頂點A開始，遍歷過程中的每一步如下：
首先選取頂點A為起始點，輸出A頂點信息，而且將A入棧，並且標記A為已訪問頂點
A的鄰接頂點有C、D、F，從中任意選取一個頂點前進。這里我們選取C為前進位置頂點。輸出C頂點信息，將C入棧，並標記C為已訪問頂點。當前位置指向頂點C
頂點C的鄰接頂點有A、D、B，此時A已經標記為已訪問頂點，因此不能繼續訪問。從B或者D中選取一個頂點前進，這里我們選取B頂點為前進位置頂點。輸出B頂點信息，將B入棧，標記B頂點為已訪問頂點。當前位置指向B
頂點B的鄰接頂點只有C、E，C已被標記，不能繼續訪問，因此選取E為前進位置頂點，輸出E頂點信息，將E入棧，標記E頂點，當前位置指向E。
頂點E的鄰接頂點均已被標記，此時無法繼續前進，則需要進行回退。將當前位置回退至頂點B，回退的同時將E出棧。
頂點B的鄰接頂點也均被標記，需要繼續回退，當前位置回退至C，回退同時將B出棧。
頂點C可以前進的頂點位置為D，則輸出D頂點信息，將D入棧，並標記D頂點。當前位置指向頂點D。
頂點D沒有前進的頂點位置，因此需要回退操作。將當前位置回退至頂點C，回退同時將D出棧。
頂點C沒有前進的頂點位置，繼續回退，將當前位置回退至頂點A，回退同時將C出棧。
頂點A前進的頂點位置為F，輸出F頂點信息，將F入棧，並標記F。將當前位置指向頂點F。
頂點F的前進頂點位置為G，輸出G頂點信息，將G入棧，並標記G。將當前位置指向頂點G。
頂點G沒有前進頂點位置，回退至F。當前位置指向F，回退同時將G出棧。
頂點F沒有前進頂點位置，回退至A，當前位置指向A，回退同時將F出棧。
頂點A沒有前進頂點位置，繼續回退，棧為空，則以A為起始的遍歷結束。若圖中仍有未被訪問的頂點，則選取未訪問的頂點為起始點，繼續執行此過程。直至所有頂點均被訪問。
採用深度優先搜索遍歷順序為A->C->B->E->D->F->G。
利用一個臨時棧來實現回溯，最終遍歷完所有頂點
問題：
（1）必須選取A作為遍歷的起點嗎？
不是原則我們可以選取任何一個節點作為起點進行開始，進行深度優先遍歷
（2）當有多個鄰接點未被訪問時，可以選取哪個作為下一個起點呢？
隨便哪個都行。
當有多個臨界點可選時，相當於走迷宮時出現了多個分叉路口，我們只要不走之前走過的路就行了。所以關鍵在於標記哪個點是否已經走過。不過，一般我們會定義一個原則，必須不碰重復點的情況下，選擇走左/右手第一條沒有走過的路，這樣比較好理解
兩個原則：
右手原則： 在沒有碰到重復頂點的情況下，分叉路口始終是向右手邊走，每路過一個頂點就做一個記號
左手原則： 在沒有碰到重復頂點的情況下，分叉路口始終是向左手邊走，每路過一個頂點就做一個記號
下面以右手原則進行深度優先遍歷再看個例子
實例二
在這里插入圖片描述
原則我們可以選取任何一個節點作為起點進行開始，進行深度優先遍歷，假設我們從頂點A開始，遍歷過程中的每一步如下：
第一步：從頂點A開始，將頂點A標記為已訪問節點
第二步：根據右手原則，訪問頂點B，並將B標記為已訪問節點
第三步：右手原則，訪問頂點C
第四步：右手原則，訪問頂點D
第五步：右手原則，訪問頂點E
第六步：右手原則，訪問頂點F
在這里插入圖片描述
第七步：右手原則，應該先訪問頂點F的鄰接頂點A，但發現A已經被訪問，則訪問A之外的最右側頂點G
在這里插入圖片描述
第八步：右手原則，先訪問頂點B，頂點B已經被訪問；在訪問頂點D，頂點D已經被訪問；最後訪問頂點H
在這里插入圖片描述
第九步：發現頂點H的鄰接頂點均已被訪問，則退回到頂點G;
第十步：頂點G的鄰接頂點均已被訪問，則退回到頂點F；
第十一步：頂點F的鄰接頂點已被訪問，則退回到頂點E；
第十二步：頂點E的鄰接頂點均已被訪問，則退回到頂點D；
第十三步：頂點D的鄰接頂點I尚未被訪問，則訪問頂點I；
在這里插入圖片描述
第十四步：頂點I的鄰接頂點均已被訪問，則退回到頂點D;
第十五步：頂點D的鄰接頂點均已被訪問，退回到頂點C；
第十六步：頂點C的鄰接頂點均已被訪問，則退回到頂點B；
頂點B的鄰接頂點均已被訪問，則退回到頂點A，頂點A為起始頂點，深度優先搜索結束。
圖的深度優先搜索和二叉樹的前序遍歷、中序遍歷、後序遍歷本質上均屬於一類方法。
上面的過程可以總結為以下3個步驟：
首先選定一個未被訪問過的頂點V作為起始頂點（或者訪問指定的起始頂點V），並將其標記為已訪問
然後搜索與頂點V鄰接的所有頂點，判斷這些頂點是否被訪問過，如果有未被訪問過的頂點W；再選取與頂點W鄰接的未被訪問過的一個頂點並進行訪問，依次重復進行。當一個頂點的所有的鄰接頂點都被訪問過時，則依次回退到最近被訪問的頂點。若該頂點還有其他鄰接頂點未被訪問，則從這些未被訪問的頂點中取出一個並重復上述過程，直到與起始頂點V相鄰接的所有頂點都被訪問過為止。
若此時圖中依然有頂點未被訪問，則再選取其中一個頂點作為起始頂點並進行遍歷，轉（2）。反之，則遍歷結束。
有向圖深度優先搜索
在這里插入圖片描述
（1）以頂點A為起始點，輸出A，將A入棧，並標記A為已經訪問。當前位置指向A。
（2）以A為尾的邊只有1條，且邊的頭為頂點B，則前進位置為頂點B，輸出B，將B入棧，標記B。當前位置指向B。
（3）頂點B可以前進的位置有C與F，選取F為前進位置，輸出F，將F入棧，並標記F。當前位置指向F。
（4）頂點F的前進位置為G，輸出G，將G入棧，並標記G。當前位置指向G。
（5）頂點G沒有可以前進的位置，則回退至F，將G出棧。當前位置指向F。
（6）頂點F沒有可以前進的位置，繼續回退至B，將F出棧。當前位置指向B。
（7）頂點B可以前進位置為C和E，選取E，輸出E，將E入棧，並標記E。當前位置指向E。
（8）頂點E的前進位置為D，輸出D，將D入棧，並標記D。當前位置指向D。
（9）頂點D的前進位置為C，輸出C，將C入棧，並標記C。當前位置指向C。
（10）頂點C沒有前進位置，進行回退至D，回退同時將C出棧。
（11）繼續執行此過程，直至棧為空，以A為起始點的遍歷過程結束。若圖中仍有未被訪問的頂點，則選取未訪問的頂點為起始點，繼續執行此過程。直至所有頂點均被訪問。
性能分析
當圖採用鄰接矩陣存儲時，由於矩陣元素個數為n 2 n^2n
2
，因此時間復雜度就是O ( n 2 ) O(n^2)O(n
2
)
當圖採用鄰接表存儲時，鄰接表中只是存儲了邊結點(e條邊，無向圖也只是2e個結點)，加上表頭結點為n（也就是頂點個數），因此時間復雜度為O(n+e)。
廣度優先搜索
演算法思想
思想：
從圖中某頂點v出發，在訪問了v之後依次訪問v的各個未曾訪問過的鄰接點
然後分別從這些鄰接點出發依次訪問它們的鄰接點，並使得「先被訪問的頂點的鄰接點先於後被訪問的頂點的鄰接點被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。
如果此時圖中尚有頂點未被訪問，則需要另選一個未曾被訪問過的頂點作為新的起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。
實現廣度優先遍歷的關鍵在於回放。
回溯與重放是完全相反的過程。
仍然以剛才的圖為例，按照廣度優先遍歷的思想
我們先遍歷頂點0，然後遍歷其鄰接點1、3
接下來我們要遍歷更外圍的頂點，可是如何找到這些更外圍的頂點呢？我們需要把剛才遍歷過的頂點1,3按照順序回顧一遍，從頂點1發現了鄰接點2，從頂點3發現了鄰接點4。於是得到了順序2,4
再把剛才遍歷過的頂點2，4按照順序回顧一遍，分別得到鄰接點5，6
再把剛才遍歷過的頂點5，7按照順序回顧一遍，分別得到鄰接點7，7。7隻需要列印一次，所以我們需要一個東西來標記當前頂點是否已經訪問過
在這里插入圖片描述
像這樣把遍歷過的頂點按照之前的遍歷順序重新回顧，就叫做重放。
同樣的，要實現重放也需要額外的存儲空間，可以利用隊列的先入先出特性來實現。
另外，還需要標記某個點是否已經被訪問過，可以用數組、set等來實現
可以看出，廣度優先搜索它其實就是一種「地毯式」層層推進的搜索策略，即先查找離起始頂點最近的，然後是次近的，依次往外搜索。
演算法特點
廣度優先搜索類似於樹的層次遍歷，是按照一種由近及遠的方式訪問圖的頂點。在進行廣度優先搜索時需要使用隊列存儲頂點信息。
圖解過程
無向圖的廣度優先搜索
在這里插入圖片描述
（1）選取A為起始點，輸出A，A入隊列，標記A，當前位置指向A。
在這里插入圖片描述
（2）隊列頭為A，A出隊列。A的鄰接頂點有B、E，輸出B和E，並將B和E入隊，以及標記B、E為已訪問。當前位置指向B。
在這里插入圖片描述
（3）隊列頭為B，B出隊列。B的鄰接頂點有C、D，輸出C、D，將C、D入隊列，並標記C、D。當前位置指向B。
在這里插入圖片描述
（4）隊列頭為E，E出隊列。E的鄰接頂點有D、F，但是D已經被標記，因此輸出F，將F入隊列，並標記F。當前位置指向E。
在這里插入圖片描述
（5）隊列頭為C，C出隊列。C的鄰接頂點有B、D，但B、D均被標記。無元素入隊列。當前位置指向C。
在這里插入圖片描述
（6）隊列頭為D，D出隊列。D的鄰接頂點有B、C、E，但是B、C、E均被標記，無元素入隊列。當前位置指向D。
在這里插入圖片描述
（7）隊列頭為F，F出隊列。F的鄰接頂點有G、H，輸出G、H，將G、H入隊列，並標記G、H。當前位置指向F。
在這里插入圖片描述
（8）隊列頭為G，G出隊列。G的鄰接頂點有F，但F已被標記，無元素入隊列。當前位置指向G。
在這里插入圖片描述
（9）隊列頭為H，H出隊列。H的鄰接頂點有F，但F已被標記，無元素入隊列。當前位置指向H。
在這里插入圖片描述
（10）隊列空，則以A為起始點的遍歷結束。若圖中仍有未被訪問的頂點，則選取未訪問的頂點為起始點，繼續執行此過程。直至所有頂點均被訪問。
有向圖的廣度優先搜索
在這里插入圖片描述
（1）選取A為起始點，輸出A，將A入隊列，標記A。
在這里插入圖片描述
（2）隊列頭為A，A出隊列。以A為尾的邊有兩條，對應的頭分別為B、C，則A的鄰接頂點有B、C。輸出B、C，將B、C入隊列，並標記B、C。
在這里插入圖片描述
（3）隊列頭為B，B出隊列。B的鄰接頂點為C，C已經被標記，因此無新元素入隊列。
在這里插入圖片描述
（4）隊列頭為C，C出隊列。C的鄰接頂點有E、F。輸出E、F，將E、F入隊列，並標記E、F。
在這里插入圖片描述
（5）列頭為E，E出隊列。E的鄰接頂點有G、H。輸出G、H，將G、H入隊列，並標記G、H。
在這里插入圖片描述
（6）隊列頭為F，F出隊列。F無鄰接頂點
在這里插入圖片描述
（7）隊列頭為G，G出隊列。G無鄰接頂點
在這里插入圖片描述
（8）隊列頭為H，H出隊列。H鄰接頂點為E，但是E已被標記，無新元素入隊列
在這里插入圖片描述
（9）隊列為空，以A為起始點的遍歷過程結束，此時圖中仍有D未被訪問，則以D為起始點繼續遍歷。選取D為起始點，輸出D，將D入隊列，標記D
在這里插入圖片描述
（10）隊列頭為D，D出隊列，D的鄰接頂點為B，B已被標記，無新元素入隊列
在這里插入圖片描述
（11）隊列為空，且所有元素均被訪問，廣度優先搜索遍歷過程結束。廣度優先搜索的輸出序列為：A->B–>C->E->F->G->H->D。
演算法分析
我們來看下，廣度優先搜索的時間、空間復雜度是多少呢？假設圖有V個頂點，E條邊
每個頂點都需要進出一遍隊列，每個邊都會被訪問一次。所以，廣度優先搜索的時間復雜度是O(V+E)。當然，對於一個連通圖來說，也就是說一個圖中的所有頂點都是連通的，，E 肯定要大於等於 V-1，所以，廣度優先搜索的時間復雜度也可以簡寫為 O(E)
廣度優先搜索的空間消耗主要在幾個輔助變數 visited 數組、queue 隊列上。這兩個存儲空間的大小都不會超過頂點的個數，所以空間復雜度是 O(V)。
總結
圖的遍歷主要就是這兩種遍歷思想，深度優先搜索使用遞歸方式，需要棧結構輔助實現。廣度優先搜索需要使用隊列結構輔助實現。在遍歷過程中可以看出，
對於連通圖，從圖的任意一個頂點開始深度或廣度優先遍歷一定可以訪問圖中的所有頂點
對於非連通圖，從圖的任意一個頂點開始深度或廣度優先遍歷並不能訪問圖中的所有頂點。
實現
深度優先遍歷
當圖採用鄰接矩陣進行存儲，遞歸的實現操作：
#define MAXVBA 100
#define INFINITY 65536
typedef struct {
char vexs[MAXVBA];
int arc[MAXVBA][MAXVBA];
int numVertexes, numEdges;
} MGraph;
// 鄰接矩陣的深度有限遞歸演算法
#define TRUE 1
#define FALSE 0
#define MAX 256
typedef int Boolean; // 這里我們定義Boolean為布爾類型，其值為TRUE或FALSE
Boolean visited[MAX]; // 訪問標志的數組
void DFS(MGraph G, int i){
visited[i] = TRUE;
printf("%c", G.vexs[i]);
for (int j = 0; j < G.numVertexes; ++j) {
if (G.arc[i][j] == 1 && !visited[j]){
DFS(G, j); // 對為訪問的鄰接頂點遞歸調用
}
}
}
// 鄰接矩陣的深度遍歷操作
void DFSTraverse(MGraph G){
int i;
// 初始化所有頂點狀態都是未訪問過狀態
for (i = 0; i < G.numVertexes; ++i) {
visited[i] = FALSE;
}
//防止圖為非聯通的情況，遍歷整個圖
for (i = 0; i < G.numVertexes; ++i) {
if (!visited[i]){ // 若是連通圖，只會執行一次
DFS(G, i);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
當圖採用鄰接矩陣進行存儲，棧的實現操作：
void DFS_Stack(MGraph G, int i)
{
int node;
int count = 1;
printf("%c ", G.vexs[i]); // 列印已訪問頂點
visited[i] = TRUE;
node = i;
push(i); //開始的節點入棧
while(count < G.numVertexes) //still has node not visited
{
/* 所有被訪問的節點依次入棧，只有node當找不到下一個相連的節點時，才使用出棧節點 */
for(j=0; j < G.numVertexes; j++)
{
if(G.arc[node][j] == 1 && visited[j] == FALSE)
{
visited[j] = TRUE;
printf("%c ", G.vexs[j]);
count++;
push(j); //push node j
break;
}
}
if(j == G.numVertexes) //與node相連的頂點均已被訪問過，所以需要從stack里取出node的上一個頂點，再看該頂點的鄰接頂點是否未被訪問
node = pop();
else //找到與node相連並且未被訪問的頂點，
node = j;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
請添加圖片描述
鄰接表存儲下圖的深度優先搜索代碼實現，與鄰接矩陣的思想相同，只是實現略有不同：
// 鄰接表的深度有限遞歸演算法
#define TRUE 1
#define FALSE 0
#define MAX 256
typedef int Boolean; // 這里我們定義Boolean為布爾類型，其值為TRUE或FALSE
Boolean visited[MAX]; // 訪問標志的數組
void DFS(GraphAdjList GL, int i)
{
EdgeNode *p;
visited[i] = TRUE;
printf("%c " GL->adjList[i].data);
p = GL->adjList[i].firstEdge;
while(p)
{
if( !visited[p->adjvex] )
{
DFS(GL, p->adjvex);
}
p = p->next;
}
}
// 鄰接表的深度遍歷操作
void DFSTraverse(GraphAdjList GL)
{
int i;
for( i=0; i < GL->numVertexes; i++ )
{
visited[i] = FALSE; // 初始化所有頂點狀態都是未訪問過狀態
}
for( i=0; i < GL->numVertexes; i++ )
{
if( !visited[i] ) // 若是連通圖，只會執行一次
{
DFS(GL, i);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
廣度優先遍歷
請添加圖片描述
// 鄰接矩陣的廣度遍歷演算法
void BFSTraverse(MGraph G)
{
int i, j;
Queue Q;
for( i=0; i < G.numVertexes; i++ )
{
visited[i] = FALSE;
}
initQueue( &Q );
for( i=0; i < G.numVertexes; i++ )
{
if( !visited[i] )
{
printf("%c ", G.vex[i]);
visited[i] = TRUE;
EnQueue(&Q, i);
while( !QueueEmpty(Q) )
{
DeQueue(&Q, &i);
for( j=0; j < G.numVertexes; j++ )
{
if( G.art[i][j]==1 && !visited[j] )
{
printf("%c ", G.vex[j]);
visited[j] = TRUE;
EnQueue(&Q, j);
}
}
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
原文鏈接：https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw%3D%3D&chksm=db828f&idx=1&mid=2653197523&scene=21&sn=#wechat_redirect
D. JS 深度優先遍歷(DFS)和廣度優先遍歷(BFS)
深度優先遍歷DFS
自定義：深度單線遊走，從根走完最後一個節點，在遊走兄弟節點，走完兄弟的所有子節點，循環之。
銀高返 遞歸演算法：
function deepFirstSearch(node, nodeList = []) {
if (node) {
nodeList.push(node);
var children = node.children;
for (var i = 0; i < children.length; i++)
//每次遞歸的時候將 需要遍歷的節點 和 節點所存儲的數組傳下去
deepFirstSearch(children[i], nodeList);
}
return nodeList;
}
非遞歸演算法：
function deepFirstSearch(node) {
var nodes = [];
if (node != null) {
var stack = [];
stack.push(node);
while (stack.length != 0) {
var item = stack.pop();
nodes.push(item);
var children = item.children;
for (var i = children.length - 1; i >= 0; i--)
stack.push(children[i]);
}
}
return nodes;
}
廣度優先遍歷(BFS)
自定義：從根開始 層層推進 走完一層 走下一層 （猶如爬樓，走完一層的樓梯，繼續下一層的樓梯）
遞鋒飢歸演算法：（容易念森棧溢出）
function breadthFirstSearch(node) {
var nodes = [];
var i = 0;
if (!(node == null)) {
nodes.push(node);
breadthFirstSearch(node.nextElementSibling);
node = nodes[i++];
breadthFirstSearch(node.firstElementChild);
}
return nodes;
}
非遞歸演算法：（推薦）
function breadthFirstSearch(node) {
var nodes = [];
if (node != null) {
var queue = [];
queue.unshift(node);
while (queue.length != 0) {
var item = queue.shift();
nodes.push(item);
var children = item.children;
for (var i = 0; i < children.length; i++)
queue.push(children[i]);
}
}
return nodes;
}
E. 採用鄰接表存儲的圖的深度優先遍歷演算法類似於二叉樹的先序遍歷，為什麼是先序呢
這是因為圖的深度優先遍歷演算法先訪問所在結點，再訪問它的鄰接點。與二叉樹的先序遍歷先訪問子樹的根結點，再訪問它的孩子結點（鄰接點）類似。圖的廣度優先遍歷演算法類似於二叉樹的按層次遍歷。
先序遍歷也叫做先根遍歷、前序遍歷，可記做根左右（二叉樹父結點向下先左後右）。
首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹，如果二叉樹為空則返回。
例如，下圖所示二叉樹的遍歷結果是：ABDECF。
(5)深度優先演算法遍歷擴展閱讀：
遍歷種類：
一、NLR：前序遍歷(Preorder
Traversal
亦稱（先序遍歷）），訪問根結點的操作發生在遍歷其左右子樹之前。
二、LNR：中序遍歷(Inorder
Traversal)，訪問根結點的操作發生在遍歷其左右子樹之中（間）。
三、LRN：後序遍歷(Postorder
Traversal)，訪問根結點的操作發生在遍歷其左右子樹之後。
注意：
由於被訪問的結點必是某子樹的根，所以N(Node）、L(Left
subtree）和R(Right
subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為
先根遍歷、中根遍歷和後根遍歷。
參考資料來源：網路-先序遍歷