6.1 图的基本概念用 $G=(V,E)$ 描述一张图，但程序不能只停留在集合符号上。面对同一批顶点与边，不同存储结构会让“判断两点是否相邻”“枚举全部邻居”等操作产生完全不同的成本。

本节比较三种表示：

• 邻接矩阵：为每一对顶点预留位置；
• 邻接表：只保存真实存在的邻接关系；
• 边集数组：把边逐条排列，不额外按顶点组织。

真正需要掌握的不是孤立地背复杂度，而是下面这条因果链：

图的规模与高频操作 → 存储方式 → 单次操作成本 → 整个算法的复杂度。

学习目标

完成本节后，你应该能够：

• 根据边集手写无向图与有向图的邻接矩阵、邻接表；
• 用 C++ 实现邻接矩阵与邻接表的增、删、查、遍历；
• 正确处理无向边、零权边、重边和自环的存储语义；
• 比较三种表示的空间、相邻查询、增删边与邻居遍历成本；
• 在邻接矩阵、邻接表和边集数组之间转换；
• 根据图的稠密度与操作模式选择存储；
• 解释为什么同一个 DFS/BFS 会因存储方式不同而具有不同复杂度。

本节使用的例图

继续使用 6.1 的简单无向图：

      0 ───── 1 ───── 3
       \      /        |
        \    /         |
          2 ────────── 4

example-graph.txt

$$V=\{0,1,2,3,4\},$$$$E=\{\{0,1\},\{0,2\},\{1,2\},\{1,3\},\{2,4\},\{3,4\}\}.$$

它有 $n=5$ 个顶点和 $m=6$ 条逻辑边。后面三种结构表达的都是这同一张图。

逻辑边不等于存储记录

无向边 $\{u,v\}$ 通常需要让 $u$ 找到 $v$，也需要让 $v$ 找到 $u$。邻接表因此会保存两条邻接记录，但图论边数 $m$ 仍只计一条。

邻接矩阵：把所有点对排成表

邻接矩阵为每一对顶点 $(i,j)$ 分配一个单元。无权图中，最常见的约定是：

