408

数据结构

图的基本概念（有向图/无向图/度/连通）

---

一、定位信息

• 圈层：核心层（大纲考点）
• 前置知识：线性表、树的基本概念（节点、边等术语的初步认知）
• 知识网络定位：图是一种比树更一般的非线性数据结构，是后续图的存储、遍历、最小生成树、最短路径、拓扑排序和关键路径的理论基础。
• 考点热度：H级（高频重点） — 图的基本概念是几乎所有图论题目的基础，近五年真题中通过选择题和综合题间接考查频次极高，累计分值 ≥5 分。

---

二、知识点讲解

2.1 图的定义

图（Graph）$G$ 由顶点集 $V$ 和边集 $E$ 组成，记作 $G = (V, E)$。其中 $V$ 是有限非空集合，$E$ 是 $V$ 中顶点之间关系的有限集合。若 $|V| = n$，则称图有 $n$ 个顶点；若 $|E| = e$，则称图有 $e$ 条边。

直观理解：把"事物"抽象为顶点，把事物之间的"关系"抽象为边，就得到了一张图。例如城市地图中，城市是顶点，公路是边。

2.2 有向图与无向图

• 无向图：边没有方向，边 $(u, v)$ 表示 $u$ 和 $v$ 之间的双向关系。无向边记作 $(u, v)$，等价于 $(v, u)$。
• 有向图：边有方向，弧 $\langle u, v \rangle$ 表示从 $u$ 指向 $v$ 的单向关系。$u$ 是弧尾（起点），$v$ 是弧头（终点）。$\langle u, v \rangle \neq \langle v, u \rangle$。

2.3 完全图

• 无向完全图：任意两个不同顶点之间都有边，边数 $e = \frac{n(n-1)}{2}$。
• 有向完全图：任意两个不同顶点之间都有两条方向相反的弧，弧数 $e = n(n-1)$。

2.4 度

• 无向图：顶点 $v$ 的度 $TD(v)$ 是与 $v$ 关联的边数。所有顶点度之和 $= 2e$（每条边贡献两个度）。
• 有向图：
  • 入度 $ID(v)$：以 $v$ 为终点的弧数。
  • 出度 $OD(v)$：以 $v$ 为起点的弧数。
  • 度 $TD(v) = ID(v) + OD(v)$。
  • 所有顶点入度之和 $=$ 所有顶点出度之和 $= e$。

2.5 子图

设 $G = (V, E)$，$G' = (V', E')$，若 $V' \subseteq V$ 且 $E' \subseteq E$，则 $G'$ 是 $G$ 的子图。

2.6 连通与连通分量

• 无向图：
  • 连通：$u$ 到 $v$ 之间存在路径，则称 $u$ 和 $v$ 连通。
  • 连通图：任意两个顶点都连通的无向图。
  • 连通分量：无向图的极大连通子图（不能再加入任何顶点和边后仍连通）。
• 有向图：
  • 强连通：$u$ 到 $v$ 和 $v$ 到 $u$ 之间都存在路径。
  • 强连通图：任意两个顶点都强连通。
  • 强连通分量：有向图的极大强连通子图。

2.7 权与网

• 权（Weight）：边或弧上的数值，表示距离、代价等。
• 网（Network）：带权的图。

2.8 稀疏图与稠密图

• 稀疏图：边数 $e \ll n^2$ 的图。
• 稠密图：边数 $e$ 接近 $n^2$ 的图。无严格界限，通常 $e < n \log n$ 视为稀疏。

2.9 路径与回路

• 路径：顶点序列 $v_0, v_1, \dots, v_k$，其中 $(v_{i-1}, v_i)$ 或 $\langle v_{i-1}, v_i \rangle \in E$。
• 路径长度：路径上边或弧的数目。
• 回路（环）：起点和终点相同的路径（$v_0 = v_k$）。
• 简单路径：顶点不重复出现的路径。
• 简单回路：除起点和终点外，其余顶点不重复的回路。

2.10 连通图的生成树

• 生成树：包含图中所有顶点的极小连通子图。$n$ 个顶点的连通图的生成树有 $n-1$ 条边。
• 生成森林：非连通图的各连通分量的生成树组成生成森林。

---

三、记忆与理解辅助

技巧 1：边数公式速记

• 无向完全图边数：$e = \frac{n(n-1)}{2}$ — 记为"$C_n^2$"
• 有向完全图弧数：$e = n(n-1)$ — 记为"$A_n^2$（排列，方向不同算两条）"

技巧 2：度之和公式口诀

• 无向图："边数乘二等于度之和"——$\sum TD(v) = 2e$
• 有向图："入度之和等于出度之和等于边数"——$\sum ID(v) = \sum OD(v) = e$

技巧 3：连通性对比表

概念	无向图	有向图
基本连通	$u$ 到 $v$ 有路径	$u$ 到 $v$ 和 $v$ 到 $u$ 都有路径
全连通	连通图	强连通图
极大连通子图	连通分量	强连通分量
最少边数（连通）	$n-1$（生成树）	$n$（一条环路）

技巧 4：稀疏图vs稠密图选存储

• 稀疏图 → 邻接表（省空间）
• 稠密图 → 邻接矩阵（访问快）

---

四、例题与精解

例题 1（基础巩固）

