圖的兩種存儲方式：鄰接表、鄰接矩陣
圖的存儲結構主要分兩種，一種是，一種是鄰接矩陣
。鄰接表
1.鄰接矩陣
圖的鄰接矩陣存儲方式是用兩個數組來表示圖：一個一維數組存儲圖中頂點資訊，一個二維數組（鄰接矩陣）存儲圖中的邊或弧的資訊。
設圖G有n個頂點，則鄰接矩陣是一個 n ∗ n n*n n∗n 的方陣，定義為：
a r g [ i ] [ j ] = { 1 ， 若 ( v i , v j ) ∈ E < v i , v j > ∈ E 0 ， 若 ( v i , v j ) ∉ E < v i , v j > ∉ E arg[i][j]=\left\{ \begin{aligned} 1 ，& 若(v_i,v_j) \in E <v_i,v_j> \in E\\ 0 ，&若(v_i,v_j) \notin E <v_i,v_j> \notin E\\ \end{aligned} \right. arg[i][j]={1，0，若(vi,vj)∈E<vi,vj>∈E若(vi,vj)∈/E<vi,vj>∈/E
看一個執行個體，下圖左就是一個無向圖。
從上面可以看出，無向圖的邊數組是一個對稱矩陣。所謂對稱矩陣就是 n n n 階矩陣的元滿足 a i j = a j i a_{ij} = a_{ji} aij=aji。即從矩陣的左上角到右下角的主對角線為軸，右上角的元和左下角相對應的元全都是相等的。從這個矩陣中，很容易知道圖中的資訊。
- 要判斷任意兩頂點是否有邊無邊就很容易了；
- 要知道某個頂點的度，其實就是這個頂點 v i v_i vi 在鄰接矩陣中第 i i i 行或（第 i i i 列）的元素之和；
- 求頂點 v i v_i vi 的所有鄰接點就是将矩陣中第i行元素掃描一遍， a r c [ i ] [ j ] arc[i][j] arc[i][j]為1就是鄰接點；
有向圖講究入度和出度，頂點 v i v_i vi 的入度為1，正好是第 i i i 列各數之和。頂點 v i v_i vi 的出度為2，即第 i i i 行的各數之和。
若G是網圖，有 n n n 個頂點，則鄰接矩陣是一個 n ∗ n n*n n∗n的方陣，定義為：
a r g [ i ] [ j ] = { W i j ， 若 ( v i , v j ) ∈ E < v i , v j > ∈ E 0 ， 若 i = j ∞ ， 反 arg[i][j]=\left\{ \begin{aligned} W_{ij} ，&若(v_i,v_j) \in E <v_i,v_j> \in E\\ 0，&若 i=j\\ \infty，&反 \end{aligned} \right. arg[i][j]=⎩⎪⎨⎪⎧Wij，0，∞，若(vi,vj)∈E<vi,vj>∈E若i=j反
2.鄰接表
鄰接矩陣是不錯的一種圖存儲結構，但是，對于邊數相對頂點較少的圖，這種結構存在對存儲空間的極大浪費。是以，找到一種數組與連結清單相結合的存儲方法稱為鄰接表。
鄰接表的處理方法是這樣的：
- 圖中頂點用一個一維數組存儲，當然，頂點也可以用單連結清單來存儲，不過，數組可以較容易的讀取頂點的資訊，更加友善;
- 圖中每個頂點 v i v_i vi 的所有鄰接點構成一個線性表，由于鄰接點的個數不定，是以，用單連結清單存儲，無向圖稱為頂點 v i v_i vi 的邊表，有向圖則稱為頂點 v i v_i vi 作為弧尾的出邊表。
例如，下圖就是一個無向圖的鄰接表的結構。
從圖中可以看出，頂點表的各個結點由
data
和
first_edge
兩個域表示，
data
是資料域，存儲頂點的資訊，
first_edge
是指針域，指向邊表的第一個結點，即此頂點的第一個鄰接點。邊表結點由
adjvex
和
next
兩個域組成。
adjvex
是鄰接點域，存儲某頂點的鄰接點在頂點表中的下标，
next
則存儲指向邊表中下一個結點的指針。
對于帶權值的網圖，可以在邊表結點定義中再增加一個
weigt
的資料域，存儲權值資訊即可。如下圖所示。
)
3.兩者差別
- 對于一個具有 n n n 個頂點 e e e 條邊的無向圖：它的鄰接表表示有 n n n個頂點表結點 2 e e e 個邊表結點；
- 對于一個具有 n n n個頂點 e e e條邊的有向圖：它的鄰接表表示有 n n n個頂點表結點 e e e個邊表結點；
- 如果圖中邊的數目遠遠小于 n 2 n^2 n2 稱作稀疏圖，這是用鄰接表表示比用鄰接矩陣表示節省空間；
- 如果圖中邊的數目接近于 n 2 n^2 n2,對于無向圖接近于 n ∗ ( n − 1 ) n*(n-1) n∗(n−1) 稱作稠密圖,考慮到鄰接表中要附加鍊域，采用鄰接矩陣表示法為宜。