存储图形（邻接列表）

邻接列表是用于表示有限图的无序列表的集合。每个列表描述图中顶点的邻居集。存储图形需要较少的内存。

让我们看一个图表及其邻接矩阵： 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 之间是否存在优势，那么如果我们保留一个邻接矩阵就会更容易。