图¶
方法速览¶
| 任务 | 方法 | 口诀 |
|---|---|---|
| 无向图度数和 | \(= 2m\)（m 为边数，握手定理） | 一条边握两只手 |
| 有向图 | 入度和 = 出度和 = m | 进多少出多少 |
| n 点边数上限 | 无向简单图 \(\dfrac{n(n-1)}{2}\)；有向 \(n(n-1)\) | 无向砍半、有向全留 |
| 连通最少边 | 无向 \(n-1\)（树）；有向强连通 \(n\)（环） | 连通靠树、强连通靠环 |
| 拓扑序 | 存在 ⟺ 无环（DAG）；反复删入度 0 的点 | 无环才排得了序 |
| 存储选型 | 稠密用邻接矩阵（\(O(n^2)\)）；稀疏用邻接表（\(O(n+m)\)） | 密方疏表 |
图的基本性质¶
图 \(G = (V, E)\)：顶点集 + 边集。
- 简单图：无自环（边两端同一点）、无重边（两点间至多一条边）；
- n 个顶点的无向简单图最多 \(\dfrac{n(n-1)}{2}\) 条边（完全图 \(K_n\) 取到）；有向简单图最多 \(n(n-1)\) 条弧；
- 树是图的特例：连通 + 无环 + 恰 \(n-1\) 条边。
无向图与有向图¶
| 对比 | 无向图 | 有向图 |
|---|---|---|
| 边 | \((u,v)\) 双向通行 | \(\langle u,v \rangle\) 单行道 |
| 顶点的度 | 与该点相连的边数 | 分入度（指向它）与出度（它指出） |
| 握手定理 | \(\sum\deg = 2m\) | \(\sum\text{入度} = \sum\text{出度} = m\) |
| 连通 | 任意两点有路（连通） | 任意两点互达才叫强连通 |
自环：一条边两端是同一点，给该顶点贡献 2 度。
度与边的关系¶
握手定理（无向）：每条边给两个端点各贡献 1 度，所以度数总和是边数的两倍。
三条推论：
- 度数和必为偶数；
- 奇度顶点个数必为偶数（否则度数和凑不出偶数）；
- 度数和的一半才是边数——“度和 24 → 边 12”。
例：无向图各点度为 \(3, 2, 2, 1, 4\)，验证：和 \(= 12 = 2\times6\) → 6 条边；奇度点 3、1 共 2 个（偶数个）✓。
连通图与连通分量¶
- 连通图：任意两点之间都有路径。n 点连通至少 \(n-1\) 条边（取到即树）；
- 连通分量：极大的连通子图——不连通图由若干个连通分量组成；
- 不连通图最多边数：把 \(n-1\) 个点连成完全图、剩 1 个点孤立：\(\dfrac{(n-1)(n-2)}{2}\) 条；
- 强连通（有向）：任意两点互相可达；n 点强连通至少 n 条边（一个大环）。
稀疏图与稠密图¶
- 稠密：\(m\) 接近 \(n^2\)；稀疏：\(m\) 接近 \(n\)（如树 \(m = n-1\)）。
拓扑序¶
把 DAG（有向无环图）的顶点排成一列，使每条边 \(\langle u,v\rangle\) 都满足 u 在 v 前面。
存在拓扑序 \(\iff\) 图无环。手算（Kahn 算法）：
- 找入度为 0 的顶点输出；
- 删掉它和它的出边（后继入度减一）；
- 重复直到输出全部顶点；中途卡住（没有入度 0 的点）说明有环。
例：边 \(\langle1,2\rangle, \langle1,3\rangle, \langle2,4\rangle, \langle3,4\rangle\)：
| 轮 | 入度表 (1,2,3,4) | 输出 |
|---|---|---|
| 1 | (0,1,1,2) | 1（唯一入度 0） |
| 2 | (—,0,0,2) | 2（或 3，此处选 2） |
| 3 | (—,—,0,1) | 3 |
| 4 | (—,—,—,0) | 4 |
拓扑序 1 2 3 4（2、3 顺序可换——拓扑序不唯一）。
图的存储¶
| 对比 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 结构 | bool g[n][n]，g[u][v]=1 有边 |
每个点挂它的邻居列表 |
| 空间 | \(O(n^2)\) 固定 | \(O(n + m)\) 按需 |
| 判“u 到 v 有边” | \(O(1)\) | \(O(\deg u)\) |
| 遍历全边 | \(O(n^2)\) | \(O(n+m)\) |
| 适用 | 稠密图、频繁两点查询 | 稀疏图、要遍历邻居 |
竞赛主流：vector<int> g[N] 邻接表（或链式前向星）。
练习题目¶
练习 1 · 握手定理¶
题目
无向图有 8 条边，所有顶点的度数之和为（ ）
- A. \(8\)
- B. \(4\)
- C. \(16\)
- D. \(64\)
答案与解析
答案：C
\(\sum\deg = 2m = 2\times8 = 16\)。
练习 2 · 由度和求边¶
题目
无向图各顶点度数之和为 24，则边数为（ ）
- A. \(12\)
- B. \(24\)
- C. \(48\)
- D. \(6\)
答案与解析
答案：A
边数 = 度数和 ÷ 2 = 12。
干扰项思路：B 忘除 2——“度数和 = 边数”是最常见口误。
练习 3 · 度和的奇偶¶
题目
下列度数序列中，不可能是无向图各顶点的度的是（ ）
- A. \(1, 1, 2, 2\)
- B. \(3, 3, 3, 3\)
- C. \(2, 2, 2\)
- D. \(3, 3, 3, 3, 3\)
答案与解析
答案：D
度数和必须为偶数：D 的和是 15（奇数）；且奇度点 5 个（奇数个）双重违规。A 和为 6、B 和为 12、C 和为 6 都能画出图。
练习 4 · 奇度点个数¶
题目
无向图中，度为奇数的顶点个数（ ）
- A. 任意
- B. 必为 0
- C. 必为奇数
- D. 必为偶数
答案与解析
答案：D
度数和是偶数（\(2m\)），奇度点必须是成对出现才能凑出偶数和——握手定理最常考的推论。
练习 5 · 无向完全图边数¶
题目
10 个顶点的无向完全图有（ ）条边。
- A. \(100\)
- B. \(90\)
- C. \(45\)
- D. \(50\)
答案与解析
答案：C
\(\dfrac{n(n-1)}{2} = \dfrac{10\times9}{2} = 45\)。
干扰项思路：B 是有向版 \(n(n-1)\)；A 是 \(n^2\)。
练习 6 · 小规模完全图¶
题目
完全图 \(K_5\)（5 个顶点两两相邻）的边数是（ ）
- A. \(5\)
- B. \(20\)
- C. \(25\)
- D. \(10\)
答案与解析
答案：D
\(\dfrac{5\times4}{2} = 10\)。
练习 7 · 有向图的边数上限¶
题目
4 个顶点的有向简单图（无自环无重边）最多有（ ）条弧。
- A. \(6\)
- B. \(12\)
- C. \(16\)
- D. \(4\)
答案与解析
答案：B
有向图的弧带方向：\(u\to v\) 与 \(v\to u\) 是两条不同的弧，有序对共 \(n(n-1) = 4\times3 = 12\) 条。
干扰项思路：A 是无向版的 \(\binom{4}{2} = 6\)——“有向不砍半”。
练习 8 · 自环的度贡献¶
题目
无向图中一个自环（顶点到自身的边）给该顶点贡献的度数是（ ）
- A. \(2\)
- B. \(1\)
- C. \(0\)
- D. \(n\)
答案与解析
答案：A
自环的两端都是这个顶点，贡献 2 度——所以“无自环”的简单图里才有干净的计数。
练习 9 · 有向图的入度出度¶
题目
有向图有 12 条弧，则所有顶点的入度之和与出度之和分别为（ ）
- A. \(12\) 和 \(24\)
- B. \(6\) 和 \(6\)
- C. \(24\) 和 \(24\)
- D. \(12\) 和 \(12\)
答案与解析
答案：D
每条弧给终点 +1 入度、起点 +1 出度：入度和 = 出度和 = 弧数 = 12。
练习 10 · 单点的入度出度关系¶
题目
有向图中某顶点入度 3、出度 2，与它相连的弧共（ ）条。
- A. \(5\)
- B. \(1\)
- C. \(6\)
- D. \(3\)
答案与解析
答案：A
入度数进来的 + 出度数出去的 = \(3+2 = 5\)。
练习 11 · 连通最少边¶
题目
8 个顶点的无向图至少要（ ）条边才可能连通。
- A. \(7\)
- B. \(8\)
- C. \(16\)
- D. \(28\)
答案与解析
答案：A
连通最少 \(n-1 = 7\) 条（恰好是树）。
练习 12 · 不连通的最多边¶
题目
6 个顶点的无向简单图最多有几条边，还能保持不连通？（ ）
- A. \(11\)
- B. \(15\)
- C. \(10\)
- D. \(14\)
答案与解析
答案：C
把 5 个点连成完全图 \(\binom{5}{2} = 10\) 条，第 6 个点孤立——再多连任何一条都会连通。
练习 13 · 连通分量¶
题目
“连通分量”是（ ）
- A. 图中的一条边
- B. 极大的连通子图
- C. 任意一个连通子图
- D. 度数最大的顶点
答案与解析
答案：B
关键在“极大”：不能再加顶点仍保持连通。不连通图的连通分量个数 ≥ 2。
练习 14 · 强连通¶
题目
n 个顶点的有向图要强连通（任意两点互达），至少需要（ ）条弧。
- A. \(n-1\)
- B. \(2n\)
- C. \(n\)
- D. \(\frac{n(n-1)}{2}\)
答案与解析
答案：C
一个有向环 \(1\to2\to\dots\to n\to1\) 即可互达，恰 n 条；\(n-1\) 条只能“单向往下”（像树），回不去。
练习 15 · 拓扑序的存在条件¶
题目
有向图存在拓扑排序的充要条件是（ ）
- A. 连通
- B. 边数少于顶点数
- C. 每点入度不超过 2
- D. 无环（是 DAG）
答案与解析
答案：D
环上每个点都在“等前面的人”，永远删不出入度 0——有环必无拓扑序；与连通与否无关。
练习 16 · 拓扑序手算¶
题目
边 \(\langle1,2\rangle, \langle1,3\rangle, \langle2,4\rangle, \langle3,4\rangle\)，下列不是合法拓扑序的是（ ）
- A.
1 2 3 4 - B.
1 3 2 4 - C.
1 2 4 3 - D.
4 1 2 3
答案与解析
答案：C
\(\langle3,4\rangle\) 要求 3 在 4 之前，1 2 4 3 里 4 抢在 3 前面，违规。A、B 都合法（2、3 无先后约束）；D 中 4 排在 2、3 之前，违反 \(\langle2,4\rangle\) 与 \(\langle3,4\rangle\) 两条边。判据只有一条：每条边的起点排在终点前。
练习 17 · 拓扑序不唯一¶
题目
拓扑排序的结果（ ）
- A. 一定唯一
- B. 一定有 n! 种
- C. 由顶点编号唯一决定
- D. 可能不唯一——无约束的顶点相对顺序可换
答案与解析
答案：D
没有边约束的点对（如上题的 2 和 3）可互换；只有“每对点都有边”时才唯一。
练习 18 · 入度 0 的意义¶
题目
Kahn 算法每轮输出入度 0 的顶点，是因为它（ ）
- A. 编号最小
- B. 度数最大
- C. 没有任何前置依赖，可以立即输出
- D. 一定在环上
答案与解析
答案：C
入度 0 = 没有边指向它 = 没人排在它前面——这就是“先修课没有先修”的课。
练习 19 · 邻接矩阵的空间¶
题目
用邻接矩阵存 1000 个顶点的图，空间为（ ）
- A. \(O(n^2)\)，与边数无关
- B. \(O(n)\)
- C. \(O(m)\)
- D. \(O(n+m)\)
答案与解析
答案：A
\(1000\times1000 = 10^6\) 个单元，固定开销；边再少也这么多——稀疏图太浪费。
练习 20 · 邻接表的空间¶
题目
邻接表的空间复杂度是（ ）
- A. \(O(n^2)\)
- B. \(O(1)\)
- C. \(O(m^2)\)
- D. \(O(n + m)\)
答案与解析
答案：D
n 个表头 + 每条边一个结点（无向图存两次是 \(n + 2m\)，量级不变）。
练习 21 · 判边速度¶
题目
频繁查询“u 与 v 之间有没有边”，最合适的存储（ ）
- A. 邻接表
- B. 邻接矩阵——查一次 \(O(1)\)
- C. 边列表
- D. 哈希表存顶点名
答案与解析
答案：B
g[u][v] 一步直达；邻接表要扫 u 的邻居链。
练习 22 · 稀疏图选型¶
题目
n = 10 万、m = 20 万的稀疏图，应选（ ）
- A. 邻接矩阵（\(10^{10}\) 单元）
- B. 邻接表（\(O(n+m)\)）
- C. 都一样
- D. 二维 bool 数组
答案与解析
答案：B
矩阵要 \(10^{10}\) 内存直接爆；邻接表 30 万级，轻松。
练习 23 · 遍历复杂度¶
题目
DFS/BFS 遍历整图，邻接表实现的时间复杂度（ ）
- A. \(O(n^2)\)
- B. \(O(nm)\)
- C. \(O(m\log n)\)
- D. \(O(n+m)\)
答案与解析
答案：D
每点进队/递归一次、每条边扫一次；矩阵版才是 \(O(n^2)\)。
练习 24 · 树与图¶
题目
关于树和图的关系（ ）
- A. 树不是图
- B. 树是无环连通图的特例
- C. 图都是树
- D. 树可以有环
答案与解析
答案：B
树 = 连通 + 无环（+ \(n-1\) 条边）；图是更一般的结构。
练习 25 · 度的上限¶
题目
n 个顶点的无向简单图中，一个顶点的度最大是（ ）
- A. \(n\)
- B. \(2n\)
- C. \(n-1\)
- D. \(n/2\)
答案与解析
答案：C
其余 \(n-1\) 个点都与它相连即满度；\(n\) 要靠自环（简单图不允许）。
练习 26 · 综合判断¶
题目
5 个顶点、7 条边的无向连通图，要变成一棵树需（ ）
- A. 删 2 条边
- B. 删 3 条边
- C. 加 1 条边
- D. 删 1 条边
答案与解析
答案：B
树保留 \(n-1 = 4\) 条，删 \(7 - 4 = 3\) 条（即 \(m - n + 1\)）。
历年真题¶
2020 年 · 第 8 题¶
题目
有 \(10\) 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图。
- A. \(9\)
- B. \(10\)
- C. \(11\)
- D. \(12\)
答案与解析
答案：A
连通最少 \(n-1 = 9\) 条（树）；再少必有孤立块。
2023 年 · 第 12 题¶
题目
考虑一个有向无环图，该图包含 4 条有向边：(1,2), (1,3), (2,4)和(3,4)。以下哪个选项是这个有向无环图的一个有效的拓扑排序？（ ）
- A.
4, 2, 3, 1 - B.
1, 2, 3, 4 - C.
1, 2, 4, 3 - D.
2, 1, 3, 4
答案与解析
答案：B
逐项检查“每条边起点在终点前”：A 中 4 排最前但两条边指向 4；C 中 4 抢在 3 前（边 3→4 违规）；D 中 2 抢在 1 前（边 1→2 违规）；B 全部满足。1 必须最先（入度 0）、4 必须最后，中间 2、3 可换。
2024 年 · 第 11 题¶
题目
在无向图中，所有顶点的度数之和等于（ ）。
- A. 图的边数
- B. 图的边数的两倍
- C. 图的顶点数
- D. 图的顶点数的两倍
答案与解析
答案：B
握手定理：一条边握两只手，各贡献 1 度。
2025 年 · 第 5 题¶
题目
在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这个总和等于？（ ）
- A. 顶点数
- B. 边数
- C. 顶点数 \(+\) 边数
- D. 顶点数 \(\times\) 边数
答案与解析
答案：B
每条弧“一进一出”：入度和 = 出度和 = 弧数 m。
易错小结¶
- 度数和是边数的两倍（无向）；有向图入度和 = 出度和 = 边数（不是两倍）；
- 奇度顶点必成偶数个；度和是奇数的序列直接判不可行；
- 无向简单图边上限 \(\binom{n}{2}\)、有向 \(n(n-1)\)——“有向不砍半”；
- 连通最少 \(n-1\) 条；不连通最多 \(\binom{n-1}{2}\) 条（n−1 个点抱团 + 1 孤点）；
- 拓扑序 ⟺ 无环；手算“删入度 0”；中途无入度 0 点 = 有环；
- 稠密图邻接矩阵（判边 O(1)）、稀疏图邻接表（空间 \(O(n+m)\)）。