8.2 圖的存儲結構
圖的存儲結構除了要存儲圖中各個頂點的本身的信息外，同時還要存儲頂點與頂點之間的所有關系（邊的信息），因此，圖的結構比較復雜，很難以數據元素在存儲區中的物理位置來表示元素之間的關系，但也正是由於其任意的特性，故物理表示方法很多。常用的圖的存儲結構有鄰接矩陣、鄰接表、十字鏈表和鄰接多重表。
8.2.1鄰接矩陣表示法
對於一個具有n個頂點的圖，可以使用n*n的矩陣（二維數組）來表示它們間的鄰接關系。圖8.10和圖8.11中，矩陣A(i，j)=1表示圖中存在一條邊(Vi，Vj)，而A(i，j)=0表示圖中不存在邊(Vi，Vj)。實際編程時，當圖為不帶權圖時，可以在二維數組中存放bool值，A(i，j)=true表示存在邊(Vi，Vj)，A(i，j)=false表示不存在邊(Vi，Vj)；當圖帶權值時，則可以直接在二維數組中存放權值，A(i，j)=null表示不存在邊(Vi，Vj)。
圖8.10所示的是無向圖的鄰接矩陣表示法，可以觀察到，矩陣延對角線對稱，即A(i，j)= A(j，i)。無向圖鄰接矩陣的第i行或第i列非零元素的個數其實就是第i個頂點的度。這表示無向圖鄰接矩陣存在一定的數據冗余。
圖8.11所示的是有向圖鄰接矩陣表示法，矩陣並不延對角線對稱，A(i，j)=1表示頂點Vi鄰接到頂點Vj；A(j，i)=1則表示頂點Vi鄰接自頂點Vj。兩者並不象無向圖鄰接矩陣那樣表示相同的意思。有向圖鄰接矩陣的第i行非零元素的個數其實就是第i個頂點的出度，而第i列非零元素的個數是第i個頂點的入度，即第i個頂點的度是第i行和第i列非零元素個數之和。
由於存在n個頂點的圖需要n2個數組元素進行存儲，當圖為稀疏圖時，使用鄰接矩陣存儲方法將出現大量零元素，照成極大地空間浪費，這時應該使用鄰接表表示法存儲圖中的數據。
8.2.2 鄰接表表示法
圖的鄰接矩陣存儲方法跟樹的孩子鏈表示法相類似，是一種順序分配和鏈式分配相結合的存儲結構。鄰接表由表頭結點和表結點兩部分組成，其中圖中每個頂點均對應一個存儲在數組中的表頭結點。如這個表頭結點所對應的頂點存在相鄰頂點，則把相鄰頂點依次存放於表頭結點所指向的單向鏈表中。如圖8.12所示，表結點存放的是鄰接頂點在數組中的索引。對於無向圖來說，使用鄰接表進行存儲也會出現數據冗余，表頭結點A所指鏈表中存在一個指向C的表結點的同時，表頭結點C所指鏈表也會存在一個指向A的表結點。
有向圖的鄰接表有出邊表和入邊表（又稱逆鄰接表）之分。出邊表的表結點存放的是從表頭結點出發的有向邊所指的尾頂點；入邊表的表結點存放的則是指向表頭結點的某個頭頂點。如圖8.13所示，圖(b)和(c)分別為有向圖(a)的出邊表和入邊表。
以上所討論的鄰接表所表示的都是不帶權的圖，如果要表示帶權圖，可以在表結點中增加一個存放權的字段，其效果如圖8.14所示。
