稀疏圖的存儲

1. 圖的五種存儲結構

圖的鄰接矩陣（Adjacency Matrix）： 圖的鄰接矩陣用兩個數組來表示圖。一個一維數組存儲圖中頂點信息，另一個二維數組（一般稱之為鄰接矩陣）來存儲圖中的邊或者弧的信息。從鄰接矩陣中我們自然知道一個頂點的度（對於無向圖）或者有向圖中一個頂點的入度出度信息。

假設圖G有n個頂點，則鄰接矩陣是一個n*n的方陣。
1.對於如果圖上的每條邊不帶權值來說，那麼我們就用真（一般為1）和假（一般為0）來表示一個頂點到另一個頂點存不存在邊。下面是一個圖的鄰接矩陣的定義：

鄰接矩陣法實現帶權值的無向圖的創建如下：

按照如圖輸入各邊（不重復）

測試程序如下：

結果可得該矩陣，證明創建樹成功。 假設n個頂點e條邊的創建，createGraph演算法的時間復雜度為O（n+n*n+e）。如果需要創建一個有向圖，那麼和上面一樣一個一個錄入邊下標和權值。

鄰接矩陣這種存儲結構的優缺點： 缺點是對於邊數相對頂點較少的稀疏圖來說會存在極大的空間浪費。假設有n個頂點,優點是對於有向完全圖和無向完全圖來說鄰接矩陣是一種不錯的存儲結構，浪費的話也只浪費了n個頂點的容量。

在樹的存儲結構一節中我們提到對於孩子表示法的第三種：用一段連續的存儲單元（數組）存儲樹中的所有結點，利用一個單鏈表來存儲數組中每個結點的孩子的信息。對於圖的存儲結構來說，我們也可以利用這種方法實現圖的存儲

鄰接表(Adjacency List): 這種數組與鏈表相結合的存儲方法叫做鄰接表。1.為什麼不也用單鏈表存儲圖的結點信息呢？原因就是數組這種順序存儲結構讀取結點信息速率快。對於頂點數組中，每個數據元素還需要存儲一個指向第一個鄰接頂點的指針，這樣才可以查找邊的信息2.圖中每個頂點Vi(i > 0)的所有鄰接點構成一個線性表 （在無向圖中這個線性表稱為Vi的邊表，有向圖中稱為頂點作為弧尾的出邊表） ，由於鄰接點的不確定性，所以用鏈表存儲，有多少個鄰接點就malloc一個空間存儲鄰接點，這樣更不會造成空間的浪費（與鄰接矩陣相比來說）。3.對於鄰接表中的某個頂點來說，用戶關心的是這個頂點的鄰接點，完全可以遍歷用單鏈表設計成的邊表或者出邊表得到，所以沒必要設計成雙鏈表。

鄰接表的存儲結構：
假設現在有一無向圖G，如下圖：

從鄰接表結構中，知道一個頂點的度或者判斷兩個頂點之間是否存在邊或者求一個頂點的所有鄰接頂點是很容易的。

假設現在有一有向圖G，如下圖：

無向圖的鄰接表創建示例如下：

假設在上圖（無向圖）中的V0V1V2V3頂點值為ABCD，則依據下面測試程序可得結果：

鄰接表的優缺點： 優點是：鄰接表存儲圖，既能夠知道一個頂點的度和頂點的鄰接結點的信息，並且更不會造成空間的浪費。缺點是鄰接表存儲有向圖時，如果關心的是頂點的出度問題自然用鄰接表結構，但是想了解入度需要遍歷圖才知道（需要考慮逆鄰接表）。

十字鏈表(Orthogonal List) ：有向圖的一種存儲方法，它把鄰接表和逆鄰接表結合起來，因此在十字鏈表結構中可以知道一個頂點的入度和出度情況。
重新定義頂點表的結點如下圖：

現在有一有向圖如下圖：

則它的存儲結構示意圖為：

其定義如下：

十字鏈表是用來存儲有向圖的，這樣可以看出一個頂點的出入度信息。對於無向圖來說完全沒必要用十字鏈表來存儲。

在無向圖中，因為我們關注的是頂點的信息，在考慮節約空間的情況下我們利用鄰接表來存儲無向圖。但是如果我們關注的是邊的信息，例如需要刪除某條邊對於鄰接表來說是挺繁瑣的。它需要操作兩個單鏈表刪除兩個結點。因此我們仿照十字鏈表的方式對邊表結點結構重新定義如下圖：

