PHP數(shù)據(jù)結(jié)構(gòu)中圖遍歷的示例分析

這篇文章將為大家詳細(xì)講解有關(guān)PHP數(shù)據(jù)結(jié)構(gòu)中圖遍歷的示例分析，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

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

樹的遍歷演化到圖的遍歷

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

復(fù)習(xí)完了樹的遍歷方式再學(xué)習(xí)圖的遍歷方式就會(huì)非常簡(jiǎn)單了，因?yàn)樵趫D的遍歷中，最基礎(chǔ)的也是基于棧和隊(duì)列的兩種遍歷形式。只不過(guò)它們的名字略有不同，基于棧的遍歷方式叫作 深度優(yōu)先遍歷 ，而基于隊(duì)列的遍歷方式叫作 廣度優(yōu)先遍歷 。其實(shí)也就是對(duì)應(yīng)著樹中的先、中、后序遍歷和層序遍歷，本質(zhì)上沒有什么太大的區(qū)別。

深度優(yōu)先遍歷

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

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

鄰接矩陣

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

$visited = []; // 已訪問(wèn)結(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)記為已訪問(wèn)
     
    // y 就是鄰接矩陣中的橫行
    for ($y = 1; $y <= count($graphArr); $y++) {
        // 循環(huán)判斷第 [x][y] 個(gè)數(shù)據(jù)是否為 1，也就是是否有邊
        // 并且這個(gè)結(jié)點(diǎn)沒有被訪問(wèn)過(guò)
        if ($graphArr[$x][$y] != 0 && !$visited[$y]) {
            // 進(jìn)行棧遞歸，傳遞的參數(shù)是當(dāng)前這個(gè)結(jié)點(diǎn)
            DFS_AM($graphArr, $y);
        }
    }
}
BuildGraph($graphArr); // 建立鄰接矩陣圖
echo '請(qǐng)輸入開始遍歷的結(jié)點(diǎn)（1-結(jié)點(diǎn)數(shù)）：'; 
fscanf(STDIN, "%d", $startNode); // 輸入從第幾個(gè)結(jié)點(diǎn)開始訪問(wèn)
DFS_AM($graphArr, $startNode); // 開始深度優(yōu)先遍歷

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

接下來(lái)我們進(jìn)行測(cè)試：

# php 5.3圖的遍歷：深度優(yōu)先與廣度優(yōu)先.php
輸入結(jié)點(diǎn)數(shù)：4
請(qǐng)輸入邊數(shù)：3
請(qǐng)輸入邊，格式為 出 入 權(quán)：1 2 1
請(qǐng)輸入邊，格式為 出 入 權(quán)：1 3 1
請(qǐng)輸入邊，格式為 出 入 權(quán)：3 4 1
請(qǐng)輸入開始遍歷的結(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 = [];  // 已訪問(wèn)結(jié)點(diǎn)
function DFS_AL($graph, $x){
    global $visited;
    $p = $graph->adjList[$x]; // 指定結(jié)點(diǎn)的第一個(gè)邊結(jié)點(diǎn)
    echo "節(jié)點(diǎn)：{$x}", PHP_EOL; // 輸出指定結(jié)點(diǎn)的信息
    $visited[$x] = true; // 設(shè)置該結(jié)點(diǎn)已被訪問(wèn)
    while($p != null){
        $y = $p->adjVex; // 獲得邊結(jié)點(diǎn)信息
        if(!$visited[$y]){ // 如果結(jié)點(diǎn)沒有被訪問(wèn)過(guò)
            DFS_AL($graph, $y); // 進(jìn)入這個(gè)邊結(jié)點(diǎn)的深度遍歷過(guò)程
        }
        $p = $p->nextArc; // 移動(dòng)到下一個(gè)邊結(jié)點(diǎn)
    }
}
$graph = BuildLinkGraph();
$graphBFS = $graph;
echo '請(qǐng)輸入開始遍歷的結(jié)點(diǎn)（1-結(jié)點(diǎn)數(shù)）：';
fscanf(STDIN, "%d", $startNode); // 輸入從第幾個(gè)結(jié)點(diǎn)開始訪問(wèn)
DFS_AL($graph, $startNode);// 開始深度優(yōu)先遍歷

是不是也很簡(jiǎn)單，接下來(lái)也是簡(jiǎn)單地測(cè)試一下：

# php 5.3圖的遍歷：深度優(yōu)先與廣度優(yōu)先.php
請(qǐng)輸入 結(jié)點(diǎn)數(shù) 邊數(shù)：
4 3
請(qǐng)輸入邊，格式為 出 入 權(quán)：1 2 1
請(qǐng)輸入邊，格式為 出 入 權(quán)：1 3 1
請(qǐng)輸入邊，格式為 出 入 權(quán)：3 4 1
請(qǐng)輸入開始遍歷的結(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

輸出的順序怎么和鄰接矩陣的不太一樣？我們?cè)谏掀恼轮袑?shí)現(xiàn)的鄰接表使用的是頭插法，后輸入的數(shù)據(jù)添加在結(jié)點(diǎn)鏈接的前面，如果我們將 3 4 1 放在第一個(gè)輸入的話，那么結(jié)點(diǎn)就和鄰接矩陣的遍歷結(jié)果一樣了。

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

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

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

