1.2 鄰接表

鄰接矩陣是不錯的一種圖存儲結(jié)構(gòu)，但是，對于邊數(shù)相對頂點較少的圖，這種結(jié)構(gòu)存在對存儲空間的極大浪費。因此，找到一種數(shù)組與鏈表相結(jié)合的存儲方法稱為鄰接表。

鄰接表的處理方法是這樣的：

(1)圖中頂點用一個一維數(shù)組存儲，當然，頂點也可以用單鏈表來存儲，不過，數(shù)組可以較容易的讀取頂點的信息，更加方便。

(2)圖中每個頂點vi的所有鄰接點構(gòu)成一個線性表，由于鄰接點的個數(shù)不定，所以，用單鏈表存儲，無向圖稱為頂點vi的邊表，有向圖則稱為頂點vi作為弧尾的出邊表。

例如，下圖就是一個無向圖的鄰接表的結(jié)構(gòu)。

對于鄰接表結(jié)構(gòu)，圖的建立代碼如下。