它的鄰接多重表結構為：

多重鄰接表的優點：對於邊的操作相比於鄰接表來說更加方便。比如說我們現在需要刪除(V0,V2)這條邊，只需將69步驟中的指針改為nullptr即可。

邊集數組(edgeset array)： 邊集數組是由兩個數組組成，一個存儲頂點信息，另一個存儲邊的信息，這個邊數組中的每個數據元素由起點下標，終點下標，和權組成（如果邊上含有權值的話）。
邊數組結構如下圖：

邊集數組實現圖的存儲的優缺點：優點是對於邊的操作方便快捷，操作的只是數組元素。比如說刪除某條邊，只需要刪除一個數組元素。缺點是：對於圖的頂點信息，我們只有遍歷整個邊數組才知道，這個費時。因此對於關注邊的操作來說，邊集數組更加方便。

2. 設有一稀疏圖G，則G採用什麼存儲較省空間

搜一下：設有一稀疏圖G，則G採用什麼存儲較省空間

3. 設有一稀疏圖G，則G採用什麼存儲較省空間

G採用鄰接表存儲較省空間。

鄰接表，存儲方法跟樹的孩子鏈表示法相類似，是一種順序分配和鏈式分配相結合的存儲結構。如這個表頭結點所對應的頂點存在相鄰頂點，則把相鄰頂點依次存放於表頭結點所指向的單向鏈表中。

對於無向圖來說，使用鄰接表進行存儲也會出現數據冗餘，表頭結點A所指鏈表中存在一個指向C的表結點的同時，表頭結點C所指鏈表也會存在一個指向A的表結點。

(3)稀疏圖的存儲擴展閱讀：

表示法

n個頂點e條邊的無向圖的鄰接表表示中有n個頂點表結點和2e個邊表結點。(換句話說，每條邊（i,j）在鄰接表 中出現兩次：一次在關於i的鄰接表中，另一次在關於j的鄰接表中)。

對於有向圖，vi的鄰接表中每個表結點都對應於以vi為始點射出的一條邊。因此，將有向圖的鄰接表稱為出邊表。對於無向圖來說，使用鄰接表進行存儲也會出現數據冗餘，表頭結點A所指鏈表中存在一個指向C的表結點的同時，表頭結點C所指鏈表也會存在一個指向A的表結點。

4. 迴路是簡單路徑 存儲稀疏圖，用鄰接矩陣比鄰接表更省空間

1、如果簡單路徑定義為除了頭尾可以重復其他頂點不能重復，則第一句就是對的，不然不對
2、存儲稀疏圖，用鄰接表比鄰接矩陣更省空間，因此第二句錯的
3、有向無環圖才可以有拓撲序列，因此第三句對的

5. 稀疏矩陣一般的壓縮存儲方法有兩種

分別是三元組和十字鏈表。

三元組是指形如（（x，y），z）的集合（這就是說，三元組是這樣的偶，其第一個射影亦是一個偶），常簡記為（x，y，z）。

三元組是計算機專業的一門公共基礎課程——數據結構里的概念。主要是用來存儲稀疏矩陣的一種壓縮方式，也叫三元組表。假設以順序存儲結構來表示三元組表（triple table），則得到稀疏矩陣的一種壓縮存儲方式，即三元組順序表，簡稱三元組表。

十字鏈表（Orthogonal List)是有向圖的另一種鏈式存儲結構。該結構可以看成是將有向圖的鄰接表和逆鄰接表結合起來得到的。用十字鏈表來存儲有向圖，可以達到高效的存取效果。同時，代碼的可讀性也會得到提升。

拓展資料：

十字鏈表（Orthogonal List)是有向圖的另一種鏈式存儲結構。可以看成是將有向圖的鄰接表和逆鄰接表結合起來得到的一種鏈表。在十字鏈表中，對應於有向圖中每一條弧都有一個結點，對應於每個定頂點也有一個結點。

十字鏈表之於有向圖，類似於鄰接表之於無向圖。

也可以理解為 將行的單鏈表和列的單鏈表結合起來存儲稀疏矩陣稱為十字鏈表， 每個節點表示一個非零元素。

三元組解釋：

1、所謂「三元組」是指圖形的幾何元素構成、圖線間的拓撲關系和尺寸約束。如果一組圖形的前二元相同而只是尺寸大小不同，則這組圖形構成一族形狀相同的系列化圖形。