$$A[i][j]=\{\begin{array}{ll}1,& (i,j)\in E,\\ 0,& (i,j)\notin E.\end{array}$$

例图的邻接矩阵为：

$A$	$0$	$1$	$2$	$3$	$4$
$0$	0	1	1	0	0
$1$	1	0	1	1	0
$2$	1	1	0	0	1
$3$	0	1	0	0	1
$4$	0	0	1	1	0

从矩阵可以直接读出三个结构：

1. A[1][3] = 1，所以顶点 $1$ 与 $3$ 相邻；
2. 第 $2$ 行有三个 1，所以 $\mathrm{deg}(2)=3$；
3. 矩阵关于主对角线对称，因为无向边同时满足 A[u][v] = A[v][u] = 1。

有向图则不要求对称：第 $i$ 行表示从 $i$ 出发的边，第 $j$ 列表示指向 $j$ 的边。因此第 $i$ 行的非零项数是出度，第 $j$ 列的非零项数是入度。

带权矩阵怎样表示“没有边”

带权图不能简单地令 0 表示没有边，因为权重 $0$ 可能合法存在。更稳妥的做法是把“是否存在”和“权值是多少”分开，例如使用 std::optional：

#include <cstddef>
#include <optional>
#include <utility>
#include <vector>

using Vertex = std::size_t;
using Weight = long long;

class GraphMatrix {
public:
    GraphMatrix(std::size_t n, bool directed)
        : directed_(directed), matrix_(n, std::vector<std::optional<Weight>>(n)) {}

    std::size_t size() const { return matrix_.size(); }

    void addEdge(Vertex u, Vertex v, Weight weight = 1) {
        matrix_.at(u).at(v) = weight;
        if (!directed_) matrix_.at(v).at(u) = weight;
    }

    void removeEdge(Vertex u, Vertex v) {
        matrix_.at(u).at(v).reset();
        if (!directed_) matrix_.at(v).at(u).reset();
    }

    bool adjacent(Vertex u, Vertex v) const {
        return matrix_.at(u).at(v).has_value();
    }

    std::optional<Weight> weight(Vertex u, Vertex v) const {
        return matrix_.at(u).at(v);
    }

    std::vector<std::pair<Vertex, Weight>> neighbors(Vertex u) const {
        const auto& row = matrix_.at(u);
        std::vector<std::pair<Vertex, Weight>> result;
        for (Vertex v = 0; v < row.size(); ++v)
            if (row[v].has_value()) result.push_back({v, *row[v]});
        return result;
    }

private:
    bool directed_;
    std::vector<std::vector<std::optional<Weight>>> matrix_;
};

adjacency-matrix.cpp

这份实现用 at 检查顶点下标；无向图添加和删除边时同步修改两个对称位置。若同一条边被再次添加，新权重会覆盖旧权重，因此它表达的是简单带权图，而不是保留全部平行边的多重图。

邻接矩阵与距离矩阵不是一回事

图的邻接矩阵中，对角线是否有值取决于是否真的存在自环；“没有边”应保持为空。Floyd 等最短路算法使用的距离矩阵通常把 $d(i,i)$ 初始化为 $0$，那表示“从自己到自己的空路径长度为 0”，不是凭空添加了一条自环。

邻接矩阵的成本

• 空间始终为 $\mathrm{\Theta }(n^2)$；
• 查询、添加、删除指定边都是 $\mathrm{\Theta }(1)$；
• 枚举一个顶点的邻居必须扫描整行，为 $\mathrm{\Theta }(n)$；
• 枚举整张图的邻接关系需要扫描整个矩阵，为 $\mathrm{\Theta }(n^2)$。

无向矩阵只需保存上三角或下三角就能压缩接近一半空间，但换来的代价是更复杂的索引计算；渐近空间仍是 $\mathrm{\Theta }(n^2)$。

连续内存也是优势

矩阵不仅查询快，按行扫描还具有较好的缓存局部性。图较稠密或 $n$ 很小时，即使渐近复杂度相同，连续数组也可能比大量小型邻接容器更快。

邻接表：只保存真实存在的边

邻接表为每个顶点维护一个列表，只记录它实际连向哪些顶点。例图可以写成：

0: 1, 2
1: 0, 2, 3
2: 0, 1, 4
3: 1, 4
4: 2, 3

adjacency-list.txt

所有列表长度之和为 $12=2m$。若换成有向图，通常只保存出边，此时所有列表长度之和就是 $m$。

C++ 实现

下面使用动态数组保存每个顶点的邻接记录。代码假设输入没有重复边；若重复调用 addEdge(u,v)，列表中也会出现重复记录。

#include <algorithm>
#include <cstddef>
#include <vector>

using Vertex = std::size_t;
using Weight = long long;

struct Edge {
    Vertex to;
    Weight weight;
};

class GraphList {
public:
    GraphList(std::size_t n, bool directed)
        : directed_(directed), adjacency_(n) {}

    std::size_t size() const { return adjacency_.size(); }

    void addEdge(Vertex u, Vertex v, Weight weight = 1) {
        adjacency_.at(u).push_back({v, weight});
        if (!directed_) adjacency_.at(v).push_back({u, weight});
    }

    bool adjacent(Vertex u, Vertex v) const {
        const auto& edges = adjacency_.at(u);
        return std::any_of(edges.begin(), edges.end(),
                           [v](const Edge& edge) { return edge.to == v; });
    }

    void removeEdge(Vertex u, Vertex v) {
        eraseTo(u, v);
        if (!directed_) eraseTo(v, u);
    }

    const std::vector<Edge>& neighbors(Vertex u) const {
        return adjacency_.at(u);
    }

private:
    void eraseTo(Vertex u, Vertex v) {
        auto& edges = adjacency_.at(u);
        edges.erase(std::remove_if(edges.begin(), edges.end(),
                                   [v](const Edge& edge) { return edge.to == v; }),
                    edges.end());
    }

    bool directed_;
    std::vector<std::vector<Edge>> adjacency_;
};

adjacency-list.cpp

邻接表的核心优势是：访问 neighbors(u) 时，拿到的全都是真实边，不必为不存在的点对付出扫描成本。

邻接表的成本

设 ${\mathrm{deg}}^{+}(u)$ 为有向图中 $u$ 的出度：

• 空间为 $\mathrm{\Theta }(n+m)$；无向图保存约 $2m$ 条记录，渐近量级不变；
• 枚举 $u$ 的邻居为 $\mathrm{\Theta }({\mathrm{deg}}^{+}(u))$；
• 动态数组尾部添加边的摊还成本为 $O(1)$；
• 查询或删除指定边最坏为 $O({\mathrm{deg}}^{+}(u))$；
• 扫描全图所有顶点和邻接记录为 $\mathrm{\Theta }(n+m)$。

无向图删除 $\{u,v\}$ 时还要扫描 $v$ 的列表，所以更精确地说，成本是 $O(\mathrm{deg}(u)+\mathrm{deg}(v))$。

WARN易错点 · 无向边只存一边

若添加无向边时只执行 adjacency[u].push_back(v)，从 $u$ 能找到 $v$，从 $v$ 却找不到 $u$，后续遍历会把一张无向图当成有向图。除非使用专门的边对象与索引，否则无向邻接表必须同步记录两个方向。

WARN易错点 · 邻居顺序不是图的性质

邻接表中边的插入顺序会影响 DFS/BFS 的访问顺序。若题目要求按顶点编号访问，应在建图后排序；排序全部邻接表的总成本可写为

$$O(\sum _{u\in V}\mathrm{deg}(u)\log \mathrm{deg}(u)),$$

简单上界为 $O(m\log n)$。排序只改变遍历顺序，不改变图本身。

查询很多，遍历也很多怎么办

动态数组邻接表擅长遍历，却不擅长反复判断指定边。可以把每个列表换成或配上哈希集合：

• 指定边查询的期望时间接近 $O(1)$；
• 仍只保存真实边；
• 代价是更高的内存和常数、较差的缓存局部性，以及不稳定的遍历顺序。

工程中常采用“邻接数组作为单一事实来源 + 热点顶点附加哈希索引”的混合方案。此时必须明确谁负责更新，避免数组与索引内容不一致。

边集数组：按边逐条保存

还有一种极简表示：不按顶点组织邻居，只把每条边依次存下来。

#include <cstddef>
#include <vector>

struct EdgeRecord {
    std::size_t from;
    std::size_t to;
    long long weight;
};

std::vector<EdgeRecord> edges = {
    {0, 1, 2},
    {0, 2, 5},
    {1, 2, 1},
    {1, 3, 4},
    {2, 4, 3},
    {3, 4, 2},
};

edge-list.cpp

边集数组占 $\mathrm{\Theta }(m)$ 空间，完整扫描所有边很自然；但寻找某个顶点的全部邻居最坏需要扫描全部 $m$ 条边。它特别适合“算法每轮本来就要看所有边”的场景，例如 Kruskal 按权重排序边、Bellman-Ford 反复松弛全部边。

一张图可以有多个视图

邻接矩阵、邻接表和边集数组不是互斥的理论阵营。工程系统可以维护一种主存储，并按算法需要临时生成另一种视图；关键是把转换成本和同步责任算进去。

三种表示的复杂度对比

下表默认：邻接表使用动态数组，边集数组无额外索引。

操作	邻接矩阵	邻接表	边集数组
空间	$\mathrm{\Theta }(n^2)$	$\mathrm{\Theta }(n+m)$	$\mathrm{\Theta }(m)$
判断 u → v	$\mathrm{\Theta }(1)$	$O({\mathrm{deg}}^{+}(u))$	$O(m)$
枚举 u 的邻居	$\mathrm{\Theta }(n)$	$\mathrm{\Theta }({\mathrm{deg}}^{+}(u))$	$\mathrm{\Theta }(m)$
添加边	$\mathrm{\Theta }(1)$	摊还 $O(1)$	摊还 $O(1)$
删除指定边	$\mathrm{\Theta }(1)$	$O({\mathrm{deg}}^{+}(u))$	$O(m)$
扫描全部边/邻接关系	$\mathrm{\Theta }(n^2)$	$\mathrm{\Theta }(n+m)$	$\mathrm{\Theta }(m)$
典型用途	稠密图、频繁点对查询	稀疏图、遍历与搜索	按边排序、全边松弛

复杂度表不是脱离实现的绝对真理。例如邻接表改用有序数组后可以二分查询，但插入与删除会搬移元素；改用哈希集合后查询期望 $O(1)$，却牺牲顺序与内存。回答复杂度问题时，应同时说清楚容器类型。

表示如何改变算法复杂度

以“访问每个顶点，并检查它的所有邻居”为例：

邻接矩阵

每访问一个顶点都要扫描长度为 $n$ 的整行。即使这一行只有两条真实边，也必须检查其余 $n-2$ 个零：

$$\underset{\text{顶点数}}{\underbrace{n}}\times \underset{\text{每行扫描}}{\underbrace{n}}=\mathrm{\Theta }(n^2).$$

邻接表

每个顶点只扫描自己的真实出边。把所有列表长度加起来：有向图为 $m$，无向图为 $2m$，再加上初始化和访问顶点的 $n$：

$$\mathrm{\Theta }(n+m).$$

O(·)复杂度 · DFS/BFS 必须注明图的表示

同样的 DFS/BFS 控制逻辑：

• 邻接矩阵实现为 $\mathrm{\Theta }(n^2)$；
• 邻接表实现为 $\mathrm{\Theta }(n+m)$。

所以“DFS/BFS 是 $O(n+m)$”隐含了使用邻接表或等价稀疏结构的前提。

这个差距在稀疏图上尤其明显。若 $n=10000$、$m=20000$，矩阵要检查约 ${10}^8$ 个单元；邻接表只需处理 ${10}^4$ 个顶点与数量级为 ${10}^4$ 的边记录。

表示之间怎样转换

邻接表转邻接矩阵

1. 分配 $n\times n$ 的空矩阵；
2. 枚举每个顶点 $u$ 的每条邻接记录 $(u,v,w)$；
3. 设置 matrix[u][v] = w。

初始化矩阵已经需要 $\mathrm{\Theta }(n^2)$ 时间与空间，随后写入边为 $\mathrm{\Theta }(m)$，总成本为 $\mathrm{\Theta }(n^2+m)=\mathrm{\Theta }(n^2)$。

邻接矩阵转邻接表

必须检查矩阵的每个单元；遇到存在的边才加入列表，因此时间为 $\mathrm{\Theta }(n^2)$，生成的邻接表空间为 $\mathrm{\Theta }(n+m)$。

邻接表转边集数组

有向图直接输出每条邻接记录即可。对于不含自环的无向图，如果每条逻辑边恰好保存为 $(u,v)$ 与 $(v,u)$ 两条邻接记录，可以只在 u < v 时输出，从而避免重复。若允许自环，u < v 会丢弃 $(u,u)$；更稳妥的做法是在建图时为每条逻辑边分配唯一的 edgeId，让同一条边的邻接记录共享该编号，转换时只输出尚未处理过的 edgeId。这样也能同时保留自环与平行边。扫描时间仍为 $\mathrm{\Theta }(n+m)$，并需要 $\mathrm{\Theta }(m)$ 的边标记空间。

转换可能丢失语义

若矩阵每个单元只保存一个权重，多重图中的平行边在转成矩阵时会被覆盖。转换前必须决定保留最小权、最后一次权重、边数，还是完整权重列表。

怎样选择表示

不要只背“稠密矩阵、稀疏邻接表”。先回答三个问题：

1. 规模与密度：$n$、$m$ 大约是多少？$m$ 是否接近 $n^2$？
2. 高频操作：主要是查询任意点对、枚举邻居，还是扫描全部边？
3. 更新模式：图几乎只读，还是边频繁增删？是否要求稳定的邻居顺序？

场景	推荐起点	原因
边数接近 $n^2$，频繁查询任意两点	邻接矩阵	点对查询 $O(1)$，稠密时空间浪费较小
大规模稀疏图，频繁 DFS/BFS	邻接表	只存真实边，完整遍历 $O(n+m)$
顶点很少，需要实现简单	邻接矩阵	代码直接，常数与维护成本低
Kruskal、Bellman-Ford 等按边处理	边集数组	排序或全边扫描最自然
邻居要按编号稳定输出	排序后的邻接表	遍历顺序可复现
既常枚举邻居，又常查指定边	邻接表 + 哈希索引	用额外空间同时优化两类操作
静态超大图，强调紧凑与连续访问	CSR 等压缩邻接结构	减少对象开销并改善缓存局部性

一个数量级判断

若 $n=10000$，矩阵共有 ${10}^8$ 个单元：即使每格只占 $1$ 字节，也约需 $95$ MiB；若每格保存 4 字节整数，则约需 $381$ MiB。若图只有 $m=20000$ 条无向边，邻接表只需保存约 $40000$ 条邻接记录，数量级差距非常明显。

反过来，若 $n=200$ 且算法反复做全源最短路，${200}^2=40000$ 个矩阵单元完全可控；矩阵的直接索引和连续内存反而更合适。

常见错误清单

WARN易错点 · 把零权边当成无边

带权图中 weight = 0 可能合法。应使用 optional、独立存在位或明确且不会与合法权值冲突的哨兵。

WARN易错点 · 混淆 $m$ 与邻接记录数

无向邻接表通常有 $2m$ 条记录，但逻辑边数仍是 $m$。Kruskal 若直接读取全部记录，还需要去重。

WARN易错点 · 用行和计算带权图的度

无权 0/1 矩阵的行和等于度；带权矩阵的行和是权重和，不是边数。计算度应统计“存在的单元个数”。允许自环时，还必须按图论定义处理自环对度的两次贡献。

WARN易错点 · 忘记输入是否允许重边

邻接表直接 push_back 会保留重复边；单值矩阵会覆盖旧边。两种实现对同一份含重边输入可能得到不同结果，必须先定义语义。

WARN易错点 · 只看密度，不看操作

稀疏图若要每秒进行大量任意点对查询，也可能需要哈希索引；稠密图若主要按边流式处理，也可能保留边集数组。表示选择最终服务于操作，而不是服务于标签。

小结

• 邻接矩阵用 $\mathrm{\Theta }(n^2)$ 空间换取指定边 $O(1)$ 查询。
• 邻接表用 $\mathrm{\Theta }(n+m)$ 空间保存真实边，适合邻居枚举与稀疏图遍历。
• 边集数组适合排序全部边或反复扫描全部边。
• 无向边在邻接表中通常保存两条记录，但逻辑边数仍为 $m$。
• 算法复杂度依赖表示：邻接矩阵上的 DFS/BFS 是 $\mathrm{\Theta }(n^2)$，邻接表上是 $\mathrm{\Theta }(n+m)$。
• 选择表示时，应同时考虑规模、密度、高频操作、更新方式和顺序要求。

练习与自测

1. 从边集写出两种表示

对无向图

$$V=\{0,1,2,3\},E=\{\{0,1\},\{0,3\},\{1,2\}\},$$

写出它的邻接矩阵与邻接表。

点击展开答案

邻接矩阵为：

	$0$	$1$	$2$	$3$
$0$	0	1	0	1
$1$	1	0	1	0
$2$	0	1	0	0
$3$	1	0	0	0

邻接表为 0: 1,3、1: 0,2、2: 1、3: 0。

2. 为什么矩阵不适合大规模稀疏图

有 $n=100000$ 个顶点、$m=300000$ 条有向边。比较邻接矩阵与邻接表的存储单元数量级。

点击展开答案

邻接矩阵需要 $n^2={10}^{10}$ 个单元，与实际边数无关；邻接表需要 $n$ 个列表头和 $m=3\times {10}^5$ 条出边记录，即 $\mathrm{\Theta }(n+m)$。两者相差约五个数量级，邻接表明显更合适。

3. 解释遍历复杂度

为什么邻接表上的 BFS 是 $O(n+m)$，而邻接矩阵上的 BFS 是 $O(n^2)$？

点击展开答案

BFS 中每个顶点至多入队一次。邻接表只扫描该顶点真实存在的邻接记录，所有列表长度总和为 $m$（无向图为 $2m$），因此总计 $O(n+m)$。邻接矩阵对每个出队顶点都要扫描长度为 $n$ 的整行，共 $n$ 行，所以是 $O(n^2)$。

4. 选择合适的表示

分别为以下任务选择主要表示，并说明理由：

1. 对 $n=150$ 的稠密图运行 Floyd；
2. 对百万顶点道路网反复枚举邻居；
3. 对全部边按权重排序后运行 Kruskal；
4. 稀疏社交图中既要遍历好友，又要频繁判断两人是否直接认识。

点击展开答案

1. 邻接矩阵：规模可控，Floyd 本身就使用距离矩阵；
2. 邻接表或 CSR：道路网通常稀疏，只扫描真实道路；
3. 边集数组：可直接按权重排序；
4. 邻接表加哈希索引：邻接表负责遍历，哈希索引加速指定边查询。

5. 找出建图错误

下面代码想添加无向边，有什么问题？

void addEdge(int u, int v) {
    graph[u].push_back(v);
}

点击展开答案

它只保存了 u → v，没有保存 v → u。应再执行 graph[v].push_back(u)。否则从不同起点遍历时会得到不一致的可达关系，实际存成了有向图。

6. 思考多重图

若顶点 $u,v$ 之间有三条权重分别为 $8,3,5$ 的平行边，单值邻接矩阵应该保存什么？

点击展开答案

没有唯一答案，取决于任务语义：最短路前处理可以只保存最小权 $3$；统计边数时应保存数量 $3$；需要还原全部原始边时则必须让单元保存权重列表，或改用邻接表/边集数组。关键不是选出一个“标准值”，而是先定义转换是否允许丢失信息。

实践入口

完成概念学习后，可以先进入 Lab 06-T-02：图的存储结构选择题精练巩固表示与复杂度；再完成 Lab 06-E-02：连通三元组的最小度数，用邻接矩阵判断三个顶点是否两两相邻；最后完成 Lab 06-E-03：不邻接植花，用邻接表枚举真实邻居，并利用最大度数条件构造确定性的选花方案。

下一章继续学习 7.1 图的遍历：DFS 与 BFS，观察同一套遍历逻辑如何在不同图表示上产生不同复杂度。

参考资料

• 严蔚敏《数据结构》（C 语言版）：图的存储结构；
• 王道《数据结构》考研复习指导：图的存储；
• 《算法导论》：第 22 章基本的图算法。