2018年國(guó)家電網(wǎng)考試備考計(jì)算機(jī)之?dāng)?shù)據(jù)結(jié)構(gòu)與算法(12)

1.2 鄰接表

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

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

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

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

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

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