Lecture 20：图基本概念
Chinese-language Computer Science 408 note: Lecture 20：图基本概念. Original source available where applicable.
On this page
This note is currently available in Chinese. The original wording, formulas and diagrams are preserved to avoid an unverified technical translation.
20.1 基本概念
20.1.1 图的定义
定义：#图
描述：图是由顶点集合和边集合组成的一种非线性数据结构，通常记为： $$ G=(V,E) $$
- $G$：Graph，表示一个图。
- $V$：Vertex set，表示顶点集合。
- $E$：Edge set，表示边集合，也可以理解为顶点之间关系的集合。
若： $$ V={v_1,v_2,\cdots,v_n} $$
则：
- $\lvert V\rvert$ 表示图中顶点的个数，也称为图的阶。
- $\lvert E\rvert$ 表示图中边的条数。
- 图中的每一条边都要依附于顶点，边本身不能脱离顶点而存在。
对有向图而言，可能的弧来自顶点的有序对，因此应写成： $$ E\subseteq V\times V $$
无向边则用顶点的无序对表示。这里的“子集”非常重要：它只限定边的端点必须来自 $V$，并不表示任意两个顶点之间必然有边；只有完全图才把所有允许的顶点对都取为边。
易错点：#空图
描述：线性表可以为空表，树可以为空树，但图不允许没有顶点。
- 图的顶点集合 $V$ 必须是非空有限集合。
- 图的边集合 $E$ 可以为空。
- 只有顶点、没有边的图是合法图。
- 没有顶点的结构不能称为图。
因此： $$ V\ne \varnothing $$
但可以有： $$ E=\varnothing $$
基本术语：#图术语
| 符号 | 英文 | 中文 | 说明 |
|---|---|---|---|
| $G$ | Graph | 图 | 整个图结构 |
| $V$ | Vertex | 顶点 | 数据元素本身 |
| $E$ | Edge | 边 | 顶点之间的关系 |
图与线性表、树的区别：
| 结构 | 关系特点 | 前驱后继关系 |
|---|---|---|
| 线性表 | 一对一 | 除表头表尾外，一个直接前驱、一个直接后继 |
| 树 | 一对多 | 一个结点可以有多个孩子，但通常只有一个双亲 |
| 图 | 多对多 | 任意两个顶点之间都可能存在关系 |
20.2 常见图
20.2.1 无向图
定义：#无向图
描述：若图 $G$ 中的每条边都没有方向，则称 $G$ 为无向图。
无向图中的边是一个无序对，记作： $$ (v,w) $$
因为没有方向，所以： $$ (v,w)=(w,v) $$
在无向图中：
- 若边 $(v,w)$ 存在，则称顶点 $v$ 和顶点 $w$ 相邻。
- 边 $(v,w)$ 依附于顶点 $v$ 和顶点 $w$。
- 顶点 $v$ 和顶点 $w$ 是边 $(v,w)$ 的两个端点。
理解：
描述：无向边只表示“两个顶点之间有关系”，不区分关系从谁指向谁。
例如社交网络中的“好友关系”通常可以看作无向关系：
$$ A\text{ 是 }B\text{ 的好友}\Longleftrightarrow B\text{ 是 }A\text{ 的好友} $$
20.2.2 有向图
定义：#有向图
描述：若图 $G$ 中的每条边都有方向，则称 $G$ 为有向图。
有向图中的边也称为弧，用有序对表示： $$ <v,w> $$
其中：
- $v$ 称为弧尾。
- $w$ 称为弧头。
- $<v,w>$ 表示从顶点 $v$ 指向顶点 $w$ 的一条弧。
因为有向边有方向，所以： $$ <v,w>\ne <w,v> $$
在有向图中：
- 若弧 $<v,w>$ 存在，则称 $v$ 邻接到 $w$。
- 也可以说 $w$ 邻接自 $v$。
- $<v,w>$ 与 $<w,v>$ 是两条不同的弧。
理解：
描述：有向边不仅表示两个顶点有关系，还表示这个关系的方向。
例如网页链接关系：
$$ A\text{ 页面链接到 }B\text{ 页面} $$
不代表：
$$ B\text{ 页面也链接到 }A\text{ 页面} $$
20.2.3 简单图
定义：#简单图
描述：若图中不存在重复边，也不存在顶点到自身的边，则称该图为简单图。
简单图需要同时满足：
- 不存在重复边。
- 不存在自回路，即不存在从某个顶点指向自身的边。
无向简单图中不允许： $$ (v,v) $$
有向简单图中不允许： $$ <v,v> $$
易错点：
描述：408 中默认讨论的图一般是简单图，除非题目明确说明允许多重边或自回路。
20.2.4 多重图
定义：#多重图
描述：若图中允许两个顶点之间存在多条边，或允许顶点通过边和自身相关联，则称该图为多重图。
多重图可能出现：
- 两个顶点之间有多条边。
- 顶点到自身有边，也就是自回路。
与简单图相比，多重图的限制更少。
NOTE · 术语口径 有些教材把“允许平行边”称为多重图，把“还允许自环”另称伪图；本 PDF 将两者统一放在多重图下。做题时以题目给出的定义为准，但简单图始终不允许平行边和自环。
图示说明
- 蓝色两图分别是简单无向图、简单有向图；灰色两图用红线标出了自环和平行边/弧。
- 有向图中方向相反的两条弧不是重复弧，例如 $<A,B>$ 与 $<B,A>$ 可以同时存在于简单有向图。
对比总结：
| 图的类型 | 边是否有方向 | 是否允许重复边 | 是否允许自回路 |
|---|---|---|---|
| 简单无向图 | 无方向 | 不允许 | 不允许 |
| 简单有向图 | 有方向 | 不允许 | 不允许 |
| 多重无向图 | 无方向 | 可以允许 | 可以允许 |
| 多重有向图 | 有方向 | 可以允许 | 可以允许 |
20.3 顶点与度
20.3.1 无向图中顶点的度
定义：#度
描述：无向图中，顶点 $v$ 的度是依附于该顶点的边的条数，记作 $TD(v)$。
其中：
- $TD(v)$ 表示 Total Degree，即总度数。
- 在无向图中，每一条边都会让它的两个端点的度各增加 $1$。
若无向图有 $n$ 个顶点、$e$ 条边，则： $$ \sum_{i=1}^{n}TD(v_i)=2e $$
为什么是 $2e$：
描述：无向边有两个端点，所以统计所有顶点的度时，每条边会被统计两次。
例如一条边 $(v_1,v_2)$：
- 对 $v_1$ 的度贡献 $1$。
- 对 $v_2$ 的度贡献 $1$。
若题目允许无向自环，则一个自环在同一顶点处有两个端点，因此对该顶点的度贡献 $2$；握手定理 $\sum TD(v_i)=2e$ 仍成立。
所以一条边总共贡献 $2$。
20.3.2 有向图中顶点的入度和出度
定义：#入度
描述：有向图中，以顶点 $v$ 为终点的弧的数目称为 $v$ 的入度，记作 $ID(v)$。
定义：#出度
描述：有向图中，以顶点 $v$ 为起点的弧的数目称为 $v$ 的出度，记作 $OD(v)$。
有向图中顶点 $v$ 的总度为： $$ TD(v)=ID(v)+OD(v) $$
若有向图有 $n$ 个顶点、$e$ 条弧，则： $$ \sum_{i=1}^{n}ID(v_i)=\sum_{i=1}^{n}OD(v_i)=e $$
进一步有： $$ \sum_{i=1}^{n}TD(v_i)=2e $$
为什么入度和出度之和都等于 $e$：
描述：每一条有向边都只有一个弧尾和一个弧头。
对一条弧 $<v,w>$：
- 它对顶点 $v$ 的出度贡献 $1$。
- 它对顶点 $w$ 的入度贡献 $1$。
所以：
- 所有顶点的入度之和 = 弧的条数。
- 所有顶点的出度之和 = 弧的条数。
- 若允许有向自环，它对同一顶点的入度和出度各贡献 $1$，上述公式仍成立。
常考判断：
| 图 | 单条边的贡献 | 度数公式 |
|---|---|---|
| 无向图 | 两个端点各加 $1$ | $\sum TD(v_i)=2e$ |
| 有向图 | 一个出度、一个入度 | $\sum ID(v_i)=\sum OD(v_i)=e$ |
| 有向图总度 | 入度加出度 | $\sum TD(v_i)=2e$ |
20.4 路径、距离与连通性
20.4.1 路径
定义：#路径
描述：从顶点 $v_p$ 到顶点 $v_q$ 的路径，是一个顶点序列。
一般写作： $$ v_p,v_{i_1},v_{i_2},\cdots,v_q $$
这个序列表示：
- $v_p$ 到 $v_{i_1}$ 之间有边。
- $v_{i_1}$ 到 $v_{i_2}$ 之间有边。
- 依次类推，最后能到达 $v_q$。
在有向图中，路径还必须满足方向一致。
路径长度：#路径长度
描述：路径长度是路径上边或弧的数目。
如果路径经过的顶点序列为： $$ v_0,v_1,v_2,\cdots,v_k $$
则路径长度为： $$ k $$
因为该路径包含： $$ (v_0,v_1),(v_1,v_2),\cdots,(v_{k-1},v_k) $$
共 $k$ 条边。
20.4.2 回路与简单路径
定义：#回路 #环
描述：若一条长度大于 $0$ 的路径的第一个顶点和最后一个顶点相同，则称该路径为回路，也称为环。
即： $$ v_0=v_k $$
定义：#简单路径
描述：若路径序列中各顶点不重复出现，则称该路径为简单路径。
注意：
- 简单路径不允许顶点重复。
- 简单回路除第一个顶点和最后一个顶点相同外，其余顶点不能重复。
易错点：
描述：路径不一定是简单路径；路径可以重复经过顶点或边，除非题目明确要求简单路径。
20.4.3 点到点的距离
定义：#距离
描述：从顶点 $u$ 到顶点 $v$ 的距离，是 $u$ 到 $v$ 的最短路径长度。
若 $u$ 到 $v$ 之间存在路径，则距离为最短路径上的边数。
若 $u$ 到 $v$ 之间不存在路径，则距离记为： $$ \infty $$
注意：
- 距离强调的是最短路径。
- 路径长度可以有很多种，距离只取其中最小的那一个。
- 对无权图来说，距离就是最少经过几条边。
- 对有权图来说，通常要区分“边数意义下的长度”和“权值意义下的长度”。
- 无向图中 $d(u,v)=d(v,u)$；有向图中受弧方向影响，$d(u,v)$ 与 $d(v,u)$ 可能不同，甚至一个有限而另一个为 $\infty$。
20.4.4 无向图的连通
定义：#连通
描述：无向图中，若顶点 $v$ 到顶点 $w$ 之间存在路径，则称 $v$ 和 $w$ 是连通的。
定义：#连通图
描述：若无向图中任意两个顶点都是连通的，则称该图为连通图。
也就是说，对任意： $$ v,w\in V $$
都存在从 $v$ 到 $w$ 的路径。
常考性质：
描述：对于 $n$ 个顶点的无向图，若它是连通图，则至少需要 $n-1$ 条边。
公式： $$ e_{\min}=n-1 $$
原因：
- 要让 $n$ 个顶点全部连通，最少可以构成一棵树。
- 树有 $n$ 个顶点时，边数为 $n-1$。
- 少于 $n-1$ 条边时，不可能把全部顶点连接成一个整体。
20.4.5 有向图的强连通
定义：#强连通
描述：有向图中，若顶点 $v$ 到顶点 $w$ 有路径，且顶点 $w$ 到顶点 $v$ 也有路径，则称 $v$ 和 $w$ 是强连通的。
即同时满足： $$ v\leadsto w $$
和： $$ w\leadsto v $$
定义：#强连通图
描述：若有向图中任意两个顶点都是强连通的，则称该图为强连通图。
也就是说，对任意两个顶点 $v,w$，都必须满足：
- 从 $v$ 可以到达 $w$。
- 从 $w$ 也可以到达 $v$。
常考性质：
描述：对于 $n\ge 2$ 个顶点的有向图，若它是强连通图，则至少需要 $n$ 条弧。
公式： $$ e_{\min}=n $$
原因：
- 最少可以让所有顶点构成一个有向环。
- 有向环中每个顶点出发都可以沿环到达其他顶点。
- 有向环有 $n$ 个顶点时，弧数为 $n$。
- 当 $n=1$ 时，单个顶点按长度为 $0$ 的路径可达自身，不需要弧也已强连通，因此最少弧数是 $0$。
20.4.6 不连通无向图的最多边数
结论：#不连通图最多边数
描述：若一个 $n\ge 2$ 顶点无向简单图是不连通的，则它最多有 $C_{n-1}^{2}$ 条边。
公式： $$ e_{\max}=C_{n-1}^{2}=\frac{(n-1)(n-2)}{2} $$
为什么这样取最大：
描述：要让图不连通，又让边数尽可能多，就让其中 $n-1$ 个顶点构成完全图，剩下 $1$ 个顶点孤立。
此时：
- $n-1$ 个顶点之间边数达到最大。
- 剩余 $1$ 个顶点不能和它们相连，否则整个图就连通了。
- 所以最多边数是 $n-1$ 个顶点的无向完全图边数。
即： $$ C_{n-1}^{2} $$
题目反推：
描述：若一个 $n$ 顶点无向简单图的边数大于 $C_{n-1}^{2}$，则它一定连通。
写作： $$ e>C_{n-1}^{2}\Longrightarrow G\text{ 一定连通} $$
20.5 子图、连通分量、生成树和生成森林
20.5.1 子图
定义：#子图
描述：设图 $G=(V,E)$ 和图 $G'=(V',E')$，若 $V'\subseteq V$ 且 $E'\subseteq E$，则称 $G'$ 是 $G$ 的子图。
即： $$ V'\subseteq V,\quad E'\subseteq E $$
则： $$ G'\subseteq G $$
注意：
- 子图首先必须是一个图。
- 如果保留了一条边，则这条边依附的两个顶点也必须保留。
- 不能只拿边、不拿边对应的顶点。
20.5.2 生成子图
定义：#生成子图
描述：若子图 $G'$ 包含原图 $G$ 的全部顶点，则称 $G'$ 为 $G$ 的生成子图。
生成子图满足： $$ V(G')=V(G) $$
但边集合可以是原图边集合的子集： $$ E(G')\subseteq E(G) $$
理解：
描述：生成子图不能删顶点，只能删边。
20.5.3 连通分量
定义：#连通分量
描述：无向图中的极大连通子图称为连通分量。
“极大”表示：
- 它不是比较所有连通子图后挑“顶点数最多”的那一个，而是按包含关系不能再扩大。
- 不能再从原图加入新的顶点及相应边而仍保持连通；若某个外部顶点能通过原图路径连到该分量，它本来就应属于同一连通分量。
- 在确定的分量顶点集合内，应包含原图中这些顶点之间的全部边。
理解：
描述：连通分量就是无向图中一块一块互相连通的最大区域。
若无向图本身是连通图，则它只有一个连通分量，就是它自己。
若无向图不是连通图，则它有多个连通分量。
20.5.4 强连通分量
定义：#强连通分量
描述：有向图中的极大强连通子图称为强连通分量。
强连通分量内部任意两个顶点 $v,w$ 都要满足： $$ v\leadsto w,\quad w\leadsto v $$
理解：
- 连通分量用于无向图。
- 强连通分量用于有向图。
- 强连通分量要求方向上能互相到达，条件比无向连通更强。
20.5.5 生成树
定义：#生成树
描述：连通图的生成树是包含图中全部顶点的一个极小连通子图。
生成树满足：
- 包含原图全部顶点。
- 保持连通。
- 边数尽可能少。
- 不含回路。
若连通图有 $n$ 个顶点，则它的生成树一定有： $$ n-1 $$
条边。
图示说明
- 左侧是原连通图，右侧保留全部六个顶点并删去多余边，得到一棵含 $6-1=5$ 条边的生成树。
- 生成树通常不唯一；不同删边选择可能得到不同树，但都必须连通、无环并包含全部顶点。
极小连通的含义：
描述：生成树已经是保持连通的最少边结构。
所以：
- 删除生成树中的任意一条边，图就会变成不连通。
- 向生成树中添加一条连接树内两个顶点的新边（例如原图中未选入的边），就会产生唯一回路。
生成树与原图的关系：
| 项目 | 原连通图 | 生成树 |
|---|---|---|
| 顶点 | 全部顶点 | 全部顶点 |
| 边 | 可以很多 | 必定 $n-1$ 条 |
| 是否连通 | 连通 | 连通 |
| 是否有环 | 可能有环 | 一定无环 |
20.5.6 生成森林
定义：#生成森林
描述：在非连通图中，各个连通分量的生成树组成的集合称为生成森林。
若一个无向图有 $k$ 个连通分量，且共有 $n$ 个顶点，则它的生成森林共有： $$ n-k $$
条边。
推导：
设第 $i$ 个连通分量有 $n_i$ 个顶点，则它的生成树有： $$ n_i-1 $$
条边。
所以整个生成森林的边数为： $$ \sum_{i=1}^{k}(n_i-1) =\sum_{i=1}^{k}n_i-k =n-k $$
生成树与生成森林对比：
| 项目 | 适用对象 | 结果 |
|---|---|---|
| 生成树 | 连通无向图 | 一棵树 |
| 生成森林 | 非连通无向图 | 多棵树 |
20.6 权值与特殊图
20.6.1 权值和网
定义：#权值
描述：图中边或弧上带有的数值称为权值。
权值可以表示：
- 距离。
- 时间。
- 成本。
- 容量。
- 相似度。
- 其他与关系相关的数量。
定义：#带权图 #网
描述：边上带有权值的图称为带权图，也称为网。
定义：#带权路径长度
描述：带权路径长度是路径上各条边权值之和。
若路径上各边权值为： $$ w_1,w_2,\cdots,w_k $$
则该路径的带权路径长度为： $$ \sum_{i=1}^{k}w_i $$
注意：
- 无权图中的路径长度通常指边数。
- 带权图中的路径长度可能指权值之和。
- 题目要看清楚是问“边数最短”还是“权值和最小”。
20.6.2 无向完全图
定义：#无向完全图
描述：无向图中，若任意两个不同顶点之间都存在一条边，则称该图为无向完全图。
若无向完全图有 $n$ 个顶点，则边数为： $$ C_n^2=\frac{n(n-1)}{2} $$
一般无向简单图的边数范围：
描述：无向简单图最多达到无向完全图的边数。
所以： $$ 0\le e\le C_n^2=\frac{n(n-1)}{2} $$
其中：
- $e=0$ 表示只有顶点、没有边。
- $e=C_n^2$ 表示无向完全图。
20.6.3 有向完全图
定义：#有向完全图
描述：有向图中，若任意两个不同顶点之间都存在方向相反的两条弧，则称该图为有向完全图。
对任意两个不同顶点 $v,w$，有向完全图中都同时存在： $$ <v,w> $$
和： $$ <w,v> $$
若有向完全图有 $n$ 个顶点，则弧数为： $$ 2C_n^2=n(n-1) $$
一般有向简单图的边数范围：
描述：有向简单图最多达到有向完全图的弧数。
所以： $$ 0\le e\le n(n-1) $$
其中：
- $e=0$ 表示只有顶点、没有弧。
- $e=n(n-1)$ 表示有向完全图。
图示说明
- 左图是五个顶点的无向完全图，每对不同顶点之间恰有一条边，共 $C_5^2=10$ 条。
- 右图是四个顶点的有向完全图，每对不同顶点之间都有方向相反的两条弧，共 $4\times 3=12$ 条。
20.7 性质总结
20.7.1 完全图边数
| 图的类型 | 最多边数 |
|---|---|
| 无向简单图 | $C_n^2=\dfrac{n(n-1)}{2}$ |
| 有向简单图 | $2C_n^2=n(n-1)$ |
20.7.2 连通性边数
| 图的类型 | 条件 | 至少边数 |
|---|---|---|
| 无向图 | 连通 | $n-1$ |
| 有向图 | 强连通且 $n\ge 2$ | $n$ |
20.7.3 度数公式
| 图的类型 | 公式 |
|---|---|
| 无向图 | $\sum_{i=1}^{n}TD(v_i)=2e$ |
| 有向图入度 | $\sum_{i=1}^{n}ID(v_i)=e$ |
| 有向图出度 | $\sum_{i=1}^{n}OD(v_i)=e$ |
| 有向图总度 | $\sum_{i=1}^{n}TD(v_i)=2e$ |
SUMMARY · 原 PDF 性质总图核对 第 6 页手写总图中的完全图边数、连通/强连通最少边数和度数关系，已完整拆入上面三张可检索表；同时补出了原图未强调的 $n=1$ 强连通特例，因此不再重复嵌入低可读性的整页截图。
20.8 题型：图基本概念
题型一：根据度数判断边数
方法：
描述：看到“度数和”，先判断是无向图还是有向图。
-
无向图： $$ e=\frac{1}{2}\sum TD(v_i) $$
-
有向图： $$ e=\sum ID(v_i)=\sum OD(v_i) $$
-
有向图如果给的是总度： $$ e=\frac{1}{2}\sum TD(v_i) $$
易错点：
- 有向图的入度和出度都等于边数。
- 有向图的总度之和才等于 $2e$。
- 不要把无向图的度数公式直接套到入度或出度上。
题型二：判断至少需要多少边
方法：
描述：先判断题目要求的是连通还是强连通。
| 题目条件 | 最少边数 | 构造方式 |
|---|---|---|
| $n$ 个顶点无向连通图 | $n-1$ | 构成一棵树 |
| $n\ge 2$ 个顶点有向强连通图 | $n$ | 构成一个有向环 |
记忆：
无向连通：像树一样连起来，n 个点最少 n-1 条边。
有向强连通：n>=2 时像环一样转起来，最少 n 条弧；n=1 时为 0 条。
题型三：判断一定连通的边数条件
方法：
描述：无向简单图要保证一定连通，就要超过“不连通时的最多边数”。
不连通时最多： $$ C_{n-1}^{2} $$
因此，一定连通的条件是： $$ e>C_{n-1}^{2} $$
即最少需要： $$ C_{n-1}^{2}+1 $$
条边，才能保证图一定连通。
构造反例思路：
- 让 $n-1$ 个顶点构成完全图。
- 剩下 $1$ 个顶点孤立。
- 这时图不连通，但边数已经尽可能多。
题型四：区分连通分量和生成树
| 概念 | 关键词 | 适用对象 |
|---|---|---|
| 连通分量 | 极大连通子图 | 无向图 |
| 强连通分量 | 极大强连通子图 | 有向图 |
| 生成树 | 极小连通子图 | 连通无向图 |
| 生成森林 | 各连通分量的生成树 | 非连通无向图 |
易错点：
- “极大”强调不能再扩大。
- “极小”强调不能再删边。
- 连通分量是一个子图，不是单纯的顶点集合。
- 生成树必须包含原图全部顶点。
相关知识
- 科目导航：数据结构导航
- 阅读顺序：上一篇：树与二叉树的应用 · 下一篇：图的存储及其操作
- 关联专题：图代码
20.9 本节复盘
必须掌握：
- 图的定义：$G=(V,E)$，且 $V$ 非空。
- 无向图的边是无序对：$(v,w)=(w,v)$。
- 有向图的边是有序对：$<v,w>\ne <w,v>$。
- 简单图不允许重复边和自回路。
- 无向图度数公式：$\sum TD(v_i)=2e$。
- 有向图度数公式：$\sum ID(v_i)=\sum OD(v_i)=e$。
- 路径长度是路径上的边数。
- 距离是最短路径长度，不存在路径时为 $\infty$。
- 无向连通图至少有 $n-1$ 条边。
- $n\ge 2$ 时，有向强连通图至少有 $n$ 条弧；$n=1$ 时为 $0$ 条。
- $n\ge 2$ 顶点不连通无向简单图最多有 $C_{n-1}^{2}$ 条边。
- 无向完全图有 $C_n^2=\dfrac{n(n-1)}{2}$ 条边。
- 有向完全图有 $n(n-1)$ 条弧。
- 生成树是包含全部顶点的极小连通子图。
- 生成森林是各个连通分量的生成树组成的集合。
一句话记忆：
图 = 顶点 + 边；无向看连通，有向看强连通；度数统计边，生成树保连通但边最少。