圖解圖的存儲結構

圖解圖的存儲結構

4 人贊了文章

剛開始接觸圖形結構的時候，覺得它很燒腦子，因為像線性表它僅有線性關係，樹形結構有清晰度的層次結構，但是對於圖形結構來說集合中的每一個元素都有可能有關係。所以在剛接觸圖形結構的時候，對於如何實現圖形結構往往感到很困惑,後來發現我們其實只要弄清楚了圖的存儲結構那麼用代碼實現起來並不困難。

要清楚地理解圖的存儲結構，首先要明白圖的存儲結構里要存儲些什麼東西。要存儲圖形結構的信息，無非就是存儲圖的頂點（vector）和圖的邊（edge）。

下面給出兩張圖，以此來介紹圖型結構的四種存儲結構。注意（無向圖和有向圖的存儲結構是有區別的，應當體會其中的區別）

G1（有向圖）

如圖所示G1有四個頂點（Vector）,四條有向邊（Edge）

G2(無向圖)

G2有五個頂點，六條邊。

一，數組存儲

數組表示法，應當是圖的存儲結構中最簡單的，利用兩個數組分別存儲頂點（vector）和邊（edge）。

1、我們先只考慮圖頂點（vector）的信息：先利用一個數組把圖頂點存儲起來。

對於G1,它的頂點用數組存儲：

對於G2，它的頂點用數組存儲：

2、再來考慮圖的邊（edge），因為一條邊連接兩個頂點，為了描述這個關係，再利用一個二維數組來存儲圖的邊。把二維數組看做一個矩陣。

對於有向圖G1，它的邊用二維數組存儲：

其中E[i][j]為1表示，從頂點v[i]到頂點v[j]有邊（這是有方向的）。

對於無向圖G2,它的邊也可以用二維數組來表示：

其中E[i][j]為1表示頂點V[i]與V[j]之間有邊（沒有方向），注意：這和有向圖是不一樣的，大家可以看到無向圖的二維數組是關於對角線對稱的。

這樣通過一維數組來保存頂點數據信息，二維數組來表示兩兩頂點之間的邊。就完成了對圖形數據結構的存儲。下面的三種方法其實也是利用數組和鏈表來對圖形數據結構的存儲。

二，鄰接表存儲

1、我們依舊先利用一維數組將圖的頂點存儲起來。

對於：G1

先強調一下弧頭和弧尾以及弧的概念

弧頭和弧尾都是指頂點，在G1中，對於Ea來說V1是弧頭，V2是弧尾

2、再將圖的邊加進來，至於怎麼加？如圖所示：

看看是不是很簡單？

其實就利用一個一維數組存儲鏈表。鏈表的頭結點是頂點（Vi），對於有向圖頭結點後面跟著的是以頂點（Vi）為弧頭的弧。

對於無向圖頭結點後面跟著的是以頂點（Vi）弧（不分方向）

。

頭結點：

頭結點中有兩個域 如圖：

1，data域：存儲頂點（Vi）的數據信息。

2，firstarc域：顧名思義就是該域指向與頂點（Vi）相連的第一條弧（arc）,這裡指的第一條並沒有特定的順序，只是為了和之後的弧進行區分而出現的概念。

邊節點（表節點，弧節點）

表節點中有三個域如圖,

對於跟在頭結點後面的表節點來說，它都對應著頭結點中的頂點（Vi），且如果是有向圖的邊那麼頂點（Vi）只能是邊的弧頭，對於無向圖來說則沒有要求。

1，adjvex:指示通過該邊，與頂點（Vi）連接的另一個頂點在圖中的位置，這裡的位置可以用頭結點在數組中的位置（下標）來表示。

2，next:指向與頂點（Vi）連接的下一條弧（該弧以頂點（Vi）為弧頭）。

3，info：這是一個可以用來存儲邊的權值的域，文章中的都沒有權值，所以不畫出info域。

剛剛說過對於無向圖和有向圖應當注意它們的區別，用鄰接表存儲圖形結構的時候，無向圖的度就是鏈表中表節點的個數，如圖無向圖的鄰接鏈表表示：