2、把組成一個元素的三個數稱為三元組。一個三元組包含以下三部分的內容SDO_STARTING_OFFSET表明每個幾何元素的第一個坐標在SDO_ORDINATES數組中的存儲位置。

3、…Mt：N2）的表示稱為三元組...…Mt稱為標號，N1、N2為結點R為關系。當n≠0時，稱Li為對結點N1的修飾。t≠0時，稱Mj為對結點N2的修飾。

參考資料：網路：十字鏈表

網路：三元組

6. 圖的表示：如何存儲微博、微信等社交網路中的好友關系

x博中，兩個人可以互相關注，互加好友，那如何存儲這些社交網路的好友關系呢？

這就要用到：圖。

和樹比起來，這是一種更加復雜的非線性表結構。

樹的元素稱為節點，圖中元素叫作頂點（vertex）。圖中的一個頂點可以與任意其他頂點建立連接關系，這種建立的關系叫作邊（edge）。

社交網路就是典型的圖結構。

把每個用戶看作一個頂點。如果兩個用戶之間互加好友，就在兩者之間建立一條邊。
所以，整個微信的好友關系就可用一張圖表示。
每個用戶有多少個好友，對應到圖中就叫作頂點的度（degree），即跟頂點相連接的邊的條數。

不過微博的社交關系跟微信還有點不同，更復雜一點。微博允許單向關注，即用戶A關注用戶B，但B可不關注A。

這就引入邊的「方向」。

A關注B，就在圖中畫一條從A到B的帶箭頭的邊，表示邊的方向。A、B互關，就畫一條從A指向B的邊，再畫一條從B指向A的邊，這種邊有方向的圖叫作「有向圖」。邊沒有方向的圖也就叫「無向圖」。

無向圖中有「度」：一個頂點有多少條邊。
有向圖中，把度分為：

QQ社交關系更復雜，不僅記錄用戶之間的好友關系，還記錄了兩個用戶之間的親密度，如何在圖中記錄這種好友關系親密度呢？
這就要用到帶權圖（weighted graph），每條邊都有個權重（weight），可以通過這個權重來表示QQ好友間的親密度。

最直觀的一種存儲方法，鄰接矩陣（Adjacency Matrix）。

依賴一個二維數組：

無向圖，若A[i][j]==1，則A[j][i]==1。實際上，只需存儲一個即可。即無向圖的二維數組，如果將其用對角線劃分為上下兩部分，則只需利用上或下面這樣一半空間就夠了，另外一半其實完全浪費。
如果存儲的是稀疏圖（Sparse Matrix），即頂點很多，但每個頂點的邊並不多，則更浪費空間。
如微信有好幾億用戶，對應到圖就是好幾億頂點。但每個用戶好友並不很多，一般也就三五百個而已。如果我們用鄰接矩陣來存儲，那絕大部分的存儲空間都被浪費了。

但這也並不是說，鄰接矩陣的存儲方法就完全沒有優點。首先，鄰接矩陣的存儲方式簡單、直接，因為基於數組，所以在獲取兩個頂點的關系時，就非常高效。其次，用鄰接矩陣存儲圖的另外一個好處是方便計算。這是因為，用鄰接矩陣的方式存儲圖，可以將很多圖的運算轉換成矩陣之間的運算。比如求解最短路徑問題時會提到一個Floyd-Warshall演算法，就是利用矩陣循環相乘若干次得到結果。

針對上面鄰接矩陣比較浪費內存空間，另外一種圖存儲，鄰接表（Adjacency List）。

有點像散列表？每個頂點對應一條鏈表，鏈表中存儲的是與這個頂點相連接的其他頂點。圖中畫的是一個有向圖的鄰接表存儲方式，每個頂點對應的鏈表裡面，存儲的是指向的頂點。對於無向圖來說，也是類似的，不過，每個頂點的鏈表中存儲的，是跟這個頂點有邊相連的頂點，你可以自己畫下。

如上圖示例，若要確定是否存在一條從頂點2到頂點4的邊，就要遍歷頂點2的鏈表，看其中是否存在頂點4，而鏈表存儲對緩存不友好。所以鄰接表查詢兩個頂點之間的關系較為低效。

基於鏈表法解決沖突的散列表中，若鏈過長，為提高查找效率，可將鏈表換成其他更高效數據結構，如平衡二叉查找樹。
鄰接表長得很像散列。所以，也可將鄰接表同散列表一樣進行「優化」。

