【原】PHP數(shù)據(jù)結(jié)構(gòu)-圖的遍歷：深度優(yōu)先與廣度優(yōu)先

硬核項目經(jīng)理 2021-05-31

展開全文

圖的遍歷：深度優(yōu)先與廣度優(yōu)先

在上一篇文章中，我們學習完了圖的相關(guān)的存儲結(jié)構(gòu)，也就是鄰接矩陣和鄰接表。它們分別就代表了最典型的順序存儲和鏈式存儲兩種類型。既然數(shù)據(jù)結(jié)構(gòu)有了，那么我們接下來當然就是學習對這些數(shù)據(jù)結(jié)構(gòu)的操作啦，也就是算法的部分。不管是圖還是樹，遍歷都是很重要的部分，今天我們就先來學習最基礎(chǔ)的兩種圖的遍歷方式。

樹的遍歷演化到圖的遍歷

還記得在樹的學習中，我們講到過先序、中序、后序以及層序遍歷這幾種遍歷形式嗎？其實先序、中序和后序可以看作是一種遍歷方式，它們都是使用棧結(jié)構(gòu)來進行遍歷，特點就是先一條路走到黑，然后再返回來走沒有過的路。而層序遍歷則是使用隊列一層一層地進行遍歷，特點就是先遍歷完子結(jié)點，然后再挨個遍歷每個子結(jié)點的下一層結(jié)點。

復習完了樹的遍歷方式再學習圖的遍歷方式就會非常簡單了，因為在圖的遍歷中，最基礎(chǔ)的也是基于棧和隊列的兩種遍歷形式。只不過它們的名字略有不同，基于棧的遍歷方式叫作深度優(yōu)先遍歷，而基于隊列的遍歷方式叫作廣度優(yōu)先遍歷。其實也就是對應著樹中的先、中、后序遍歷和層序遍歷，本質(zhì)上沒有什么太大的區(qū)別。

深度優(yōu)先遍歷

我們依然還是從棧的遍歷方式入手，也就是圖中的深度優(yōu)先遍歷這種形式。對于棧來說，不斷地將新的結(jié)點壓棧，直到發(fā)現(xiàn)它沒有其它的子結(jié)點后再原路返回，當發(fā)現(xiàn)某個結(jié)點有其它的結(jié)點時再進入子結(jié)點壓棧，這就是深度遍歷的思想。

在這里，需要注意的是我們要記錄一下已經(jīng)訪問過的結(jié)點，當出現(xiàn)多個結(jié)點都有連接到某一個結(jié)點的路徑時，保證這個結(jié)點只訪問過一次。這是和樹結(jié)構(gòu)的最大不同，因為樹是一路向下的，平級結(jié)點之間沒有聯(lián)系，一個結(jié)點只有一個上級結(jié)點。而圖則是任意一個結(jié)點都可以和其它任意的結(jié)點有關(guān)系。

鄰接矩陣

首先，我們看一下鄰接矩陣的深度優(yōu)先遍歷算法的實現(xiàn)?，F(xiàn)在看不懂沒關(guān)系，往下拉去看下圖解，然后結(jié)合著一起看。當然，更好的方案是自己運行起來。

$visited = []; // 已訪問結(jié)點

function DFS_AM($graphArr, $x)
{
    global $visited;
    echo "節(jié)點：{$x}", PHP_EOL;
    $visited[$x] = true; // 當前結(jié)點標記為已訪問
     
    // y 就是鄰接矩陣中的橫行
    for ($y = 1; $y <= count($graphArr); $y++) {
        // 循環(huán)判斷第 [x][y] 個數(shù)據(jù)是否為 1，也就是是否有邊
        // 并且這個結(jié)點沒有被訪問過
        if ($graphArr[$x][$y] != 0 && !$visited[$y]) {
            // 進行棧遞歸，傳遞的參數(shù)是當前這個結(jié)點
            DFS_AM($graphArr, $y);
        }
    }
}

BuildGraph($graphArr); // 建立鄰接矩陣圖

echo '請輸入開始遍歷的結(jié)點（1-結(jié)點數(shù)）：'; 
fscanf(STDIN, "%d", $startNode); // 輸入從第幾個結(jié)點開始訪問
DFS_AM($graphArr, $startNode); // 開始深度優(yōu)先遍歷

代碼量不多吧，使用的就是上篇文章中建立鄰接矩陣的代碼，如果已經(jīng)忘了就回去看看或者直接從文章最下面的鏈接去看源代碼吧。

接下來我們進行測試：

# php 5.3圖的遍歷：深度優(yōu)先與廣度優(yōu)先.php
輸入結(jié)點數(shù)：4
請輸入邊數(shù)：3
請輸入邊，格式為 出 入 權(quán)：1 2 1
請輸入邊，格式為 出 入 權(quán)：1 3 1
請輸入邊，格式為 出 入 權(quán)：3 4 1
請輸入開始遍歷的結(jié)點（1-結(jié)點數(shù)）：3
節(jié)點：3
節(jié)點：1
節(jié)點：2
節(jié)點：4

鄰接表

當然，鄰接表的遍歷思想也是相同的，只是中間的循環(huán)算法使用的是鏈式特點的方式。

