图的存储：边列表、邻接表与邻接矩阵

“顶点 0 能直接到哪里？”和“0 到 2 有没有边？”看起来很接近，却可能需要完全不同的扫描。边列表要在所有边里找，邻接表只查顶点 0 的那一组，邻接矩阵则能直接读一个格子。先确定算法反复要问什么，再选择存储方式；数据结构总览也是按操作来组织选择的。

顶点、边，以及需要回答的问题

Open Data Structures 的图章节把有向图定义为 $G=(V,E)$：$V$ 是顶点集合，$E$ 中的每条边是一个有序顶点对 $(u,v)$，表示从 $u$ 指向 $v$。这里记 $n=|V|$、$m=|E|$，用整数 0..n-1 标识顶点。

无向边连接两个端点，交换端点不改变这条边；有向边则要区分 u→v 和 v→u。加权图还给每条边一个权重，如长度或费用。无权图只记录是否相连。权重可以为零，所以“没有边”和“有一条权重为零的边”必须分开表示。

一个存储方案通常需要支持：枚举所有顶点与所有边，枚举某个顶点的出邻居，查找某条边及其权重，以及插入、删除边。有向图还可能需要入邻居。顶点集合要单独保留：只看边的端点，找不到没有任何关联边的孤立顶点。

还要约定重复的端点对意味着什么。简单图不含自环或平行边；允许这些边时，可以为每条边保留独立记录。一个矩阵格子只存一个权重，无法同时保留多条平行边及其身份。下面的例子允许自环，但把同一有向端点对的重复输入合并为最小权重；它不是保留所有边的多重图。

同一张图，三种表示

取顶点 0, 1, 2, 3，边为 0→1:4、0→2:0、1→2:2、2→2:5。顶点 3 孤立，顶点 2 有一个自环。

边列表把 (起点, 终点, 权重) 放在一个数组里。邻接表为每个顶点保留一组出边；加权时用 (邻居, 权重)。邻接矩阵用起点作行、终点作列。教材用布尔值表示边是否存在；本例把有边的格子改为权重，把无边的格子设为 None。

起点／行	边列表中的记录	邻接表 adj[u]	矩阵行，列顺序为 0, 1, 2, 3
0	(0,1,4), (0,2,0)	[(1,4), (2,0)]	[None, 4, 0, None]
1	(1,2,2)	[(2,2)]	[None, None, 2, None]
2	(2,2,5)	[(2,5)]	[None, None, 5, None]
3	无记录	[]	[None, None, None, None]

表中为方便比较，按起点展示边列表；实际存储仍是一个数组，没有按起点查找的索引。这张图有 $n=4$、$m=4$：边列表存 4 条边记录，邻接表有 4 个列表和共 4 个邻接项，矩阵分配 $4^2=16$ 个格子，其中 4 个有边。这里数的是记录和格子，不是字节。

查询顶点 0 的全部出邻居，边列表检查 4 条记录，邻接表读取 2 个邻接项，矩阵扫描一行的 4 个格子。三者都得到 [(1,4), (2,0)]。查询 0→2 的权重得到 0；查询 2→0 得到 None。矩阵查询存在性必须用 is not None，不能用权重的真假值。

无向图的邻接表通常把每条非自环边存两次：adj[u] 中有 (v,w)，adj[v] 中有 (u,w)；矩阵对应的两个格子也相同。边列表可以每条无向边只存一次，但找邻居时要检查两端。下面的构建函数对无向自环只存一个邻接项；按图论中的度数约定，自环仍贡献 2，不能直接用列表长度代替度数。

操作成本取决于容器和约定

以下比较固定顶点集合上的边操作：边列表和邻接表内部都用未排序的动态数组，矩阵每格存一个权重或无边标记，索引、权重比较和移动一项都按常数成本计。令 $d^+(u)$ 为顶点 $u$ 存储的出邻接项数。表中加 1 是为了包含空图、空列表时的常数开销；除追加外，时间列给出最坏情况上界。