可將鄰接表中的鏈表改成平衡二叉查找樹。實際可選用紅黑樹。即可更快速查找兩個頂點之間是否存在邊。
這里的二叉查找樹也可換成其他動態數據結構，如跳錶、散列表。
還可將鏈表改成有序動態數組，通過二分查找快速定位兩個頂點之間是否存在邊。

雖然微博有向圖，微信是無向圖，但對該問題，二者思路類似，以微博為例。

數據結構服務於演算法，選擇哪種存儲方法和需支持的操作有關。
對於微博用戶關系，需支持如下操作：

因為社交網路是一張稀疏圖，使用鄰接矩陣存儲比較浪費存儲空間。所以，這里採用鄰接表。

但一個鄰接表存儲這種有向圖也是不夠的。查找某用戶關注了哪些用戶很容易，但若想知道某用戶都被哪些用戶關注了，即粉絲列表就沒法了。

因此，還需一個逆鄰接表，存儲用戶的被關注關系：

基礎的鄰接表不適合快速判斷兩個用戶是否為關注與被關注關系，所以進行優化，將鄰接表的鏈表改為支持快速查找的動態數據結構。

因需按照用戶名稱首字母排序，分頁獲取用戶的粉絲列表或關注列表，跳錶最合適：插入、刪除、查找都非常高效，時間復雜度 ，空間復雜度稍高，是 。
跳錶存儲數據先天有序，分頁獲取粉絲列表或關注列表，非常高效。

對小規模數據，如社交網路中只有幾萬、幾十萬個用戶，可將整個社交關系存儲在內存，該解決方案沒問題。

可通過哈希演算法等數據分片方案，將鄰接表存儲在不同機器：
如下圖，在機器1上存儲頂點1，2，3的鄰接表，在機器2上，存儲頂點4，5的鄰接表。逆鄰接表的處理方式也一樣。當要查詢頂點與頂點關系的時候，我們就利用同樣的哈希演算法，先定位頂點所在的機器，然後再在相應的機器上查找。

還能藉助外部存儲（比如硬碟），因為外部存儲的存儲空間比內存多很多：
如用下表存儲這樣一個圖。為高效支持前面定義的操作，可建多個索引，比如第一列、第二列，給這兩列都建立索引。

7. 1.設有一稠密圖G，則G採用（ ）存儲較省空間，設有一稀疏圖G，則G採用（ ）存儲較省空間

鄰接矩陣
鄰接表

8. 稀疏圖為什麼用鄰接表存儲而不用鄰接矩陣我知道是空間效率問題，怎麼個說啊謝謝大神！

既然是稀疏圖 那麼每個節點的鄰居節點數目肯定少咯 當然用鄰接表（N個節點，用N*m個位置，m為每個節點的平均鄰居數目）
要是用鄰接矩陣的話 每個節點都要給鄰居空N-1個位置（N個節點，需要N*N個位置）
當m遠小於N時（稀疏圖就符合這種情況），當然鄰接表省空間。

9. 關於數據結構中圖的儲存方式的選擇

首先你要明白，鄰接鏈表存圖的空間復雜度與圖中邊的數量有關(O(N+E) E表示圖中邊的數目)，而數組存圖空間復雜度與點數有關（O(N^2)N表示點數）
看點的數量，如果點的數量不是很大（比如幾百個左右或者更小）那麼二者都可以選擇。
如果點的數量過大的話，用數組存儲稀疏圖會造成大量的空間浪費，此時選擇使用鄰接表更好。

10. 鄰接表與鄰接矩陣的異同點有哪些

（1）聯系：鄰接表中每個鏈頭後的所有邊表結點對應鄰接矩陣中的每一行，鄰接表中的每個邊表結點對應鄰接矩陣該行的一個非零元素。

（2）區別：

①對於任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關）。

②鄰接矩陣的空間復雜度為0（n2），而鄰接表的空間復雜度為0（n＋e）。

③在鄰接表上容易找到任意一頂點的第一個鄰接點和下一個鄰接點，但要判定任意兩個頂點（vi，vj）之間是否有邊或弧相連，則需搜索第i個或第j個鏈表，還不及鄰接矩陣方便。

④鄰接矩陣多用於稠密圖的存儲（e接近n（n－1）／2），而鄰接表多用於稀疏圖的存儲（e＜＜n2）。