思路：

有沒有可能把鄰接表和逆鄰接表結合起來。

所以就產生了十字鏈表(Orthogonal List)

為此我們重新定義頂點表結點結構：

data

firstIn

firstOut

firstIn：第一個入邊

firstOut：第一個出邊

然后定義邊表結點結構

tailVex

headVex

headLink

tailLink

tailVex：弧起點的頂點的下標

headVex：弧終點的頂點的下標

headLink：逆鄰接表

tailLink：鄰接表

如下圖所示：

十字鏈表結構復制，其實創建圖算法的時間復雜度是和鄰接表相同的，因此，在有向圖中，十字鏈表是非常好的數據結構模型。

鄰接多重表

如果要刪除鄰接表中的結點，那么就要把結點刪除，然后把刪除結點的前后兩個結點連接起來。

所以比較復制。

對于這種情況，就產生了連接多重表。

重新定義邊表結構，如下：

iVex

iLink

jVex

jLink

其中iVex和jVex是與某邊依附的兩個頂點在頂點表中的下標。iLink指向衣服頂點iVex下一條邊，jLink指向依附頂點jVex的下一條邊。

也就是說在鄰接多重表里面，邊表存放的是一條邊，而不是一個頂點。

如下圖所示：

邊集數組

由兩個一位數組構成，一個是存儲頂點信息，一個存儲邊信息，這個邊數組每個數據元素由一個邊的起點下標（begin）、終點下標（end）和權（weight）組成。

如下圖：

總結

以上是生活随笔為你收集整理的7.2图的存储结构(十字链表、邻接多重表、边集数组)的全部內容，希望文章能夠幫你解決所遇到的問題。

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