PHP數(shù)據(jù)結(jié)構(gòu)之圖存儲結(jié)構(gòu)的示例分析

這篇文章主要介紹PHP數(shù)據(jù)結(jié)構(gòu)之圖存儲結(jié)構(gòu)的示例分析，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

圖的存儲結(jié)構(gòu)

圖的概念介紹得差不多了，大家可以消化消化再繼續(xù)學(xué)習(xí)后面的內(nèi)容。如果沒有什么問題的話，我們就繼續(xù)學(xué)習(xí)接下來的內(nèi)容。當(dāng)然，這還不是最麻煩的地方，因為今天我們只是介紹圖的存儲結(jié)構(gòu)而已。

圖的順序存儲結(jié)構(gòu)：鄰接矩陣

什么是鄰接矩陣

首先還是來看看如何用順序結(jié)構(gòu)來存儲圖。不管是棧、隊列、樹，我們都可以使用一個簡單的數(shù)組就可以實現(xiàn)這些數(shù)據(jù)結(jié)構(gòu)的順序存儲能力。但是圖就不一樣了，從上篇文章中，我們學(xué)到過，一個結(jié)點的表示是 <x, y> 這種形式。如果我們把這個結(jié)點相像是一個坐標軸上的點，那么我們是不是就可以用一個二維數(shù)組來表示它呢？沒錯，讓二維數(shù)組的第一維表示為 x 軸，第二維表示為 y 軸，這樣我們就可以構(gòu)建出一張圖來了。沒錯，二維數(shù)組這種形式還有一個別名就叫做：矩陣。

在圖的術(shù)語中，使用二維數(shù)組來表示的圖的順序存儲結(jié)構(gòu)就叫做鄰接矩陣。就像下面這個表格一樣。

在這個表格中，我們有橫豎兩個坐標，X1-4 和 Y1-4 表示這個圖中一共有 4 個結(jié)點，通過它們的對應(yīng)關(guān)系就可以看做是一個結(jié)點與另一個結(jié)點之間是否有邊。比如說 X1 和 Y2 這一對坐標 <X1, Y2> ，它們的值是 1 ，這就說明 結(jié)點1 到 結(jié)點2 之間有一條邊。在這里，我們使用的是無權(quán)圖，也就是用 0 表示沒有邊，用 1 表示兩個結(jié)點之間有邊。同時，它還是一張無向圖，所以 <Y2, X1> 的值也是 1 ，它的意圖是從 結(jié)點2 到 結(jié)點1 之間也有一條邊。如果是有向圖，那么就要根據(jù)有向箭頭的指向來確定這條邊是否設(shè)置為 1 。

上面的這個鄰接矩陣對應(yīng)的圖是什么樣子的呢？大家可以自己嘗試手動畫一畫。畫不出來也不要緊，因為我們才剛開始學(xué)嘛。其實它就是我們最開始展示的那張圖的鄰接矩陣。

左邊的圖就是對應(yīng)的我們上面的那個表格中的鄰接矩陣。那么右邊那個有向圖的鄰接矩陣是什么樣子的呢？我們也寫寫試試。

有意思吧？那么如果是有權(quán)圖呢？其實很簡單的我們將圖中的 1 直接換成對應(yīng)邊的權(quán)值就可以了，不過有可能有的邊的權(quán)值就是 0 ，所以在有權(quán)圖中，我們可以定義一個非常大的數(shù)，或者定義一個非常小的負數(shù)當(dāng)做 無限數(shù) 來表示這兩個結(jié)點沒有邊。

構(gòu)造鄰接矩陣

接下來，我們就通過代碼來構(gòu)造這樣一個鄰接矩陣的存儲結(jié)構(gòu)。我們還是用無向圖的例子來實現(xiàn)。因為無向圖是需要反向的結(jié)點也賦值的，所以它比有向圖多了一個步驟，其它的基本上都是相似的。

// 鄰接矩陣
$graphArr = [];
function CreateGraph($Nv, &$graphArr)
{
    $graphArr = [];
    for ($i = 1; $i <= $Nv; $i++) {
        for ($j = 1; $j <= $Nv; $j++) {
            $graphArr[$i][$j] = 0;
        }
    }
}
// 鄰接矩陣
function BuildGraph(&$graphArr)
{
    echo '請輸入結(jié)點數(shù)：';
    fscanf(STDIN, "%d", $Nv);
    CreateGraph($Nv, $graphArr);
    if ($graphArr) {
        echo '請輸入邊數(shù)：';
        fscanf(STDIN, "%d", $Ne);
        if ($Ne > 0) {
            for ($i = 1; $i <= $Ne; $i++) {
                echo '請輸入邊，格式為 出 入 權(quán)：';
                fscanf(STDIN, "%d %d %d", $v1, $v2, $weight);
                $graphArr[$v1][$v2] = $weight;
                // 如果是無向圖，還需要插入逆向的邊
                $graphArr[$v2][$v1] = $weight;
            }
        }
    }
}