$visited = [];  // 已訪問結(jié)點

function DFS_AL($graph, $x){
    global $visited;

    $p = $graph->adjList[$x]; // 指定結(jié)點的第一個邊結(jié)點
    echo "節(jié)點：{$x}", PHP_EOL; // 輸出指定結(jié)點的信息
    $visited[$x] = true; // 設(shè)置該結(jié)點已被訪問

    while($p != null){
        $y = $p->adjVex; // 獲得邊結(jié)點信息
        if(!$visited[$y]){ // 如果結(jié)點沒有被訪問過
            DFS_AL($graph, $y); // 進入這個邊結(jié)點的深度遍歷過程
        }
        $p = $p->nextArc; // 移動到下一個邊結(jié)點
    }

}

$graph = BuildLinkGraph();
$graphBFS = $graph;
echo '請輸入開始遍歷的結(jié)點（1-結(jié)點數(shù)）：';
fscanf(STDIN, "%d", $startNode); // 輸入從第幾個結(jié)點開始訪問
DFS_AL($graph, $startNode);// 開始深度優(yōu)先遍歷

是不是也很簡單，接下來也是簡單地測試一下：

# php 5.3圖的遍歷：深度優(yōu)先與廣度優(yōu)先.php
請輸入 結(jié)點數(shù) 邊數(shù)：
4 3
請輸入邊，格式為 出 入 權(quán)：1 2 1
請輸入邊，格式為 出 入 權(quán)：1 3 1
請輸入邊，格式為 出 入 權(quán)：3 4 1
請輸入開始遍歷的結(jié)點（1-結(jié)點數(shù)）：3
節(jié)點：3
節(jié)點：4
節(jié)點：1
節(jié)點：2

輸出的順序怎么和鄰接矩陣的不太一樣？我們在上篇文章中實現(xiàn)的鄰接表使用的是頭插法，后輸入的數(shù)據(jù)添加在結(jié)點鏈接的前面，如果我們將 3 4 1 放在第一個輸入的話，那么結(jié)點就和鄰接矩陣的遍歷結(jié)果一樣了。

深度優(yōu)先遍歷圖示

直接就上來看了代碼，又講了半天算法，是不是還是一頭霧水？沒關(guān)系，我們直接上圖看看：

左邊是鄰接矩陣的，右邊是鄰接表的。我們測試的圖比較簡單，4 個結(jié)點 3 條邊，下面是復雜一些有 6 個結(jié)點 5 條邊的圖。大家可以自己測試一下。每一步的遍歷和執(zhí)行順序看小黑圓的數(shù)字。下面我們以鄰接矩陣的第一張圖來簡單地講解下訪問的步驟：

首先我們輸入從結(jié)點3 開始訪問，然后開始深度遍歷，這時輸出結(jié)點3
第一步結(jié)點3 的循環(huán)中獲得它和結(jié)點1 有邊，于是遞歸傳入結(jié)點1 ，結(jié)點1 入棧
輸出結(jié)點1，目前的遞歸中結(jié)點1 在棧頂
在結(jié)點1 的循環(huán)中發(fā)現(xiàn) 結(jié)點1 和結(jié)點 2 有邊，于是遞歸傳入結(jié)點2 ，結(jié)點2 入棧
輸出結(jié)點2，目前的遞歸中結(jié)點2 在棧頂
注意了，重點在這里，結(jié)點2 的循環(huán)中沒有發(fā)現(xiàn)與其它未訪問的結(jié)點有邊存在了，于是遞歸開始返回，也就是開始出棧了，依次返回到結(jié)點1 、結(jié)點3，沒有任何輸出，?？樟?，遞歸回到最外層的函數(shù)了
繼續(xù) 結(jié)點3 的循環(huán)，發(fā)現(xiàn)與結(jié)點4 有邊，遞歸傳入結(jié)點4
輸出結(jié)點4，目前的遞歸中結(jié)點4 在棧頂
結(jié)點4 的循環(huán)中沒有發(fā)現(xiàn)其它未訪問的結(jié)點及邊了，遞歸返回，結(jié)點4 出棧
結(jié)點3 循環(huán)完成，遍歷結(jié)束

一步一步的很清晰吧，大家試著自己分析一下下面那個復雜一些圖的深度遍歷順序，看看和我們程序輸出的結(jié)果是不是一樣的。在很多的考研或者數(shù)據(jù)結(jié)構(gòu)考試中，經(jīng)常會有選擇題或應用題讓你手動地來寫出深度優(yōu)先遍歷的順序哦！

廣度優(yōu)先遍歷

接下來就是廣度優(yōu)先遍歷了，其實說白了就是我們在學習樹的遍歷時候的層序遍歷。前面我們說過，深度遍歷是一條路走到黑，沒路了退回來。而廣度遍歷則是一層一層的查看，直到找到出口。

鄰接矩陣

使用鄰接矩陣來進行廣度優(yōu)先遍歷的操作，其實最核心的遍歷方式和深度遍歷沒什么區(qū)別，都是對某一個結(jié)點進行邊的查找，唯一不同的就是把遞歸棧換成了隊列而已。