• 首先我們輸入從 結(jié)點(diǎn)3 開始訪問(wèn)，然后開始深度遍歷，這時(shí)輸出 結(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)與其它未訪問(wè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)其它未訪問(wèn)的結(jié)點(diǎn)及邊了，遞歸返回，結(jié)點(diǎn)4 出棧

• 結(jié)點(diǎn)3 循環(huán)完成，遍歷結(jié)束

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

廣度優(yōu)先遍歷

接下來(lái)就是廣度優(yōu)先遍歷了，其實(shí)說(shuō)白了就是我們?cè)趯W(xué)習(xí)樹的遍歷時(shí)候的層序遍歷。前面我們說(shuō)過(guò)，深度遍歷是一條路走到黑，沒路了退回來(lái)。而廣度遍歷則是一層一層的查看，直到找到出口。

鄰接矩陣

使用鄰接矩陣來(lái)進(jìn)行廣度優(yōu)先遍歷的操作，其實(shí)最核心的遍歷方式和深度遍歷沒什么區(qū)別，都是對(duì)某一個(gè)結(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)記為已訪問(wèn)
    EnSqQueue($queue, $x); // 結(jié)點(diǎn)入隊(duì)
    while($x){ // 循環(huán)判斷結(jié)點(diǎn)是否 fasle
        // 遍歷所有結(jié)點(diǎn)是否與這個(gè)結(jié)點(diǎn)有邊
        for ($y = 1; $y <= $graphCount; $y++) {
            // 如果有邊并且未訪問(wèn)過(guò)
            if ($graphArr[$x][$y] != 0 && !$visited[$y]) {
                $visited[$y] = true; // 結(jié)點(diǎn)標(biāo)記為已訪問(wèn)
                EnSqQueue($queue, $y); // 結(jié)點(diǎn)入隊(duì)
            }
        }
        $x = DeSqQueue($queue); // 出隊(duì)一個(gè)結(jié)點(diǎn)
        echo $x, PHP_EOL; // 輸出結(jié)點(diǎn)
    }
}
echo '請(qǐng)輸入開始廣度遍歷的結(jié)點(diǎn)（1-結(jié)點(diǎn)數(shù)）：';
fscanf(STDIN, "%d", $startNode);
BFS_AM($graphArr, $startNode); // 開始廣度遍歷

代碼中的注釋也很清晰明了了，我們直接進(jìn)行測(cè)試：

……
……
請(qǐng)輸入開始廣度遍歷的結(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)記為已訪問(wèn)
    $queue = InitSqQueue();// 初始化隊(duì)列
    EnSqQueue($queue, $x); // 結(jié)點(diǎn)入隊(duì)
    
    // 如果一直有能出隊(duì)的結(jié)點(diǎn)，就一直循環(huán)
    // 也就是說(shuō)，如果隊(duì)列空了，循環(huán)就結(jié)束
    while(($i = DeSqQueue($queue))!==false){
        echo $i, PHP_EOL; // 輸出結(jié)點(diǎn)
        $p = $graph->adjList[$i]; // 結(jié)點(diǎn)的第一個(gè)邊結(jié)點(diǎn)
        while($p != null){ // 如果不為空
            $y = $p->adjVex; // 邊結(jié)點(diǎn)信息
            if(!$visited[$y]){ // 如果沒有訪問(wèn)過(guò)
                $visited[$y] = true; // 標(biāo)記結(jié)點(diǎn)為已訪問(wèn)
                EnSqQueue($queue, $y); // 入隊(duì)結(jié)點(diǎn)
            }
            $p = $p->nextArc; // 結(jié)點(diǎn)指針指向下一個(gè)
        }
    }
}
echo '請(qǐng)輸入開始遍歷的結(jié)點(diǎn)（1-結(jié)點(diǎn)數(shù)）：';
fscanf(STDIN, "%d", $startNode);
BFS_AL($graph, $startNode); // 開始廣度遍歷

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

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

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

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

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

• 輸入 結(jié)點(diǎn)3 開始廣度遍歷，結(jié)點(diǎn)標(biāo)記為已訪問(wèn)，這時(shí) 結(jié)點(diǎn)3 入隊(duì)

• 使用 while 循環(huán)判斷 結(jié)點(diǎn)x 是否為 null ，如果不為 null 進(jìn)入循環(huán)體

• 遍歷所有結(jié)點(diǎn)是否與這個(gè)結(jié)點(diǎn)有邊，如果有邊，并且這個(gè)結(jié)點(diǎn)沒有被訪問(wèn)過(guò)，標(biāo)記已訪問(wèn)，加入隊(duì)列

• 出隊(duì)一個(gè)元素，并賦值給 x

• 輸出 x 結(jié)點(diǎn)的信息

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

關(guān)于“PHP數(shù)據(jù)結(jié)構(gòu)中圖遍歷的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。