在這段代碼中，首先我們通過 CreateGraph() 方法來初始化一個二維矩陣。也就是根據(jù)我們輸入的結(jié)點數(shù)量，實現(xiàn)一個 X * Y 的二維數(shù)組結(jié)構(gòu)，并且定義它的所有值都是 0 ，也就是說，這個圖目前還沒有邊。

然后，在 BuildGraph() 方法調(diào)用完 CreateGraph() 之后，我們繼續(xù)輸入邊的信息。先輸入邊的數(shù)量，我們有幾條邊，如果邊小于等于 0 的話就不要繼續(xù)創(chuàng)建了。其實還可以嚴謹一點根據(jù) 無向完全圖和有向完全圖 的定義來讓邊不能超過最大的限度。

接下來，我們就循環(huán)繼續(xù)輸入邊的信息，這里我需要的輸入格式是邊的 出結(jié)點 、入結(jié)點 、權(quán)值。由于我們的示例是無向圖，所以我們除了要為 <x, y> 創(chuàng)建邊之外，也要為 <y, x> 創(chuàng)建邊。代碼的注釋中已經(jīng)說明了。

解釋代碼可能還是比較抽象。直接運行一下試試吧。

BuildGraph($graphArr);
// 請輸入結(jié)點數(shù)：4
// 請輸入邊數(shù)：4
// 請輸入邊，格式為 出 入 權(quán)：1 2 1
// 請輸入邊，格式為 出 入 權(quán)：1 3 1
// 請輸入邊，格式為 出 入 權(quán)：1 4 1
// 請輸入邊，格式為 出 入 權(quán)：3 4 1
print_r($graphArr);
// Array
// (
//     [1] => Array
//         (
//             [1] => 0
//             [2] => 1
//             [3] => 1
//             [4] => 1
//         )
//     [2] => Array
//         (
//             [1] => 1
//             [2] => 0
//             [3] => 0
//             [4] => 0
//         )
//     [3] => Array
//         (
//             [1] => 1
//             [2] => 0
//             [3] => 0
//             [4] => 1
//         )
//     [4] => Array
//         (
//             [1] => 1
//             [2] => 0
//             [3] => 1
//             [4] => 0
//         )
// )
//  x
//y 0 1 1 1
//  1 0 0 0
//  1 0 0 1
//  1 0 1 0

在命令行環(huán)境中調(diào)用我們的 PHP 文件，然后根據(jù)提示的內(nèi)容依次輸入相關(guān)的信息。最后打印出來的數(shù)組內(nèi)容是不是就和我們上面的表格中一模一樣了。簡簡單單的一段代碼，我們就實現(xiàn)了圖的順序存儲。

可能有的同學(xué)會一時懵圈。因為我第一眼看到的時候也是完全懵了，不過仔細的對比畫出來的圖和上面的表格其實馬上就能想明白了。這次我們真的是進入二維的世界了。是不是感覺圖瞬間就把樹甩到十萬八千里之外了。完全二叉樹的時候，我們的思想是二維的，但結(jié)構(gòu)還是一維的，而到鄰接矩陣的時候，不管是思想還是代碼結(jié)構(gòu)，全部都進化到了二維空間，高大上真不是吹的。

圖的鏈式存儲結(jié)構(gòu)：鄰接表

說完順序存儲結(jié)構(gòu)，自然不能忽視另一種形式的存儲結(jié)構(gòu)，那就是圖的鏈式存儲結(jié)構(gòu)。其實對于圖來說，鏈式結(jié)構(gòu)非常簡單和清晰，因為我們只需要知道一個結(jié)點和那些結(jié)點有邊就行了。那么我們就讓這個結(jié)點形成一個單鏈表，一路往后鏈接就好了，就像下圖這樣。（同樣以上圖無向圖為例）

從 結(jié)點1 開始，它指向一個后繼是 結(jié)點2 ，然后繼續(xù)向后鏈接 結(jié)點3 和 結(jié)點4 。這樣，與 結(jié)點1 相關(guān)的邊就都描述完成了。由于我們展示的依然是無向圖的鄰接表表示，所以 結(jié)點2 的鏈表結(jié)點指向了 結(jié)點 1 。也就是完成了 <y, x> 的反向指向。

對于代碼實現(xiàn)來說，我們可以將頭結(jié)點，也就是正式的 1-4 結(jié)點保存在一個順序表中。然后讓每個數(shù)組元素的值為第一個結(jié)點的內(nèi)容。這樣，我們就可以讓鏈表結(jié)點只保存結(jié)點名稱、權(quán)重和下一個結(jié)點對象的指向信息就可以了。

// 頭結(jié)點
class AdjList
{
    public $adjList = []; // 頂點列表
    public $Nv = 0; // 結(jié)點數(shù)
    public $Ne = 0; // 邊數(shù)
}
// 邊結(jié)點
class ArcNode
{
    public $adjVex = 0; // 結(jié)點
    public $nextArc = null; // 鏈接指向
    public $weight = 0; // 權(quán)重
}

