Lecture 20：图基本概念
408 学习笔记：Lecture 20：图基本概念。保留原有知识内容、公式与图示；有对应原件时提供查看和下载入口。
本页目录
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)$ 条弧。
- 生成树是包含全部顶点的极小连通子图。
- 生成森林是各个连通分量的生成树组成的集合。
一句话记忆：
图 = 顶点 + 边；无向看连通，有向看强连通；度数统计边，生成树保连通但边最少。