溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹PHP數據結構之圖存儲結構的示例分析，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！
圖的存儲結構
圖的概念介紹得差不多了，大家可以消化消化再繼續學習后面的內容。如果沒有什么問題的話，我們就繼續學習接下來的內容。當然，這還不是最麻煩的地方，因為今天我們只是介紹圖的存儲結構而已。
圖的順序存儲結構：鄰接矩陣
什么是鄰接矩陣
首先還是來看看如何用順序結構來存儲圖。不管是棧、隊列、樹，我們都可以使用一個簡單的數組就可以實現這些數據結構的順序存儲能力。但是圖就不一樣了，從上篇文章中，我們學到過，一個結點的表示是 <x, y> 這種形式。如果我們把這個結點相像是一個坐標軸上的點，那么我們是不是就可以用一個二維數組來表示它呢？沒錯，讓二維數組的第一維表示為 x 軸，第二維表示為 y 軸，這樣我們就可以構建出一張圖來了。沒錯，二維數組這種形式還有一個別名就叫做：矩陣。
在圖的術語中，使用二維數組來表示的圖的順序存儲結構就叫做鄰接矩陣。就像下面這個表格一樣。
在這個表格中，我們有橫豎兩個坐標，X1-4 和 Y1-4 表示這個圖中一共有 4 個結點，通過它們的對應關系就可以看做是一個結點與另一個結點之間是否有邊。比如說 X1 和 Y2 這一對坐標 <X1, Y2> ，它們的值是 1 ，這就說明 結點1 到 結點2 之間有一條邊。在這里，我們使用的是無權圖，也就是用 0 表示沒有邊，用 1 表示兩個結點之間有邊。同時，它還是一張無向圖，所以 <Y2, X1> 的值也是 1 ，它的意圖是從 結點2 到 結點1 之間也有一條邊。如果是有向圖，那么就要根據有向箭頭的指向來確定這條邊是否設置為 1 。
上面的這個鄰接矩陣對應的圖是什么樣子的呢？大家可以自己嘗試手動畫一畫。畫不出來也不要緊，因為我們才剛開始學嘛。其實它就是我們最開始展示的那張圖的鄰接矩陣。
左邊的圖就是對應的我們上面的那個表格中的鄰接矩陣。那么右邊那個有向圖的鄰接矩陣是什么樣子的呢？我們也寫寫試試。
有意思吧？那么如果是有權圖呢？其實很簡單的我們將圖中的 1 直接換成對應邊的權值就可以了，不過有可能有的邊的權值就是 0 ，所以在有權圖中，我們可以定義一個非常大的數，或者定義一個非常小的負數當做 無限數 來表示這兩個結點沒有邊。
構造鄰接矩陣
接下來，我們就通過代碼來構造這樣一個鄰接矩陣的存儲結構。我們還是用無向圖的例子來實現。因為無向圖是需要反向的結點也賦值的，所以它比有向圖多了一個步驟，其它的基本上都是相似的。
// 鄰接矩陣
$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 '請輸入結點數：';
fscanf(STDIN, "%d", $Nv);
CreateGraph($Nv, $graphArr);
if ($graphArr) {
echo '請輸入邊數：';
fscanf(STDIN, "%d", $Ne);
if ($Ne > 0) {
for ($i = 1; $i <= $Ne; $i++) {
echo '請輸入邊，格式為 出 入 權：';
fscanf(STDIN, "%d %d %d", $v1, $v2, $weight);
$graphArr[$v1][$v2] = $weight;
// 如果是無向圖，還需要插入逆向的邊
$graphArr[$v2][$v1] = $weight;
}
}
}
}在這段代碼中，首先我們通過 CreateGraph() 方法來初始化一個二維矩陣。也就是根據我們輸入的結點數量，實現一個 X * Y 的二維數組結構，并且定義它的所有值都是 0 ，也就是說，這個圖目前還沒有邊。
然后，在 BuildGraph() 方法調用完 CreateGraph() 之后，我們繼續輸入邊的信息。先輸入邊的數量，我們有幾條邊，如果邊小于等于 0 的話就不要繼續創建了。其實還可以嚴謹一點根據 無向完全圖和有向完全圖 的定義來讓邊不能超過最大的限度。
接下來，我們就循環繼續輸入邊的信息，這里我需要的輸入格式是邊的 出結點 、入結點 、權值。由于我們的示例是無向圖，所以我們除了要為 <x, y> 創建邊之外，也要為 <y, x> 創建邊。代碼的注釋中已經說明了。
解釋代碼可能還是比較抽象。直接運行一下試試吧。
BuildGraph($graphArr); // 請輸入結點數：4 // 請輸入邊數：4 // 請輸入邊，格式為 出 入 權：1 2 1 // 請輸入邊，格式為 出 入 權：1 3 1 // 請輸入邊，格式為 出 入 權：1 4 1 // 請輸入邊，格式為 出 入 權：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
在命令行環境中調用我們的 PHP 文件，然后根據提示的內容依次輸入相關的信息。最后打印出來的數組內容是不是就和我們上面的表格中一模一樣了。簡簡單單的一段代碼，我們就實現了圖的順序存儲。
可能有的同學會一時懵圈。因為我第一眼看到的時候也是完全懵了，不過仔細的對比畫出來的圖和上面的表格其實馬上就能想明白了。這次我們真的是進入二維的世界了。是不是感覺圖瞬間就把樹甩到十萬八千里之外了。完全二叉樹的時候，我們的思想是二維的，但結構還是一維的，而到鄰接矩陣的時候，不管是思想還是代碼結構，全部都進化到了二維空間，高大上真不是吹的。
圖的鏈式存儲結構：鄰接表
說完順序存儲結構，自然不能忽視另一種形式的存儲結構，那就是圖的鏈式存儲結構。其實對于圖來說，鏈式結構非常簡單和清晰，因為我們只需要知道一個結點和那些結點有邊就行了。那么我們就讓這個結點形成一個單鏈表，一路往后鏈接就好了，就像下圖這樣。（同樣以上圖無向圖為例）
從 結點1 開始，它指向一個后繼是 結點2 ，然后繼續向后鏈接 結點3 和 結點4 。這樣，與 結點1 相關的邊就都描述完成了。由于我們展示的依然是無向圖的鄰接表表示，所以 結點2 的鏈表結點指向了 結點 1 。也就是完成了 <y, x> 的反向指向。
對于代碼實現來說，我們可以將頭結點，也就是正式的 1-4 結點保存在一個順序表中。然后讓每個數組元素的值為第一個結點的內容。這樣，我們就可以讓鏈表結點只保存結點名稱、權重和下一個結點對象的指向信息就可以了。
// 頭結點
class AdjList
{
public $adjList = []; // 頂點列表
public $Nv = 0; // 結點數
public $Ne = 0; // 邊數
}
// 邊結點
class ArcNode
{
public $adjVex = 0; // 結點
public $nextArc = null; // 鏈接指向
public $weight = 0; // 權重
}
接下來，我們來看看如何使用鄰接表這種結構來建立圖。
function BuildLinkGraph()
{
fscanf(STDIN, "請輸入 結點數 邊數：%d %d", $Nv, $Ne);
if ($Nv > 1) {
// 初始化頭結點
$adj = new AdjList();
$adj->Nv = $Nv; // 保存下來方便使用
$adj->Ne = $Ne; // 保存下來方便使用
// 頭結點列表
for ($i = 1; $i <= $Nv; $i++) {
$adj->adjList[$i] = null; // 全部置為 NULL ，一個無邊空圖
}
if ($Ne > 0) {
//
for ($i = 1; $i <= $Ne; $i++) {
echo '請輸入邊，格式為 出 入 權：';
fscanf(STDIN, "%d %d %d", $v1, $v2, $weight);
// 建立一個結點
$p1 = new ArcNode;
$p1->adjVex = $v2; // 結點名稱為 入結點
$p1->nextArc = $adj->adjList[$v1]; // 下一跳指向 出結點 的頭結點
$p1->weight = $weight; // 設置權重
$adj->adjList[$v1] = $p1; // 讓頭結點的值等于當前新創建的這個結點
// 無向圖需要下面的操作，也就是反向的鏈表也要建立
$p2 = new ArcNode;
// 注意下面兩行與上面代碼的區別
$p2->adjVex = $v1; // 這里是入結點
$p2->nextArc = $adj->adjList[$v2]; // 這里是出結點
$p2->weight = $weight;
$adj->adjList[$v2] = $p2;
}
return $adj;
}
}
return null;
}代碼中的注釋已經寫得很清楚了。可以看出，在鄰接表的操作中，無向圖也是一樣的比有向圖多一步操作的，如果只是建立有向圖的話，可以不需要 p2 結點的操作。特別需要注意的就是，在這段代碼中，我們使用的是鏈表操作中的 頭插法 。也就是最后一條數據會插入到 頭結點 上，而最早的那個邊會在鏈表的最后。大家看一下最后建立完成的數據結構的輸出就明白了。
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 // )
使用鄰接表來建立的圖的鏈式存儲結構是不是反而比鄰接矩陣更加的清晰明了一些。就像樹的鏈式和順序結構一樣，在圖中它們的優缺點也是類似的。鄰接矩陣占用的物理空間更多，因為它需要兩層一樣多元素的數組，就像上面的表格一樣，需要占據 4 * 4 的物理格子。而鄰接表我們可以直接數它的結點數，只需要 12 個格子就完成了。而且，更主要的是，鏈式的鄰接表可以隨時擴展邊結點和邊數，不需要重新地初始化，我們只需要簡單地修改上面的測試代碼就能夠實現，而鄰接矩陣如果要修改結點數的話，就得要重新初始化整個二維數組了。
以上是“PHP數據結構之圖存儲結構的示例分析”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
