1.2 鄰接表

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

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

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

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

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

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