操作	边列表	邻接表	邻接矩阵
总空间，含顶点集合	$\Theta(n+m)$	$\Theta(n+m)$	$\Theta(n^2+n)$
枚举 u 的全部出邻居	$O(m+1)$	$O(d^+(u)+1)$	$O(n+1)$
查找 u→v 或其权重	$O(m+1)$	$O(d^+(u)+1)$	$O(1)$
追加一条边，不检查重复	摊还 $O(1)$	摊还 $O(1)$	$O(1)$ 写入／覆盖
按端点查找并删除边	$O(m+1)$	$O(d^+(u)+1)$	$O(1)$

矩阵的空间对非空图通常写成 $\Theta(n^2)$；表中的额外 $n$ 也计入了顶点记录。边列表的边记录本身只占 $\Theta(m)$，加上独立顶点集合才能保留孤立顶点。动态数组的摊还追加与删除移位，见数组与动态数组。一次扩容仍可能复制整个数组。

“追加不检查重复”不能当作唯一边更新的成本。若插入前要检查端点对、合并权重或拒绝重复，边列表和普通邻接表还要付出查找成本。无向邻接表删除非自环边还需处理两端，成本为 $O(d(u)+d(v)+1)$。矩阵插入只会覆盖一个端点对的值，不能追加一条独立平行边。

若每个邻接容器改为以邻居为键的哈希表，查找、更新和删除在合适哈希与受控负载下可以有期望 $O(1)$ 成本，扩容另需摊还分析；遍历则还涉及桶和容量，见哈希表。这与表中的线性列表不是同一种成本约定。有向图若只存出邻接表，找入邻居需要扫描全部列表，花费 $O(n+m)$；额外保留反向邻接表可以按入边数枚举，但每次更新必须维护两份记录。

当 $m$ 远小于 $n^2$ 时，邻接表省去大量无边格子。稠密图里两者的空间量级接近，矩阵的直接查边更有吸引力。增加顶点是另一种操作：一个紧凑的矩阵若重新分配并复制，可能花费 $O(n^2)$，不能套用上表的常数写入成本。

从边列表构建：先决定哪些边要保留

下面程序的顶点为 0..n-1，n 是非负整数，权重为整数。输入有 6 条记录，0→1 的权重依次出现 7, 4, 4。合并后保留权重 4，总计 4 条边。这个最小权重规则适合只关心最短路代价的平行边；它会丢掉边的身份和数量，不能用来统计边的重数或直接合并流网络的容量。

构建分为三步：

1. 检查端点属于顶点集合，用端点对作键保存最小权重。有向图保留端点顺序；无向图把较小端点放在前面，因而 (0,1) 和 (1,0) 会合并。
2. 为全部 $n$ 个顶点创建空邻接表，再分配无边矩阵。这样孤立顶点也有位置。
3. 把每条保留的边加入邻接表与矩阵；无向非自环边再补反向记录，自环只加一次。

若原始记录数为 $r$，在哈希操作期望常数时间、动态数组追加摊还常数时间的条件下，归并并构建邻接表需要期望 $O(n+r)$ 时间，临时键表占 $O(m)$ 空间。本程序还构建矩阵，所以总构建时间为期望 $O(n^2+n+r)$。需要保留平行边时，可省略归并、直接追加每条记录；删除指定边则应使用边 ID，普通单权重矩阵也要换成能保存多条边的结构。

CPython 的 dict 用可扩容哈希表实现。上述构建界还假定键的哈希与比较成本固定、哈希分布合适；它不是任意输入下的最坏时间保证。

可运行例子：三种存储回答同样的查询

保存完整代码为 graph_representations.py，用 Python 3.7 或更新版本运行 python3 graph_representations.py。Python 的字典约定从 3.7 起保证插入顺序，更新已有键不会移动它；因此下面的边列表按端点对首次出现的顺序输出。程序分别实现邻居枚举和权重查找，对有向图和无向图的所有顶点对检查结果一致，并检查反向重复边、自环、孤立顶点、空图和越界端点。查询参数使用已声明的顶点。

def build(n, raw_edges, directed=True):
    best = {}
    for u, v, weight in raw_edges:
        if not (0 <= u < n and 0 <= v < n):
            raise ValueError("endpoint outside vertex set")
        key = (u, v) if directed else (min(u, v), max(u, v))
        if key not in best or weight < best[key]:
            best[key] = weight
    edges = [(u, v, weight) for (u, v), weight in best.items()]
    adjacency = [[] for _ in range(n)]
    matrix = [[None] * n for _ in range(n)]
    for u, v, weight in edges:
        adjacency[u].append((v, weight))
        matrix[u][v] = weight
        if not directed and u != v:
            adjacency[v].append((u, weight))
            matrix[v][u] = weight
    return edges, adjacency, matrix


