圖其實就是頂點和邊的集合，所以說，圖的存儲本質(zhì)就是存儲圖的頂點和邊。

1. 鄰接矩陣

頂點存儲在一維數(shù)組中
邊存儲在二維數(shù)組（矩陣）中，arc[v][w]表示的就是v到w的邊
如果v到w的邊存在則存儲邊的權(quán)值，如果不存在則標(biāo)為無窮

2. 鄰接表

稀疏圖存在的邊是很少的，有向圖的鄰接矩陣是對稱的。所以，這兩種情況下使用鄰接矩陣存儲邊都是很浪費(fèi)空間的。
因此可以使用鄰接表，類似于樹的孩子表示法。頂點中有指針域，指向鄰頂點的鏈表，與該頂點相鄰的頂點依次在鏈表中排序

Paste_Image.png

有向圖中，需要用兩個鄰接表存儲邊，鄰接表與逆鄰接表。用于分別存儲不同方向的邊（出邊和入邊）。

3. 十字鏈表

專用于有向圖，解決鄰接表需要兩個鄰接表的問題。
形如鄰接表，但鏈表結(jié)點的結(jié)構(gòu)有所不同，且除了出邊鏈表，還有入邊鏈表

鏈表結(jié)點結(jié)構(gòu)

tailVex：弧指向的結(jié)點
headVex：弧出發(fā)的點
headLink：指向入邊鏈表的下一個結(jié)點
tailLink：指向出邊鏈表的下一個結(jié)點
可以理解為，一個鏈表結(jié)點（等于是一條表）同時存在兩個鏈表當(dāng)中，因此整個十字鏈表是，所有鏈交織成一張網(wǎng)。

十字鏈表

4. 鄰接多重鏈表

無向圖優(yōu)化存儲結(jié)構(gòu)，無向圖的邊是對稱的，在鄰接表中，<v1,v2>,<v2,v1>表達(dá)的是同一條邊。除了占用存儲空間外，刪除，添加邊的時候也很麻煩，對一條邊的操作，要處理兩次。
鄰接多重鏈表其頂點指向的是一條邊，而非一個鏈表。

邊的存儲結(jié)構(gòu)

iVex，jVex分別是邊的結(jié)點
iLink是指向iVex結(jié)點的下一條邊的指針
jLink是指向jVex結(jié)點的下一條邊的指針

鄰接多重表

如果要遍歷一個頂點的所有邊，從頂點的指針指向的第一條邊出發(fā)。然后找到邊中與頂點相對應(yīng)的指針，找下一條邊。

5. 邊集數(shù)組

邊集數(shù)組

就是如此簡單粗暴地把頂點和邊存儲，但后期還原圖的時候需要多次的遍歷，存儲結(jié)構(gòu)簡單，但是操作圖就變得復(fù)雜了。