题目：一个有 $n$ 个顶点的无向图，最多有多少条边？最少要多少条边才能保证是连通图？

命题意图：考查完全图的边数公式和连通图的最少边数条件。

审题分析：

• 已知：无向图，$n$ 个顶点。
• 求解：(1) 最大边数；(2) 连通所需的最少边数。

解题思路：

• 最大边数对应完全图。
• 连通的最少边数：考虑最坏情况，先让 $n-1$ 个顶点各自孤立，最后用一条链连起来。

完整步骤：

1. 最大边数：无向完全图，每对顶点之间都有边。 $e_{\max} = \frac{n(n-1)}{2}$

2. 最少边数保证连通：$n$ 个顶点的连通图至少有 $n-1$ 条边（生成树性质）。可以用反证法：若只有 $n-2$ 条边，由握手定理 $\sum TD(v) = 2(n-2) = 2n-4$，平均度约为 $2 - \frac{4}{n}$，当 $n \geq 3$ 时可能存在孤立顶点，无法保证连通。 $e_{\min} = n - 1$

方法反思：连通图最少边数 $n-1$ 是生成树的边数，这个结论在最小生成树（DS-05-04）中会反复使用。

---

例题 2（中等提升）

题目：设无向图 $G$ 有 16 条边，其中有 3 个顶点的度为 4，其余顶点的度均小于 4。问 $G$ 中至少有多少个顶点？

命题意图：考查握手定理（度之和公式）的应用。

审题分析：

• 已知：$e = 16$，3 个顶点度为 4，其余顶点度 $< 4$。
• 求解：顶点数 $n$ 的最小值。

解题思路：由握手定理 $\sum TD(v) = 2e = 32$，先扣除 3 个度为 4 的顶点的贡献，再让其余顶点度尽可能大以减少顶点数。

完整步骤：

1. 握手定理：$\sum TD(v) = 2 \times 16 = 32$。
2. 3 个度为 4 的顶点贡献：$3 \times 4 = 12$。
3. 剩余度数：$32 - 12 = 20$。
4. 其余顶点度 $< 4$，即最大度为 3。要使顶点数最少，让每个其余顶点度取最大值 3。
5. 其余顶点数 $\geq \lceil \frac{20}{3} \rceil = 7$。
6. 总顶点数 $n \geq 3 + 7 = 10$。

验证：$n = 10$ 时，3 个顶点度为 4，7 个顶点度为 $\frac{20}{7} \approx 2.86$，可取 6 个度为 3、1 个度为 2，总计 $12 + 18 + 2 = 32$。✓

答案：至少 10 个顶点。

方法反思：此类题目核心工具是握手定理 $\sum TD(v) = 2e$，配合极值分析。变式方向：改为有向图，用 $\sum ID(v) = \sum OD(v) = e$。

---

五、考情分析

• 考查频次：图的基本概念本身不单独出大题，但作为选择题和大题的基础，近 5 年真题中几乎每年都有涉及（直接或间接考查 ≥4 次）。
• 常见题型：选择题（判断图的性质、计算度之和）、填空题（给定条件求顶点数/边数）。
• 分值占比：直接考查约 2–4 分，间接考查（作为大题前置判断）更高。
• 命题趋势：概念题趋于灵活，常与图的存储结构、遍历算法结合考查。近年来对连通分量、生成树等概念的辨析题有增加趋势。
• 基于大纲与命题规律推测

---

六、易错点提醒

1. 错误表现：混淆无向边 $(u, v)$ 和有向弧 $\langle u, v \rangle$ 的记法。 错误原因：有向图中 $\langle u, v \rangle$ 和 $\langle v, u \rangle$ 是两条不同的弧，但无向图中 $(u, v)$ 和 $(v, u)$ 是同一条边。 正确理解：无向边用圆括号，无序；有向弧用尖括号，有序。画图时无向图边不带箭头，有向图弧带箭头。

2. 错误表现：计算有向图边数时，将所有顶点度之和直接等于 $2e$。 错误原因：有向图中每条弧只给弧尾一个出度、弧头一个入度，度之和 $= 2e$ 仍然成立，但入度之和 $=$ 出度之和 $= e$ 是更常用的性质。关键是不要混淆"入度之和"与"度之和"。 正确理解：有向图 $\sum TD(v) = 2e$（因为 $TD = ID + OD$，每条弧贡献一个 $ID$ 和一个 $OD$）；$\sum ID(v) = \sum OD(v) = e$。

3. 错误表现：认为 $n$ 个顶点的连通图至少需要 $n$ 条边。 错误原因：与有向强连通图混淆。无向连通图最少 $n-1$ 条边（生成树），而有向强连通图最少 $n$ 条边（一条环路）。 正确理解：无向连通最少 $n-1$；有向强连通最少 $n$（首尾相接的环）。

4. 错误表现：将连通分量理解为"任意一个连通子图"。 错误原因：连通分量是"极大"连通子图，即不能再加入任何其他顶点和边后仍保持连通。 正确理解：连通分量 = 极大连通子图，必须包含所有能通过路径到达的顶点。

---

七、来源标注

• 依据 2026 考研统考大纲
• 依据《数据结构（C语言版）》严蔚敏版
• 依据大学本科经典教材共识