线性表描述“一前一后”，树描述“一对多”，图则允许任意两个对象建立关系。社交网络中的关注、地图中的道路、课程之间的先修依赖，都可以抽象成顶点与边。

本节先建立图论的基本语言：什么是有向图与无向图，怎样计算度，路径、环与连通分别描述什么。下一节再回答工程问题——这些顶点与边究竟怎样放进内存。

学习目标

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

• 用 $G=(V,E)$ 描述一张图，并计算顶点数与边数；
• 区分有向图、无向图、带权图与无权图；
• 计算度、入度与出度，并使用握手定理检查结果；
• 区分路径、简单路径、回路、可达与连通；
• 说明无向图的连通分量以及有向图的强、弱连通；
• 根据 $n$ 与 $m$ 判断图大致是稀疏还是稠密；
• 识别自环、重边等需要额外约定的边界情况。

一张贯穿全文的小图

先看一张有 $5$ 个顶点、$6$ 条边的无向图：

      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=|V|=5$，$m=|E|=6$。花括号 $\{u,v\}$ 表示无向边：从 $u$ 可以走到 $v$，从 $v$ 也可以走到 $u$。如果是有向边，则写成有序对 $(u,v)$ 或 $u\to v$。

顶点、边、方向与权重

DEF定义 · 图

图记为 $G=(V,E)$：$V$ 是有限的顶点集，$E$ 是顶点之间的边集。记顶点数为 $n=|V|$，边数为 $m=|E|$。

按边的语义，图可以继续分类：

分类维度	类型	边的含义	例子
是否有方向	无向图	$\{u,v\}$ 不区分方向	双向道路、互为好友
是否有方向	有向图	$(u,v)$ 与 $(v,u)$ 是不同的边	关注关系、课程依赖
是否有数值	无权图	只关心边是否存在	是否认识、是否连通
是否有数值	带权图	每条边带权 $w(u,v)$	距离、时间、费用

“无权”不等于边没有代价。许多算法会把无权图的每条边统一视为权重 $1$，于是路径长度就是经过的边数。

简单图、自环与重边

若一条边从顶点连回自己，例如 $(u,u)$，称为自环。若同一对端点之间允许存在多条边，称为平行边或重边；允许平行边的图称为多重图。

DEF定义 · 简单图

不含自环和重边的图称为简单图。本章的核心示例与代码默认处理简单图；若输入允许自环或重边，必须额外约定度数、边数和存储覆盖规则。

为什么要先声明这个前提？因为同一份输入在不同实现中可能产生不同结果：邻接表直接追加会保留重边，单值邻接矩阵则可能用新权重覆盖旧权重。算法开始前必须先定义语义。

邻接与度

若边 $\{u,v\}$ 存在，则无向图中的 $u$ 与 $v$ 相邻。顶点 $u$ 的度 $\mathrm{deg}(u)$ 是与它关联的边数。

贯穿例图中：

顶点	邻居	度
$0$	$1,2$	$2$
$1$	$0,2,3$	$3$
$2$	$0,1,4$	$3$
$3$	$1,4$	$2$
$4$	$2,3$	$2$

度数总和为 $2+3+3+2+2=12=2m$。原因很直接：每条无向边在两个端点处各贡献一次度数。

PROP性质 · 握手定理

对任意无向图，

$$\sum _{v\in V}\mathrm{deg}(v)=2m.$$

因此奇数度顶点的个数必为偶数。若允许自环，一条自环在同一顶点处贡献两次度数，等式仍然成立。

有向图的入度与出度

有向边 $(u,v)$ 从 $u$ 指向 $v$：

• 出度 ${\mathrm{deg}}^{+}(u)$：从 $u$ 出发的边数；
• 入度 ${\mathrm{deg}}^{-}(v)$：指向 $v$ 的边数。

每条有向边恰好贡献一次出度和一次入度，所以

$$\sum _{v\in V}{\mathrm{deg}}^{+}(v)=\sum _{v\in V}{\mathrm{deg}}^{-}(v)=m.$$

WARN易错点 · 有向图不能只说“度”

有向图中必须说明讨论的是入度、出度，还是两者之和。顶点的出度为 $0$ 不代表它与图无关：它仍可能有许多入边。

路径、回路与可达

DEF定义 · 路径与可达

从 $v_0$ 到 $v_k$ 的路径是一个顶点序列

$$v_0,v_1,\dots ,v_k,$$

其中每对相邻顶点之间都有边；有向图还必须遵守边的方向。若存在从 $u$ 到 $v$ 的路径，就称 $v$ 从 $u$ 可达。顶点不重复的路径称为简单路径；起点与终点相同的非空路径形成回路，其中除首尾外不重复顶点的称为简单环。

在例图中：

• $0\to 1\to 3\to 4$ 是从 $0$ 到 $4$ 的一条路径；
• $0\to 2\to 4$ 也是一条路径，而且经过的边更少；
• $0\to 1\to 2\to 0$ 构成一个环；
• 因为存在路径，所以顶点 $4$ 从顶点 $0$ 可达。

带权图中，路径长度通常指沿途边权之和；无权图中，路径长度通常指经过的边数。最短路径算法将在第 7 章展开，本节只需要先明确“路径是否合法”。

WARN易错点 · 有向边不能逆着走

