鄰接多重表

鄰接多重表(adjacent multiList)是無向圖（網）的另一種鏈式存儲結構。在此存儲結構中，圖的頂點信息存放在頂點數組中，數組元素有兩個域：data域，存放與頂點相關的信息；firstedge域，指向一個單鏈表，此單鏈表存儲所有依附於該頂點的邊的信息。這些單鏈表的一個表結點對應一條邊，表結點有六個域：mark為標誌域，用來標記該邊是否被訪問過；ivex和jvex分別存放該邊兩個頂點在無向圖中的位置；info域存放該邊相關的信息，實際上就是弧的權值，對於無向圖，info域可省略; ilink指向下一條依附於頂點ivex的邊對應的表結點;jlink指向下一條依附於頂點jvex的邊對應的表結點。 ^[2] 

鄰接表是圖的一種順序存儲與鏈式存儲相結合的存儲結構，類似於樹的孩子鏈表法順序存儲是指無向圖中的頂點信息用一個一維數組來存儲，一個頂點數組元素是一個頂點結點。頂點結點有兩個域，一個是數據域(data)，存放與頂點相關的信息;一個是指針域( firestar)存放該頂點的鄰接表的第一個結點的地址。頂點的鄰接表是把所有鄰接於某結點的頂點構成一個表，它採用鏈式存儲結構。鄰接表中的每個結點保存的是與該頂點相關的邊或弧的信息，它有兩個域，一個是鄰接頂點域 adnex)，存放鄰接頂點的信息，實際上就是鄰接頂點在頂點數組中的序號:另一個是指針域( next arc)，存放下一個鄰接頂點的結點的地址。 ^[3] 

解決鄰接表存儲無向圖時同一條邊要存儲兩次的問題。

鄰接多重表主要用於存儲無向圖。因為如果用鄰接表存儲無向圖，每條邊的兩個邊結點分別在以該邊所依附的兩個頂點為頭結點的鏈表中，這給圖的某些操作帶來不便。例如，對已訪問過的邊做標記，或者要刪除圖中某一條邊等，都需要找到表示同一條邊的兩個結點。因此，在進行這一類操作的無向圖的問題中，採用鄰接多重表作存儲結構更為適宜。 ^[4] 

在邊表中，每條邊只出現一次，但讓這條邊屬於兩個單鏈表。 ^[5]  鄰接多重表的存儲結構和十字鏈表類似，也是由頂點表和邊表組成，每一條邊用一個結點表示。 ^[4] 

在鄰接多重表在鄰接多重表中，所有依附於同一頂點的邊串聯在同一鏈表中，由於每條邊依附於兩個頂點，則每個邊結點同時鏈接在兩個鏈表中。可見，對無向圖而言，其鄰接多重表和鄰接表的差別，僅僅在於同一條邊在鄰接表中用兩個結點表示，而在鄰接多重表中只用一個結點。因此，除了在邊結點中增加一個標誌域外，鄰接多重表所需的存儲量和鄰接表相同。在鄰接多重表上，各種基本操作的實現亦和鄰接表相似。 ^[4]