圖的遍歷：深度優(yōu)先與廣度優(yōu)先
在上一篇文章中，我們學(xué)習(xí)完了圖的相關(guān)的存儲結(jié)構(gòu)，也就是 鄰接矩陣 和 鄰接表 。它們分別就代表了最典型的 順序存儲 和 鏈?zhǔn)酱鎯?兩種類型。既然數(shù)據(jù)結(jié)構(gòu)有了，那么我們接下來當(dāng)然就是學(xué)習(xí)對這些數(shù)據(jù)結(jié)構(gòu)的操作啦，也就是算法的部分。不管是圖還是樹，遍歷都是很重要的部分，今天我們就先來學(xué)習(xí)最基礎(chǔ)的兩種圖的遍歷方式。
樹的遍歷演化到圖的遍歷
還記得在樹的學(xué)習(xí)中，我們講到過先序、中序、后序以及層序遍歷這幾種遍歷形式嗎？其實(shí)先序、中序和后序可以看作是一種遍歷方式，它們都是使用棧結(jié)構(gòu)來進(jìn)行遍歷，特點(diǎn)就是先一條路走到黑，然后再返回來走沒有過的路。而層序遍歷則是使用隊(duì)列一層一層地進(jìn)行遍歷，特點(diǎn)就是先遍歷完子結(jié)點(diǎn)，然后再挨個遍歷每個子結(jié)點(diǎn)的下一層結(jié)點(diǎn)。
復(fù)習(xí)完了樹的遍歷方式再學(xué)習(xí)圖的遍歷方式就會非常簡單了，因?yàn)樵趫D的遍歷中，最基礎(chǔ)的也是基于棧和隊(duì)列的兩種遍歷形式。只不過它們的名字略有不同，基于棧的遍歷方式叫作 深度優(yōu)先遍歷 ，而基于隊(duì)列的遍歷方式叫作 廣度優(yōu)先遍歷 。其實(shí)也就是對應(yīng)著樹中的先、中、后序遍歷和層序遍歷，本質(zhì)上沒有什么太大的區(qū)別。
深度優(yōu)先遍歷
我們依然還是從棧的遍歷方式入手，也就是圖中的 深度優(yōu)先遍歷 這種形式。對于棧來說，不斷地將新的結(jié)點(diǎn)壓棧，直到發(fā)現(xiàn)它沒有其它的子結(jié)點(diǎn)后再原路返回，當(dāng)發(fā)現(xiàn)某個結(jié)點(diǎn)有其它的結(jié)點(diǎn)時再進(jìn)入子結(jié)點(diǎn)壓棧，這就是深度遍歷的思想。
在這里，需要注意的是我們要記錄一下已經(jīng)訪問過的結(jié)點(diǎn)，當(dāng)出現(xiàn)多個結(jié)點(diǎn)都有連接到某一個結(jié)點(diǎn)的路徑時，保證這個結(jié)點(diǎn)只訪問過一次。這是和樹結(jié)構(gòu)的最大不同，因?yàn)闃涫且宦废蛳碌?，平級結(jié)點(diǎn)之間沒有聯(lián)系，一個結(jié)點(diǎn)只有一個上級結(jié)點(diǎn)。而圖則是任意一個結(jié)點(diǎn)都可以和其它任意的結(jié)點(diǎn)有關(guān)系。
鄰接矩陣
首先，我們看一下鄰接矩陣的深度優(yōu)先遍歷算法的實(shí)現(xiàn)?，F(xiàn)在看不懂沒關(guān)系，往下拉去看下圖解，然后結(jié)合著一起看。當(dāng)然，更好的方案是自己運(yùn)行起來。
$visited = []; // 已訪問結(jié)點(diǎn)
function DFS_AM($graphArr, $x)
{
global $visited;
echo "節(jié)點(diǎn)：{$x}", PHP_EOL;
$visited[$x] = true; // 當(dāng)前結(jié)點(diǎn)標(biāo)記為已訪問
// y 就是鄰接矩陣中的橫行
for ($y = 1; $y <= count($graphArr); $y++) {
// 循環(huán)判斷第 [x][y] 個數(shù)據(jù)是否為 1，也就是是否有邊
// 并且這個結(jié)點(diǎn)沒有被訪問過
if ($graphArr[$x][$y] != 0 && !$visited[$y]) {
// 進(jìn)行棧遞歸，傳遞的參數(shù)是當(dāng)前這個結(jié)點(diǎn)
DFS_AM($graphArr, $y);
}
}
}
BuildGraph($graphArr); // 建立鄰接矩陣圖
echo '請輸入開始遍歷的結(jié)點(diǎn)（1-結(jié)點(diǎn)數(shù)）：';
fscanf(STDIN, "%d", $startNode); // 輸入從第幾個結(jié)點(diǎn)開始訪問
DFS_AM($graphArr, $startNode); // 開始深度優(yōu)先遍歷
代碼量不多吧，使用的就是上篇文章中建立鄰接矩陣的代碼，如果已經(jīng)忘了就回去看看或者直接從文章最下面的鏈接去看源代碼吧。
接下來我們進(jìn)行測試：
# php 5.3圖的遍歷：深度優(yōu)先與廣度優(yōu)先.php
輸入結(jié)點(diǎn)數(shù)：4
請輸入邊數(shù)：3
請輸入邊，格式為 出 入 權(quán)：1 2 1
請輸入邊，格式為 出 入 權(quán)：1 3 1
請輸入邊，格式為 出 入 權(quán)：3 4 1
請輸入開始遍歷的結(jié)點(diǎn)（1-結(jié)點(diǎn)數(shù)）：3
節(jié)點(diǎn)：3
節(jié)點(diǎn)：1
節(jié)點(diǎn)：2
節(jié)點(diǎn)：4
鄰接表
當(dāng)然，鄰接表的遍歷思想也是相同的，只是中間的循環(huán)算法使用的是鏈?zhǔn)教攸c(diǎn)的方式。
$visited = []; // 已訪問結(jié)點(diǎn)
function DFS_AL($graph, $x){
global $visited;
$p = $graph->adjList[$x]; // 指定結(jié)點(diǎn)的第一個邊結(jié)點(diǎn)
echo "節(jié)點(diǎn)：{$x}", PHP_EOL; // 輸出指定結(jié)點(diǎn)的信息
$visited[$x] = true; // 設(shè)置該結(jié)點(diǎn)已被訪問
while($p != null){
$y = $p->adjVex; // 獲得邊結(jié)點(diǎn)信息
if(!$visited[$y]){ // 如果結(jié)點(diǎn)沒有被訪問過
DFS_AL($graph, $y); // 進(jìn)入這個邊結(jié)點(diǎn)的深度遍歷過程
}
$p = $p->nextArc; // 移動到下一個邊結(jié)點(diǎn)
}
}
$graph = BuildLinkGraph();
$graphBFS = $graph;
echo '請輸入開始遍歷的結(jié)點(diǎn)（1-結(jié)點(diǎn)數(shù)）：';
fscanf(STDIN, "%d", $startNode); // 輸入從第幾個結(jié)點(diǎn)開始訪問
DFS_AL($graph, $startNode);// 開始深度優(yōu)先遍歷
是不是也很簡單，接下來也是簡單地測試一下：
# php 5.3圖的遍歷：深度優(yōu)先與廣度優(yōu)先.php
請輸入 結(jié)點(diǎn)數(shù) 邊數(shù)：
4 3
請輸入邊，格式為 出 入 權(quán)：1 2 1
請輸入邊，格式為 出 入 權(quán)：1 3 1
請輸入邊，格式為 出 入 權(quán)：3 4 1
請輸入開始遍歷的結(jié)點(diǎn)（1-結(jié)點(diǎn)數(shù)）：3
節(jié)點(diǎn)：3
節(jié)點(diǎn)：4
節(jié)點(diǎn)：1
節(jié)點(diǎn)：2
輸出的順序怎么和鄰接矩陣的不太一樣？我們在上篇文章中實(shí)現(xiàn)的鄰接表使用的是頭插法，后輸入的數(shù)據(jù)添加在結(jié)點(diǎn)鏈接的前面，如果我們將 3 4 1 放在第一個輸入的話，那么結(jié)點(diǎn)就和鄰接矩陣的遍歷結(jié)果一樣了。
深度優(yōu)先遍歷圖示
直接就上來看了代碼，又講了半天算法，是不是還是一頭霧水？沒關(guān)系，我們直接上圖看看：
左邊是鄰接矩陣的，右邊是鄰接表的。我們測試的圖比較簡單，4 個結(jié)點(diǎn) 3 條邊，下面是復(fù)雜一些有 6 個結(jié)點(diǎn) 5 條邊的圖。大家可以自己測試一下。每一步的遍歷和執(zhí)行順序看小黑圓的數(shù)字。下面我們以鄰接矩陣的第一張圖來簡單地講解下訪問的步驟：
首先我們輸入從 結(jié)點(diǎn)3 開始訪問，然后開始深度遍歷，這時輸出 結(jié)點(diǎn)3
第一步 結(jié)點(diǎn)3 的循環(huán)中獲得它和 結(jié)點(diǎn)1 有邊，于是遞歸傳入 結(jié)點(diǎn)1 ，結(jié)點(diǎn)1 入棧
輸出 結(jié)點(diǎn)1，目前的遞歸中 結(jié)點(diǎn)1 在棧頂
在 結(jié)點(diǎn)1 的循環(huán)中發(fā)現(xiàn) 結(jié)點(diǎn)1 和 結(jié)點(diǎn) 2 有邊，于是遞歸傳入 結(jié)點(diǎn)2 ，結(jié)點(diǎn)2 入棧
輸出 結(jié)點(diǎn)2，目前的遞歸中 結(jié)點(diǎn)2 在棧頂
注意了，重點(diǎn)在這里，結(jié)點(diǎn)2 的循環(huán)中沒有發(fā)現(xiàn)與其它未訪問的結(jié)點(diǎn)有邊存在了，于是遞歸開始返回，也就是開始出棧了，依次返回到 結(jié)點(diǎn)1 、結(jié)點(diǎn)3，沒有任何輸出，?？樟耍f歸回到最外層的函數(shù)了
繼續(xù) 結(jié)點(diǎn)3 的循環(huán)，發(fā)現(xiàn)與 結(jié)點(diǎn)4 有邊，遞歸傳入 結(jié)點(diǎn)4
輸出 結(jié)點(diǎn)4，目前的遞歸中 結(jié)點(diǎn)4 在棧頂
結(jié)點(diǎn)4 的循環(huán)中沒有發(fā)現(xiàn)其它未訪問的結(jié)點(diǎn)及邊了，遞歸返回，結(jié)點(diǎn)4 出棧
結(jié)點(diǎn)3 循環(huán)完成，遍歷結(jié)束
一步一步的很清晰吧，大家試著自己分析一下下面那個復(fù)雜一些圖的深度遍歷順序，看看和我們程序輸出的結(jié)果是不是一樣的。在很多的考研或者數(shù)據(jù)結(jié)構(gòu)考試中，經(jīng)常會有選擇題或應(yīng)用題讓你手動地來寫出深度優(yōu)先遍歷的順序哦！
廣度優(yōu)先遍歷
接下來就是廣度優(yōu)先遍歷了，其實(shí)說白了就是我們在學(xué)習(xí)樹的遍歷時候的層序遍歷。前面我們說過，深度遍歷是一條路走到黑，沒路了退回來。而廣度遍歷則是一層一層的查看，直到找到出口。
鄰接矩陣
使用鄰接矩陣來進(jìn)行廣度優(yōu)先遍歷的操作，其實(shí)最核心的遍歷方式和深度遍歷沒什么區(qū)別，都是對某一個結(jié)點(diǎn)進(jìn)行邊的查找，唯一不同的就是把遞歸棧換成了隊(duì)列而已。
$visited = [];
function BFS_AM($graphArr, $x){
global $visited;
$queue = InitSqQueue(); // 初始化隊(duì)列
$graphCount = count($graphArr); // 獲取矩陣結(jié)點(diǎn)數(shù)量
$visited[$x] = true; // 結(jié)點(diǎn)標(biāo)記為已訪問
EnSqQueue($queue, $x); // 結(jié)點(diǎn)入隊(duì)
while($x){ // 循環(huán)判斷結(jié)點(diǎn)是否 fasle
// 遍歷所有結(jié)點(diǎn)是否與這個結(jié)點(diǎn)有邊
for ($y = 1; $y <= $graphCount; $y++) {
// 如果有邊并且未訪問過
if ($graphArr[$x][$y] != 0 && !$visited[$y]) {
$visited[$y] = true; // 結(jié)點(diǎn)標(biāo)記為已訪問
EnSqQueue($queue, $y); // 結(jié)點(diǎn)入隊(duì)
}
}
$x = DeSqQueue($queue); // 出隊(duì)一個結(jié)點(diǎn)
echo $x, PHP_EOL; // 輸出結(jié)點(diǎn)
}
}
echo '請輸入開始廣度遍歷的結(jié)點(diǎn)（1-結(jié)點(diǎn)數(shù)）：';
fscanf(STDIN, "%d", $startNode);
BFS_AM($graphArr, $startNode); // 開始廣度遍歷
代碼中的注釋也很清晰明了了，我們直接進(jìn)行測試：
……
……
請輸入開始廣度遍歷的結(jié)點(diǎn)（1-結(jié)點(diǎn)數(shù)）：3
3
1
4
2
鄰接表
同樣地，我們也提供鄰接表的鏈?zhǔn)綇V度優(yōu)先遍歷的核心函數(shù)。
$visited = [];
function BFS_AL($graph, $x){
global $visited;
$visited[$x] = true; // 結(jié)點(diǎn)標(biāo)記為已訪問
$queue = InitSqQueue();// 初始化隊(duì)列
EnSqQueue($queue, $x); // 結(jié)點(diǎn)入隊(duì)
// 如果一直有能出隊(duì)的結(jié)點(diǎn)，就一直循環(huán)
// 也就是說，如果隊(duì)列空了，循環(huán)就結(jié)束
while(($i = DeSqQueue($queue))!==false){
echo $i, PHP_EOL; // 輸出結(jié)點(diǎn)
$p = $graph->adjList[$i]; // 結(jié)點(diǎn)的第一個邊結(jié)點(diǎn)
while($p != null){ // 如果不為空
$y = $p->adjVex; // 邊結(jié)點(diǎn)信息
if(!$visited[$y]){ // 如果沒有訪問過
$visited[$y] = true; // 標(biāo)記結(jié)點(diǎn)為已訪問
EnSqQueue($queue, $y); // 入隊(duì)結(jié)點(diǎn)
}
$p = $p->nextArc; // 結(jié)點(diǎn)指針指向下一個
}
}
}
echo '請輸入開始遍歷的結(jié)點(diǎn)（1-結(jié)點(diǎn)數(shù)）：';
fscanf(STDIN, "%d", $startNode);
BFS_AL($graph, $startNode); // 開始廣度遍歷
核心的循環(huán)中的操作其實(shí)也和深度遍歷沒什么太大的區(qū)別，同樣是換成了隊(duì)列這種存儲形式而已。
……
……
請輸入開始廣度遍歷的結(jié)點(diǎn)（1-結(jié)點(diǎn)數(shù)）：3
3
4
1
2
廣度優(yōu)先遍歷圖示
好吧，上面又羅列完了算法，接下來就是圖示的時間了，相信還是一看圖大家就馬上能明白廣度優(yōu)先遍歷的具體步驟了。
和上面的圖一樣，同樣還是左邊是鄰接矩陣，右邊是鄰接表。在這里，我們依然還是直接分步驟來看一下左邊最上面圖的遍歷操作順序：
輸入 結(jié)點(diǎn)3 開始廣度遍歷，結(jié)點(diǎn)標(biāo)記為已訪問，這時 結(jié)點(diǎn)3 入隊(duì)
使用 while 循環(huán)判斷 結(jié)點(diǎn)x 是否為 null ，如果不為 null 進(jìn)入循環(huán)體
遍歷所有結(jié)點(diǎn)是否與這個結(jié)點(diǎn)有邊，如果有邊，并且這個結(jié)點(diǎn)沒有被訪問過，標(biāo)記已訪問，加入隊(duì)列
廣度優(yōu)先遍歷沒有棧的回溯，就是一條線性的隊(duì)列走完就完了，所以圖示會非常清晰。單獨(dú)一個結(jié)點(diǎn)我們會將和它相關(guān)的所有結(jié)點(diǎn)入隊(duì)，然后出隊(duì)最頂上的結(jié)點(diǎn)，這樣就能夠像樹的層序遍歷一樣按照一層一層的順序來遍歷整個圖。同樣地，拿起紙筆，找復(fù)雜一點(diǎn)的圖，試試能不能手寫出類似于廣度優(yōu)先遍歷順序的題目吧！
總結(jié)
大家學(xué)完了之后是不是發(fā)現(xiàn)今天介紹的深度優(yōu)先和廣度優(yōu)先兩種遍歷方式真的和樹的遍歷方式?jīng)]什么太大的區(qū)別。最大的不同就是我們要標(biāo)記已訪問過的結(jié)點(diǎn)而已。不管怎么說，使用棧和隊(duì)列來對樹或圖進(jìn)行遍歷是所有樹和圖的操作算法中最最基礎(chǔ)的部分，也是考試和面試中最常見的問題，大家一定要深入理解掌握哦！
測試代碼：
https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/5.圖/source/5.3圖的遍歷：深度優(yōu)先與廣度優(yōu)先.php
參考文檔：
《數(shù)據(jù)結(jié)構(gòu)》第二版，嚴(yán)蔚敏
《數(shù)據(jù)結(jié)構(gòu)》第二版，陳越
《數(shù)據(jù)結(jié)構(gòu)高分筆記》2020版，天勤考研