若有向图只有 $u\to v$，则 $v$ 从 $u$ 一步可达，但不能据此推出 $u$ 从 $v$ 可达。无向图中的可达关系是对称的，有向图中的可达关系通常不是。

连通与连通分量

DEF定义 · 无向图的连通

无向图中，若任意两个顶点之间都存在路径，就称图连通。若整张图不连通，则每个“内部互相可达、再也无法扩张”的最大顶点集合称为一个连通分量。

贯穿例图只有一个连通分量，因此整图连通。如果再加入一个没有任何边的顶点 $5$，那么顶点集合会分成 $\{0,1,2,3,4\}$ 与 $\{5\}$ 两个连通分量；孤立顶点自己也构成一个分量。

有向图需要区分：

• 忽略边的方向后连通，称为弱连通；
• 任意两点 $u,v$ 都同时满足 $u$ 可达 $v$、$v$ 可达 $u$，称为强连通。

例如只有两条边 $0\to 1$、$1\to 2$ 的图，忽略方向后是连通的，所以它弱连通；但 $2$ 无法回到 $0$，所以它不强连通。

存下来不等于判断出来

存储结构只记录“哪些边存在”，不会自动告诉我们图是否连通。判断连通分量需要在表示之上运行 DFS 或 BFS；有向图的强连通分量还需要专门算法。

稀疏与稠密

在不含自环的简单图中：

• 无向图最多有 $\frac{n(n-1)}{2}$ 条边；
• 有向图最多有 $n(n-1)$ 条边。

DEF定义 · 稀疏图与稠密图

当 $m$ 远小于 $n^2$ 时，通常称图稀疏；当 $m$ 与 $n^2$ 同数量级时，称图稠密。

“稀疏”和“稠密”不是非黑即白的严格标签，而是帮助估算存储成本的尺度。道路网络、网页链接通常很稀疏；规模较小的全连接关系或距离表则可能接近稠密。

贯穿例图中 $n=5$，简单无向图最多有 $5\times 4/2=10$ 条边，实际有 $6$ 条。对这样的小图，两种主要存储都很轻量；当 $n$ 增长到数万或数百万时，$m$ 与 $n^2$ 的差距才会直接决定能否放进内存。

从概念走向存储

目前我们一直用集合写图：$V$ 保存顶点，$E$ 保存边。这种数学表示很精确，却没有回答程序怎样高效完成下面的操作：

1. 判断 $u$ 与 $v$ 是否相邻；
2. 枚举 $u$ 的全部邻居；
3. 添加或删除一条边；
4. 扫描整张图的全部边。

6.2 图的存储结构将比较邻接矩阵、邻接表与边集数组。它们表达的是同一张图，但会让上述操作具有不同成本。

小结

• 图 $G=(V,E)$ 用顶点表示对象，用边表示对象之间的关系。
• 边可以有方向与权重；简单图不含自环和重边。
• 无向图满足度数和为 $2m$；有向图的入度和、出度和都等于 $m$。
• 路径描述怎样沿边到达，环是回到起点的非空路径。
• 无向图讨论连通分量；有向图还要区分弱连通与强连通。
• $m$ 远小于 $n^2$ 时图通常稀疏；$m$ 与 $n^2$ 同数量级时图通常稠密。
• 这些结构特征会直接影响下一节的存储选择。

练习与自测

1. 检查度数

无向图有

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

求每个顶点的度，并用握手定理检查结果。

点击展开答案

度数依次为 $2,2,1,1$，总和为 $6$。因为 $m=3$，握手定理给出 $2m=6$，两者一致；奇数度顶点 $2,3$ 共有两个，也是偶数。

2. 计算入度与出度

有向图包含边 $0\to 1$、$0\to 2$、$2\to 1$、$1\to 3$。分别求四个顶点的入度与出度。

点击展开答案

顶点	入度	出度
$0$	0	2
$1$	2	1
$2$	1	1
$3$	1	0

入度和与出度和都为 $4=m$。

3. 自环怎样影响度

无向图有边 $\{0,0\}$ 与 $\{0,1\}$。顶点 $0$ 的度是多少？

点击展开答案

$\mathrm{deg}(0)=3$：自环在顶点 $0$ 处贡献两次度，边 $\{0,1\}$ 再贡献一次。顶点 $1$ 的度为 $1$，度数总和为 $4=2m$。

4. 判断连通性

有向图只有边 $0\to 1$、$1\to 2$、$2\to 1$。它是否弱连通？是否强连通？

点击展开答案

忽略方向后，三个顶点连成一体，所以图弱连通。但顶点 $1$、$2$ 都无法回到 $0$，所以整图不强连通；$\{1,2\}$ 构成一个强连通分量，$\{0\}$ 构成另一个。

5. 最大边数

一个不含自环的简单无向图有 $8$ 个顶点，最多能有多少条边？简单有向图呢？

点击展开答案

简单无向图最多有 $8\times 7/2=28$ 条边；简单有向图把两个方向视为不同边，最多有 $8\times 7=56$ 条边。

下一步

先完成 Lab 06-T-01：图的基本概念选择题精练，检查自己能否独立判断度、路径与连通性；再完成 Lab 06-E-01：图的度数与奇偶性统计，用代码处理无向度数、有向入度与出度、自环和平行边。最后继续学习 6.2 图的存储结构，把顶点与边装进邻接矩阵、邻接表和边集数组。

参考资料

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