圖 - 圖的存儲結構 - 鄰接表表示法（一）

　　圖的鄰接表表示法

　　圖的鄰接表表示法類似於樹的孩子鏈表表示法對於圖G中的每個頂點v i 該方法把所有鄰接於v i 的頂點v j 鏈成一個帶頭

　　結點的單鏈表這個單鏈表就稱為頂點v i 的鄰接表(Adjacency List)

　　 鄰接表的結點結構

　　()表結點結構

　　┌────┬───┐

　　│adjvex │next │

　　└────┴───┘

　　鄰接表中每個表結點均有兩個域:

　　① 鄰接點域adjvex

　　存放與vi相鄰接的頂點v j 的序號j

　　② 鏈域next

　　將鄰接表的所有表結點鏈在一起

　　注意

　　若要表示邊上的信息(如權值)則在表結點中還應增加一個數據域

　　()頭結點結構

　　┌────┬─────┐

　　│vertex │firstedge │

　　└────┴─────┘

　　頂點v i 鄰接表的頭結點包含兩個域

　　① 頂點域vertex

　　存放頂點v i 的信息

　　② 指針域firstedge

　　v i 的鄰接表的頭指針

　　注意

　　① 為了便於隨機訪問任一頂點的鄰接表將所有頭結點順序存儲在一個向量中就構成了圖的鄰接表表示

　　② 有時希望增加對圖的頂點數及邊數等屬性的描述可將鄰接表和這些屬性放在一起來描述圖的存儲結構

　　無向圖的鄰接表

　　對於無向圖v i 的鄰接表中每個表結點都對應於與v i 相關聯的一條邊因此將鄰接表的表頭向量稱為頂點表將無向圖的

　　鄰接表稱為邊表

　　【例】對於無向圖G 其鄰接表表示如下面所示其中頂點v 的邊表上三個表結點中的頂點序號分別為和它們分別表示

　　關聯於v 的三條邊(v v )(v v )和(v v )

　　

　　注意

　　n個頂點e條邊的無向圖的鄰接表表示中有n個頂點表結點和e個邊表結點

　　有向圖的鄰接表

　　對於有向圖v i 的鄰接表中每個表結點都對應於以v i 為始點射出的一條邊因此將有向圖的鄰接表稱為出邊表

　　【例】有向圖G 的鄰接表表示如下面(a)圖所示其中頂點v 的鄰接表上兩個表結點中的頂點序號分別為和它們分別表示從

　　v 射出的兩條邊(簡稱為v 的出邊)和

　　

　　注意

　　n個頂點e條邊的有向圖它的鄰接表表示中有n個頂點表結點和e個邊表結點

　　有向圖的逆鄰接表

　　在有向圖中為圖中每個頂點v i 建立一個入邊表的方法稱逆鄰接表表示法

　　入邊表中的每個表結點均對應一條以v i 為終點(即射入v i )的邊

　　【例】G 的逆鄰表如上面(b)圖所示其中v 的人邊表上兩個表結點和分別表示射人v 的兩條邊(簡稱為v 的入邊)

　　1 ，v 0 >和。tw.WInGwiT.COM

　　注意：

　　n個頂點e條邊的有向圖，它的接表表示中有n個頂點表結點和e個邊表結點。

From:http://tw.wingwit.com/Article/program/sjjg/201311/23847.html