接下來，我們來看看如何使用鄰接表這種結(jié)構(gòu)來建立圖。

function BuildLinkGraph()
{
    fscanf(STDIN, "請輸入 結(jié)點數(shù) 邊數(shù)：%d %d", $Nv, $Ne);
    if ($Nv > 1) {
        // 初始化頭結(jié)點
        $adj = new AdjList();
        $adj->Nv = $Nv; // 保存下來方便使用
        $adj->Ne = $Ne; // 保存下來方便使用
        // 頭結(jié)點列表
        for ($i = 1; $i <= $Nv; $i++) {
            $adj->adjList[$i] = null; // 全部置為 NULL ，一個無邊空圖
        }
        
        if ($Ne > 0) {
//
            for ($i = 1; $i <= $Ne; $i++) {
                echo '請輸入邊，格式為 出 入 權(quán)：';
                fscanf(STDIN, "%d %d %d", $v1, $v2, $weight);
                // 建立一個結(jié)點
                $p1 = new ArcNode;
                $p1->adjVex = $v2; // 結(jié)點名稱為 入結(jié)點
                $p1->nextArc = $adj->adjList[$v1]; // 下一跳指向 出結(jié)點 的頭結(jié)點
                $p1->weight = $weight; // 設(shè)置權(quán)重
                $adj->adjList[$v1] = $p1; // 讓頭結(jié)點的值等于當(dāng)前新創(chuàng)建的這個結(jié)點
                // 無向圖需要下面的操作，也就是反向的鏈表也要建立
                $p2 = new ArcNode;
                // 注意下面兩行與上面代碼的區(qū)別
                $p2->adjVex = $v1; // 這里是入結(jié)點
                $p2->nextArc = $adj->adjList[$v2]; // 這里是出結(jié)點
                
                $p2->weight = $weight;
                $adj->adjList[$v2] = $p2;
            }
            return $adj;
        }
    }
    return null;
}

代碼中的注釋已經(jīng)寫得很清楚了?？梢钥闯?，在鄰接表的操作中，無向圖也是一樣的比有向圖多一步操作的，如果只是建立有向圖的話，可以不需要 p2 結(jié)點的操作。特別需要注意的就是，在這段代碼中，我們使用的是鏈表操作中的 頭插法 。也就是最后一條數(shù)據(jù)會插入到 頭結(jié)點 上，而最早的那個邊會在鏈表的最后。大家看一下最后建立完成的數(shù)據(jù)結(jié)構(gòu)的輸出就明白了。

print_r(BuildLinkGraph());
// AdjList Object
// (
//     [adjList] => Array
//         (
//             [1] => ArcNode Object
//                 (
//                     [adjVex] => 4
//                     [nextArc] => ArcNode Object
//                         (
//                             [adjVex] => 3
//                             [nextArc] => ArcNode Object
//                                 (
//                                     [adjVex] => 2
//                                     [nextArc] => 
//                                     [weight] => 1
//                                 )
//                             [weight] => 1
//                         )
//                     [weight] => 1
//                 )
//             [2] => ArcNode Object
//                 (
//                     [adjVex] => 1
//                     [nextArc] => 
//                     [weight] => 1
//                 )
//             [3] => ArcNode Object
//                 (
//                     [adjVex] => 4
//                     [nextArc] => ArcNode Object
//                         (
//                             [adjVex] => 1
//                             [nextArc] => 
//                             [weight] => 1
//                         )
//                     [weight] => 1
//                 )
//             [4] => ArcNode Object
//                 (
//                     [adjVex] => 3
//                     [nextArc] => ArcNode Object
//                         (
//                             [adjVex] => 1
//                             [nextArc] => 
//                             [weight] => 1
//                         )
//                     [weight] => 1
//                 )
//         )
//     [Nv] => 4
//     [Ne] => 4
// )

使用鄰接表來建立的圖的鏈式存儲結(jié)構(gòu)是不是反而比鄰接矩陣更加的清晰明了一些。就像樹的鏈式和順序結(jié)構(gòu)一樣，在圖中它們的優(yōu)缺點也是類似的。鄰接矩陣占用的物理空間更多，因為它需要兩層一樣多元素的數(shù)組，就像上面的表格一樣，需要占據(jù) 4 * 4 的物理格子。而鄰接表我們可以直接數(shù)它的結(jié)點數(shù)，只需要 12 個格子就完成了。而且，更主要的是，鏈式的鄰接表可以隨時擴展邊結(jié)點和邊數(shù)，不需要重新地初始化，我們只需要簡單地修改上面的測試代碼就能夠?qū)崿F(xiàn)，而鄰接矩陣如果要修改結(jié)點數(shù)的話，就得要重新初始化整個二維數(shù)組了。

以上是“PHP數(shù)據(jù)結(jié)構(gòu)之圖存儲結(jié)構(gòu)的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道！