$visited = [];
function BFS_AM($graphArr, $x){
    global $visited;

    $queue = InitSqQueue(); // 初始化隊列
    $graphCount = count($graphArr); // 獲取矩陣結(jié)點數(shù)量
    $visited[$x] = true; // 結(jié)點標記為已訪問
    EnSqQueue($queue, $x); // 結(jié)點入隊
    while($x){ // 循環(huán)判斷結(jié)點是否 fasle
        // 遍歷所有結(jié)點是否與這個結(jié)點有邊
        for ($y = 1; $y <= $graphCount; $y++) {
            // 如果有邊并且未訪問過
            if ($graphArr[$x][$y] != 0 && !$visited[$y]) {
                $visited[$y] = true; // 結(jié)點標記為已訪問
                EnSqQueue($queue, $y); // 結(jié)點入隊
            }
        }
        $x = DeSqQueue($queue); // 出隊一個結(jié)點
        echo $x, PHP_EOL; // 輸出結(jié)點
    }
}

echo '請輸入開始廣度遍歷的結(jié)點（1-結(jié)點數(shù)）：';
fscanf(STDIN, "%d", $startNode);
BFS_AM($graphArr, $startNode); // 開始廣度遍歷

代碼中的注釋也很清晰明了了，我們直接進行測試：

……
……
請輸入開始廣度遍歷的結(jié)點（1-結(jié)點數(shù)）：3
3
1
4
2

鄰接表

同樣地，我們也提供鄰接表的鏈式廣度優(yōu)先遍歷的核心函數(shù)。

$visited = [];
function BFS_AL($graph, $x){
    global $visited;

    $visited[$x] = true; // 結(jié)點標記為已訪問
    $queue = InitSqQueue();// 初始化隊列
    EnSqQueue($queue, $x); // 結(jié)點入隊
    
    // 如果一直有能出隊的結(jié)點，就一直循環(huán)
    // 也就是說，如果隊列空了，循環(huán)就結(jié)束
    while(($i = DeSqQueue($queue))!==false){
        echo $i, PHP_EOL; // 輸出結(jié)點
        $p = $graph->adjList[$i]; // 結(jié)點的第一個邊結(jié)點
        while($p != null){ // 如果不為空
            $y = $p->adjVex; // 邊結(jié)點信息
            if(!$visited[$y]){ // 如果沒有訪問過
                $visited[$y] = true; // 標記結(jié)點為已訪問
                EnSqQueue($queue, $y); // 入隊結(jié)點
            }
            $p = $p->nextArc; // 結(jié)點指針指向下一個
        }
    }
}

echo '請輸入開始遍歷的結(jié)點（1-結(jié)點數(shù)）：';
fscanf(STDIN, "%d", $startNode);
BFS_AL($graph, $startNode); // 開始廣度遍歷

核心的循環(huán)中的操作其實也和深度遍歷沒什么太大的區(qū)別，同樣是換成了隊列這種存儲形式而已。

……
……
請輸入開始廣度遍歷的結(jié)點（1-結(jié)點數(shù)）：3
3
4
1
2

廣度優(yōu)先遍歷圖示

好吧，上面又羅列完了算法，接下來就是圖示的時間了，相信還是一看圖大家就馬上能明白廣度優(yōu)先遍歷的具體步驟了。

和上面的圖一樣，同樣還是左邊是鄰接矩陣，右邊是鄰接表。在這里，我們依然還是直接分步驟來看一下左邊最上面圖的遍歷操作順序：

輸入結(jié)點3 開始廣度遍歷，結(jié)點標記為已訪問，這時結(jié)點3 入隊
使用 while 循環(huán)判斷結(jié)點x 是否為 null ，如果不為 null 進入循環(huán)體
遍歷所有結(jié)點是否與這個結(jié)點有邊，如果有邊，并且這個結(jié)點沒有被訪問過，標記已訪問，加入隊列
出隊一個元素，并賦值給 x
輸出 x 結(jié)點的信息

廣度優(yōu)先遍歷沒有棧的回溯，就是一條線性的隊列走完就完了，所以圖示會非常清晰。單獨一個結(jié)點我們會將和它相關(guān)的所有結(jié)點入隊，然后出隊最頂上的結(jié)點，這樣就能夠像樹的層序遍歷一樣按照一層一層的順序來遍歷整個圖。同樣地，拿起紙筆，找復雜一點的圖，試試能不能手寫出類似于廣度優(yōu)先遍歷順序的題目吧！

總結(jié)

大家學完了之后是不是發(fā)現(xiàn)今天介紹的深度優(yōu)先和廣度優(yōu)先兩種遍歷方式真的和樹的遍歷方式?jīng)]什么太大的區(qū)別。最大的不同就是我們要標記已訪問過的結(jié)點而已。不管怎么說，使用棧和隊列來對樹或圖進行遍歷是所有樹和圖的操作算法中最最基礎(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)》第二版，嚴蔚敏

《數(shù)據(jù)結(jié)構(gòu)》第二版，陳越

《數(shù)據(jù)結(jié)構(gòu)高分筆記》2020版，天勤考研