def grid_neighbors(row, column, rows, columns):
    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        r, c = row + dr, column + dc
        if 0 <= r < rows and 0 <= c < columns:
            yield r, c


n = 4
raw_edges = [(0, 1, 7), (0, 2, 0), (0, 1, 4),
             (1, 2, 2), (2, 2, 5), (0, 1, 4)]
edges, adjacency, matrix = build(n, raw_edges)
print("edges:", edges)
print("adjacency:", adjacency)
print("matrix:")
for row in matrix:
    print(row)


def edge_neighbors(edges, u, directed=True):
    neighbors = []
    for source, target, weight in edges:
        if source == u:
            neighbors.append((target, weight))
        elif not directed and target == u:
            neighbors.append((source, weight))
    return neighbors


def list_neighbors(adjacency, u):
    return list(adjacency[u])


def matrix_neighbors(matrix, u):
    return [(v, weight) for v, weight in enumerate(matrix[u])
            if weight is not None]


def edge_weight(edges, u, v, directed=True):
    key = (u, v) if directed else (min(u, v), max(u, v))
    return next((w for a, b, w in edges if (a, b) == key), None)


def list_weight(adjacency, u, v):
    return next((w for b, w in adjacency[u] if b == v), None)


def matrix_weight(matrix, u, v):
    return matrix[u][v]


queries = [(0, 2), (2, 0), (2, 2)]
for name, store, neighbors, weight in [
    ("edge-list", edges, edge_neighbors, edge_weight),
    ("adjacency-list", adjacency, list_neighbors, list_weight),
    ("matrix", matrix, matrix_neighbors, matrix_weight),
]:
    print(name, neighbors(store, 0), neighbors(store, 3),
          [weight(store, u, v) for u, v in queries])
    for u in range(n):
        assert sorted(neighbors(store, u)) == sorted(list_neighbors(adjacency, u))
        for v in range(n):
            assert weight(store, u, v) == matrix[u][v]

undirected = build(3, [(0, 1, 7), (1, 0, 4), (1, 1, 0)], directed=False)
assert undirected == (
    [(0, 1, 4), (1, 1, 0)],
    [[(1, 4)], [(0, 4), (1, 0)], []],
    [[None, 4, None], [4, 0, None], [None, None, None]],
)
u_edges, u_adjacency, u_matrix = undirected
for u in range(3):
    assert sorted(edge_neighbors(u_edges, u, directed=False)) == sorted(
        list_neighbors(u_adjacency, u)) == sorted(matrix_neighbors(u_matrix, u))
    for v in range(3):
        assert edge_weight(u_edges, u, v, directed=False) == list_weight(
            u_adjacency, u, v) == matrix_weight(u_matrix, u, v)
assert build(0, []) == ([], [], [])
try:
    build(2, [(0, 2, 1)])
except ValueError:
    pass
else:
    raise AssertionError("invalid endpoint accepted")
print("boundary checks: OK")
print("grid (0, 1):", list(grid_neighbors(0, 1, 2, 3)))

输出：

edges: [(0, 1, 4), (0, 2, 0), (1, 2, 2), (2, 2, 5)]
adjacency: [[(1, 4), (2, 0)], [(2, 2)], [(2, 5)], []]
matrix:
[None, 4, 0, None]
[None, None, 2, None]
[None, None, 5, None]
[None, None, None, None]
edge-list [(1, 4), (2, 0)] [] [0, None, 5]
adjacency-list [(1, 4), (2, 0)] [] [0, None, 5]
matrix [(1, 4), (2, 0)] [] [0, None, 5]
boundary checks: OK
grid (0, 1): [(1, 1), (0, 0), (0, 2)]

每行的三个查询结果组依次为顶点 0 的出邻居、顶点 3 的出邻居，以及 0→2、2→0、2→2 的权重。代码复制邻接表再返回邻居，所以枚举仍需线性读取这些项；矩阵的 matrix_weight 则直接读取一个格子。

