7.4 圖的存儲結構
圖是無法以數據元素在內存中的物理位置來表示元素之間的關系，下面提供5種圖的不同的存儲結構。
7.4.1鄰接矩陣又叫數組表示法）
考慮到圖由定點和邊或弧組成，和在一起比較困難，那就很自然的考慮分兩個結構來分別存儲。頂點不分大小、主次，所以用一個一維數組來存儲是不錯的選擇。而邊或弧由於是頂點與頂點之間的關系，一維搞不定，那就考慮用一個二維數組來存儲。於是我們的鄰接矩陣的方案誕生了。
圖的鄰接矩陣存儲方式是用兩個數組來表示圖。一個一維數組存儲圖中頂點信息，一個二維數組稱為鄰接矩陣）存儲圖中的邊或弧的信息。
設圖GV，E）有n個頂點，則鄰接矩陣是一個n x n 的方陣，定義為：
無向圖的邊數組是一個對稱矩陣。
1）要判定任意兩頂點是否有邊無邊就容易了，只需看邊數組中arc[i][j]是否等於1。
2）要知道某個頂點的度，其實就是這個頂點Vi在鄰接矩陣第i行的元素之和。
3）求頂點Vi的所有鄰接點，就是將鄰接矩陣中第i行元素掃描一遍，arc[i][j]為1就是鄰接點。
我們再來看一個有向圖樣例
有向圖講究入度和出度。頂點V1的入度就是第1列各個元素之和。頂點V1的出度就是第1行各個元素之和。
鄰接矩陣的存儲結構
#define MAXVEX 100
#define INFINITY 65535
typedef struct
{
char vexs[MAXVEX]; //頂點表，存儲頂點
int arc[MAXVEX] [MAXVEX]; //鄰接矩陣，存儲邊的信息
int numVertexes; //圖中的頂點的數目
int numEdges;//圖中的邊的數目
}MGraph;
7.4.2鄰接表
鄰接矩陣，對於變數相對較少的圖，這種結構存在對存儲空間的極大浪費。現在考慮另外一種存儲方式，鄰接表。
1、圖中的頂點用一個一維數組存儲，當然，頂點可以用單鏈表來存儲，不過數組更容易讀取頂點信息，更加方便。另外，對於頂點數組中，每個元素還需要存儲指向第一個鄰接點的指針，以便查找該頂點的邊信息。
2、圖中每個頂點Vi的所有鄰接點構成一個線性表，由於鄰接點個數不定，所以采用單鏈表存儲，無向圖稱為頂點Vi的邊表，有向圖則稱為Vi作為弧尾的出邊表。
對於這樣的結構：
1）要想知道某個頂點的度，就去查找這個頂點的邊表中節點的個數。
2）若要判斷頂點Vi到Vj是否存在邊，只需要測試頂點Vi的邊表中adjvex是否存在節點Vj的下標j就行了。
3）若求頂點的所有鄰接點，其實就是對此頂點的邊表進行遍歷，得到的adjvex域對應的頂點就是鄰接點。
若是有向圖，我們以頂點為弧尾來存儲邊表的，這樣很容易得到每個頂點的出度，但有時為了便於確定頂點的入度或以頂點為弧頭的弧，我們可以建立一個有向圖的逆鄰接表。如下圖所示：
對於帶權值的，可以在邊表節點定義中再增加一個weight的數據域，存儲權值信息即可
7.4.3十字鏈表
對於有向圖，鄰接表關心了出度，想了解入度就必須要遍歷整個圖才能知道，有沒有可以把鄰接表和逆鄰接表結合起來呢，就是十字鏈表。
7.4.4鄰接多重表
7.4.5邊集數組
本文出自 “李海川” 博客，請務必保留此出處http://lihaichuan.blog.51cto.com/498079/1293276