但是對於有向圖，鏈表中表節點的個數是頂點（Vi）的出度，因為以（Vi）頂點為頭結點的鏈表後面接著的表節點中是以頂點（Vi）為弧頭的弧，所以要有向圖的度還要求出有向圖的入度，鄰接表中的adjvex域值為i的表節點的個數是頂點（Vi）的入度。

為了方便求有向圖的入度我們引入了逆鄰接表，

G1逆鄰接表如圖：

在逆鄰接表中，鏈表的頭結點是頂點（Vi），對於有向圖後面跟著的是以頂點（Vi）為弧尾的弧。

對比一下鄰接表和逆鄰接表

鄰接表的頭結點和逆接表的頭結點，邊節點一致，只不過是連接方式不一樣。

鄰接表：鏈表的頭結點存儲的（Vi）是弧頭，後面跟著表節點中存儲的是弧頭（Vi）的弧。

簡單來說鏈表中的表節點是頭結點頂點（Vi）指出去的弧，所以鏈表中的表節點個數就是頂點（V

三，十字鏈表法

所謂的十字鏈表法就是結合了鄰接表和逆鄰接表，以方便求出圖形結構的出度和入度。

我們來分析一下十字鏈表法中鏈表的節點。 頭結點：頭結點中有三個域如圖所示：

信息域data：存儲頂點（Vi）數據信息 指針域firstin：存儲第一個以頂點（Vi）為弧頭的邊節點地址 指針域firstout：存儲第一個頂點（Vi）為弧尾的邊節點地址。

表節點（邊節點）：有五個域，如圖所示：

其中頭域headvex和尾域tailvex顧名思義存儲的是該邊（弧）的弧頭和弧尾的信息，可以是弧頭和弧尾在數組中的位置。 鏈域hlink存儲的是和該邊弧頭一樣的邊位置，即hlink指向和該邊弧頭一樣的邊。 鏈域tlink存儲的是和該邊弧尾一樣的邊位置，即hlink指向和該邊弧尾一樣的邊。 信息域info中可以存儲邊的信息如權值。

下面給出圖進行分析（圖太難畫了，我上傳教材上的圖進行分析）

四，鄰接多重表

鄰接多重表是針對於無向圖改進的存儲結構，因為利用方法二鄰接表來存儲無向圖的時候，我們會發現無向圖的一條邊會出現在數組中兩條不同的鏈表中，比如：

Ea出現在a[0]頂點後面，又出現在a[1]頂點後面。

這對我們對邊進行操作的時候十分不便，假設我要刪除一條邊，那麼我要在兩條鏈表中去刪除這條邊兩次，這增加了我們程序的複雜度。

鄰接多重鏈表就是針對於無向圖改進的存儲結構，讓一條邊僅僅用一個節點表示。

一條邊由一個節點六個域表示：如圖所示：

mark域：用來標記這條邊是否被檢索過。 ivex和jvex域：這兩個域中存儲的是頂點的位置,因為一條邊連接兩個頂點，所以這兩個域放在一起講，ivex域中存儲節點Vi的位置，jvex域中存儲節點Vj的位置。 ilink和jlink域：這兩個域中存放的是邊的位置，那為什麼一個邊節點裡面會存儲兩條邊的位置呢？這是因為一條邊對應兩個頂點，而頂點的邊都是由一個個邊節點鏈接起來的，ilink中存儲頂點Vi的下一條邊的位置。

jlink中存儲頂點Vj的下一條邊的位置。 info域：可以用來存儲邊的權值。

頭結點如圖所示：

給出教材中利用多重鏈表對無向圖G2的存儲

我們可以看到其實不管是比較複雜的樹形結構還是圖形結構都可以用線性表來表示，想起了我們老師說過的數據結構其實只有兩種，線性表的順序結構，和線性表的鏈式結構。雖然不敢說老師的話是真理，但是確實有他的道理，像棧，隊列，樹和圖都可以用線性表來表示。有點萬變不離其中的意思。

參考教材：《數據結構》（嚴蔚敏 吳偉民）

《數據結構與演算法》（傳智播客）

推薦閱讀：