儲存圖形（鄰接列表）

鄰接列表是用於表示有限圖的無序列表的集合。每個列表描述圖中頂點的鄰居集。儲存圖形需要較少的記憶體。

讓我們看一個圖表及其鄰接矩陣： http://i.stack.imgur.com/PwJ3D.jpg

現在我們使用這些值建立一個列表。

http://i.stack.imgur.com/WEEcx.jpg

這稱為鄰接列表。它顯示哪些節點連線到哪些節點。我們可以使用 2D 陣列儲存此資訊。但是我們會花費與 Adjacency Matrix 相同的記憶體。相反，我們將使用動態分配的記憶體來儲存這個記憶體。

許多語言都支援 Vector 或 List ，我們可以使用它來儲存鄰接列表。對於這些，我們不需要指定 List 的大小。我們只需要指定最大節點數。

虛擬碼將是：

Procedure Adjacency-List(maxN, E):       // maxN denotes the maximum number of nodes
edge[maxN] = Vector()                    // E denotes the number of edges
for i from 1 to E
    input -> x, y                        // Here x, y denotes there is an edge between x, y
    edge[x].push(y)
    edge[y].push(x)
end for
Return edge

由於這是一個無向圖，它有一條從 x 到 y 的邊，還有一條從 y 到 x 的邊。如果它是有向圖，我們將省略第二個。對於加權圖，我們也需要儲存成本。我們將建立另一個名為 cost []的向量或列表來儲存它們。虛擬碼： ****

Procedure Adjacency-List(maxN, E):
edge[maxN] = Vector()
cost[maxN] = Vector()
for i from 1 to E
    input -> x, y, w
    edge[x].push(y)
    cost[x].push(w)
end for
Return edge, cost

從這一點，我們可以很容易地找出連線到任何節點的節點總數，以及這些節點是什麼。它比 Adjacency Matrix 花費的時間更少。但是如果我們需要找出 u 和 v 之間是否存在優勢，那麼如果我們保留一個鄰接矩陣就會更容易。