• 對于圖來說，鄰接矩陣是不錯的一種圖存儲結構，但是我們也發(fā)現(xiàn)，對于邊數(shù)相對頂點較少的圖，這種結構是存在對存儲空間的極大浪費的。因此我們考慮另外一種存儲結構方式：鄰接表（Adjacency List），即數(shù)組與鏈表相結合的存儲方法。

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

1、圖中頂點用一個一維數(shù)組存儲，另外，對于頂點數(shù)組中，每個數(shù)據(jù)元素還需要存儲指向第一個鄰接點的指針，以便于查找該頂點的邊信息。

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

• 例如圖7-4-6就是一個無向圖的鄰接表結構。

若是有向圖，鄰接表的結構是類似的，如圖7-4-7，以頂點作為弧尾來存儲邊表容易得到每個頂點的出度，而以頂點為弧頭的表容易得到頂點的入度，即逆鄰接表。

對于帶權值的網圖，可以在邊表結點定義中再增加一個weight的數(shù)據(jù)域，存儲權值信息即可，如圖7-4-8所示。

• 下面示例無向圖的鄰接表創(chuàng)建：（改編自《大話數(shù)據(jù)結構》）

這里的鄰接點插入使用了單鏈表創(chuàng)建中的頭插法，對于無向圖來說，一條邊對應都是兩個頂點，所以在循環(huán)中，一次就針對i和j分別進行了插入。