查询无向边列表时，也要传入 directed=False，与 build 保持一致；邻接表和矩阵已经存有反向记录。不同表示的邻居顺序可能不同，因此断言用 sorted 比较邻居及其权重。

隐式图：网格不一定需要存边

程序末尾的 grid_neighbors 把二维网格当作图，按上、下、左、右生成邻居，只保留边界内的格子。这里所有格子都可通行、不允许斜走，也没有跨边界环绕。一个 $2\times3$ 网格有 6 个顶点；横向有 $2(3-1)=4$ 条无向边，纵向有 $(2-1)3=3$ 条，共 7 条。格子 (0,1) 的三个邻居是 (1,1)、(0,0)、(0,2)，与输出一致。

每次最多检查 4 个候选，邻居生成用 $O(1)$ 时间，无需预存这 7 条边。规则网格的尺寸本身只需常数空间；若有障碍，还需存储并检查通行状态。对于 $R$ 行、$C$ 列的网格，BFS／DFS 仍要保存访问状态和队列／栈，最坏可占 $O(RC)$ 空间。隐式表示省掉的是边存储，不会省掉搜索状态。

如果边表示某种合法操作，如拼图的一步移动，也可以按状态计算邻居。此时要把生成、验证一个候选的实际成本计入遍历时间，不能一概视为常数。

现有算法笔记分别假定什么表示

图算法总览按问题选算法；下面按本站笔记中的代码或伪代码解释其存储需求。ODS 的遍历章节也在邻接表假设下分析 BFS／DFS。

笔记	当前使用的表示	为什么需要它
BFS／DFS	顶点到邻居列表的映射，无权邻接表	每次处理一个顶点就枚举其邻居；完整遍历为 $O(n+m)$。矩阵扫描各行会变成 $O(n^2)$，每次扫边列表则为 $O(n(m+1))$。
Dijkstra	(邻居, 权重) 邻接表，加惰性二叉堆	只松弛当前顶点的出边；要求非负权重。笔记中的一般惰性堆界为 $O(n+m\log(m+1))$，简单图可用常见的 $O((n+m)\log n)$ 表达。
Bellman–Ford	独立的 n，以及可重复遍历的 (u,v,w) 边列表	每轮都松弛所有边，不依赖按顶点找邻居；最坏 $O(n+nm)$，非空边集时通常写作 $O(nm)$。
Floyd–Warshall	从边列表初始化距离矩阵	三重循环需要任意顶点对的距离，时间 $O(n^3)$、矩阵空间 $O(n^2)$。
Kruskal	每条无向边一条记录的边列表，另有并查集	先按权重排序，再检查两端是否同属一个分量；含初始化的时间为 $O(n+m\log(m+1))$，无需邻居索引。
Prim	对称加权邻接表，加惰性边堆	新顶点加入树时，把它通向外部的边加入堆；整个森林为 $O(n+m\log(m+1))$。笔记也列出矩阵加线性选择的 $O(n^2)$ 方案。

这里的遍历成本按遍历全部顶点计算，并假定访问标记和映射查询为常数成本；用哈希集合或字典时，这需要相应的期望常数时间条件。只从一个起点搜索时，可按可达顶点和所检查的边计算，但若先分配全部顶点的状态数组，还要计入 $O(n)$ 初始化。惰性堆允许多个旧条目，因此任意多重图上的对数项保留 $\log(m+1)$，不要直接换成 $\log n$。

邻接矩阵和距离矩阵也不能混用。本例 matrix[2][2]=5 表示真的有一条权重 5 的自环；Floyd–Warshall 的距离对角线先设为 0，表示不走边的路径，再与自环权重取最小值。它用无穷大表示无路，并把平行边取最小权重。

本站 BFS／DFS 函数接收顶点到邻居列表的映射。可用 graph = {u: [v for v, _ in outgoing] for u, outgoing in enumerate(adjacency)} 转换本例的加权邻接表，其中空列表仍保留孤立顶点。BFS 求最少边数的路径；DFS 访问可达顶点，但不保证路径的边数最少。两者都忽略权重，不能计算本例的最小加权距离。

我的阅读 · 打开过的笔记会记在当前浏览器里。