因為圖的結構特點，使得其在存儲、遍歷也相對復雜一些。

鄰接矩陣存儲圖

最簡單的方式就是將圖的頂點用一維數組存儲進來，然后將邊信息存儲在二維矩陣中，這兩個數組合稱為圖的鄰接矩陣（Adjacency Matrix）。

無向圖的鄰接矩陣

有向圖的鄰接矩陣

鄰接表存儲圖

看上圖鄰接矩陣的結構，可以得知鄰接矩陣中的邊數組中存在大量為零的空占位，浪費了大量空間，所以就自然而然想到利用鏈表來進行邊的存儲，這就是鄰接表（Adjacency List）。

無向圖的鄰接表

有向圖的鄰接表

有向圖鄰接表的邊表為以弧尾為鏈表表頭進行存儲的，這樣對于頂點的出度統計較為方便，而有向圖逆鄰接表則正好與鄰接表相反，邊表是以弧尾作為鏈表表頭的。

有向圖逆鄰接表邊表

網的鄰接表

鄰接多重表存儲無向圖

假如對無向圖的鄰接表進行刪除某邊操作時需要對相關結點進行遍歷找到相應邊然后進行刪除，比較麻煩，故鄰接多重表對其進行改良。

邊表結構：

其中，ivex和jvex為某邊依附的兩頂點在頂點表中的下標，ilink指向依附頂點ivex的下一條邊，同理jlink指向依附頂點jvex的下一條邊。

鄰接多重表結構

十字鏈表存儲有向圖

用鄰接表存儲有向圖存在一個問題，對于某一頂點的弧統計還是很麻煩的，鄰接表對于頂點作為弧頭的弧統計很麻煩，逆鄰接表對于頂點作為弧尾的弧統計很麻煩。所以為了對頂點更好的查詢，便參考線索二叉樹的設計思路，得到了十字鏈表（Orthogonal List）。

頂點表的結構為：

邊表結構為：

其中，tailvex為弧尾在頂點表中的下標，headvex為弧頭在頂點表中的下標，headlink指的是入邊表指針域，指的是弧頭相同的下一條邊，taillink指的是出邊表指針域，指的是弧尾相同的下一邊。

十字鏈表存儲示意

圖中實線為鄰接表，虛線為逆鄰接表。

邊集數組存儲圖

注意和鄰接矩陣進行區別。

總結

以上是生活随笔為你收集整理的假设以邻接矩阵作为图的存储结构_图的存储的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。