12. 边的权、网和带权路径长度
## 12. 边的权、网和带权路径长度
在一些图中，每条边可以被赋予一个代表某种意义的数值，称为该边的权值。这种边上带有权值的图称为带权图，也称网。路径上所有边的权值之和，称为该路径的带权路径长度。
## 13. 完全图（也称简单完全图）
对于无向图，边的数量 $|E|$ 范围是从 0 到 $n(n - 1) / 2$。当边数达到最大值 $n(n - 1) / 2$ 时，该无向图称为完全图，意味着任意两个顶点之间都有一条边相连。对于有向图， $|E|$ 的范围是从 0 到 $n(n - 1)$，有 $n(n - 1)$ 条弧的有向图称为有向完全图，即任意两个顶点之间都存在方向相反的两条弧。图 6.1 中 $G_{2}$ 为无向完全图，而 $G_{3}$ 为有向完全图。
## 14. 稠密图、稀疏图
边数相对较少的图称为稀疏图，反之称为稠密图。这两个概念本身较为模糊，稀疏和稠密常常是相对而言的。一般认为，当图 $G$ 满足 $|E| < |V|\log_2|V|$ 时，可视为稀疏图。
## 15. 有向树
一个顶点的入度为 0、其余顶点的入度均为 1 的有向图，称为有向树。
## 6.1.2 本节试题精选
### 一、单项选择题
01. 一个有 $n$ 个顶点和 $n$ 条边的无向图一定是（）。
A. 连通的
B. 不连通的
C. 无环的
D. 有环的
① 有向图强连通情况下边最少的情况；至少需要 $n$ 条边，构成一个环路。
<!-- page: 210 -->
2027年数据结构考研复习指导
02. 若从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。
A. 强连通图
B. 连通图
C. 有回路
D. 一棵树
03. 以下关于图的叙述中，正确的是（）。
A. 图与树的区别在于图的边数大于或等于顶点数
B. 假设有图 $G = \{V, \{E\}\}$，顶点集 $V' \subseteq V$，$E' \subseteq E$，则 $V'$ 和 $\{E'\}$ 构成 $G$ 的子图
C. 无向图的连通分量是指无向图中的极大连通子图
D. 图的遍历就是从图中某一顶点出发访遍图中其余顶点
04. 以下关于图的叙述中，正确的是（）。
A. 强连通有向图的任何顶点到其他所有顶点都有弧
B. 图的任意顶点的入度等于出度
C. 有向完全图一定是强连通有向图
D. 有向图的边集的子集和顶点集的子集都构成原有向图的子图
05. 一个有28条边的非连通无向图至少有（ ）个顶点。
A. 7
B. 8
C. 9
D. 10
06. 对于一个有 $n$ 个顶点的图：若是连通无向图，其边的个数至少为（）；若是强连通有向图，则其边的个数至少为（）。
A. $n - 1, n$
B. $n - 1, n(n - 1)$
C. $n, n$
D. $n, n(n - 1)$
07. 无向图 $G$ 有 23 条边，度为 4 的顶点有 5 个，度为 3 的顶点有 4 个，其余都是度为 2 的顶点，则图 $G$ 有（ ）个顶点。
A. 11
B. 12
C. 15
D. 16
08. 在有 $n$ 个顶点的有向图中，顶点的度最大可达（）。
A. $n$
B. $n - 1$
C. $2n$
D. $2n - 2$
09. 具有 6 个顶点的无向图，当有（ ）条边时能确保是一个连通图。
A. 8
B. 9
C. 10
D. 11
10. 设有无向图 $G = (V, E)$ 和 $G' = (V', E')$，若 $G'$ 是 $G$ 的生成树，则下列不正确的是（）。
I. $G'$ 为 $G$ 的连通分量
II. $G'$ 为 $G$ 的无环子图
III. $G'$ 为 $G$ 的极小连通子图且 $V' = V$
A. I、II
B. 只有 III
C. II、III
D. 只有 I
11. 具有 51 个顶点和 21 条边的无向图的连通分量最多为（）。
A. 33
B. 34
C. 45
D. 32
12. 在右图所示的有向图中，共有（ ）个强连通分量。
A. 1
B. 2
C. 3
D. 4
13. 若具有 $n$ 个顶点的图是一个环，则它有（ ）棵生成树。
A. $n^{2}$
B. $n$
C. $n - 1$
D. 1
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
14. 若一个具有 $n$ 个顶点、$e$ 条边的无向图是一个森林，则该森林中必有（ ）棵树。
<!-- page: 211 -->
第6章 图
199
A. $n$
B. $e$
C. $n - e$
D. 1
15. 【2009统考真题】下列关于无向连通图特性的叙述中，正确的是（）。
I. 所有顶点的度之和为偶数
II. 边数大于顶点个数减 1
III. 至少有一个顶点的度为 1
A. 只有 I
B. 只有 II
C. I 和 II
D. I 和 III
16. 【2010统考真题】若无向图 $G = (V, E)$ 中含有 7 个顶点，要保证图 $G$ 在任何情况下都是连通的，则需要的边数最少是（）。
A. 6
B. 15
C. 16
D. 21
17. 【2017统考真题】已知无向图 $G$ 含有 16 条边，其中度为 4 的顶点个数为 3，度为 3 的顶点个数为 4，其他顶点的度均小于 3。图 $G$ 所含的顶点个数至少是（）。
A. 10
B. 11
C. 13
D. 15
18. 【2022统考真题】对于无向图 $G = (V, E)$，下列选项中，正确的是（）。
A. 当 $|V| > |E|$ 时， $G$ 一定是连通的
B. 当 $|V| < |E|$ 时， $G$ 一定是连通的
C. 当 $|V| = |E| - 1$ 时， $G$ 一定是不连通的
D. 当 $|V| > |E| + 1$ 时， $G$ 一定是不连通的
## 二、综合应用题
01. 图 $G$ 是一个非连通无向图，共有 28 条边，该图至少有多少个顶点？
## 6.1.3 答案与解析
## 一、单项选择题
01. D
若一个无向图有 $n$ 个顶点和 $n - 1$ 条边，可以使它连通但没有环（生成树），但若再加一条边，在不考虑重边的情形下，则必然会构成环。
02. B
强连通图是有向图，与题意矛盾，选项 A 错误；对无向连通图做一次深度优先搜索，可以访问到该连通图的所有顶点，选项 B 正确；有回路的无向图不一定是连通图，因为回路不一定包含图的所有顶点，选项 C 错误；连通图可能是树，也可能存在环，选项 D 错误。
03. C
图与树的区别是逻辑上的区别，而不是边数的区别，图的边数也可能小于树的边数，选项 A 错误；若 $E'$ 中的边对应的顶点不是 $V'$ 的元素，则 $V'$ 和 $\{E'\}$ 无法构成图，选项 B 错误；无向图的极大连通子图称为连通分量，选项 C 正确；图的遍历要求每个顶点只能被访问一次，且若图非连通，则从某一顶点出发无法访问到其他全部顶点，选项 D 的说法不准确。
04. C
强连通有向图的任何顶点到其他所有顶点都有路径，但未必有弧；无向图任意顶点的入度等于出度，但有向图未必满足；若边集中的某条边对应的某个顶点不在对应的顶点集中，则有向图的边集的子集和顶点集的子集无法构成子图。
05. C
考查至少有多少个顶点的情形，我们考虑该非连通图最极端的情况，即它由一个完全图加一个独立的顶点构成，此时若再加一条边，则必然使图变成连通图。在 $28 = n(n - 1)/2 = 8 \times 7/2$
<!-- page: 212 -->
2027年数据结构考研复习指导
条边的完全无向图中，总共有8个顶点，再加上1个不连通的顶点，共9个顶点。
06. A
对于连通无向图，边最少即构成一棵树的情形；对于强连通有向图，边最少即构成一个有向环的情形。
07. D
因为在具有 $n$ 个顶点、$e$ 条边的无向图中，有 $\sum_{i=1}^{n} \mathrm{TD}(v_i) = 2e$，所以求得度为2的顶点数为7，从而共有16个顶点。
08. D
在有向图中，顶点的度等于入度与出度之和。$n$ 个顶点的有向图中，任意一个顶点最多还可以与其他 $n-1$ 个顶点有一对指向相反的边相连。注意，数据结构中仅讨论简单图。
09. D
5个顶点构成一个完全无向图，需要 $n(n - 1) / 2 = 10$ 条边；再加上1条边后，能保证第6个顶点必然与此完全无向图构成一个连通图，所以共需11条边。
10. D
一个连通图的生成树是一个极小连通子图，显然它是无环的，因此说法Ⅱ、Ⅲ正确。极大连通子图称为连通分量，$G^{*}$ 连通但非连通分量。这里再补充一下“极大连通子图”；若图本来就是连通的，且每个子部分包含其本身的所有顶点和边，则它就是极大连通子图。
11. C
初始考虑只有51个顶点的无向图 $G$，此时 $G$ 中每个顶点都是连通分量，问题转化为向 $G$ 中添加21条边，如何添加这21条边使得连通分量数目最多。若向两个不同的连通分量之间添加边，则连通分量数目会减1，所以应尽可能地将这21条边加入同一个连通分量且让其接近完全图，含有7个顶点的完全图有21条边，所以用7个顶点构成一个含有21条边的连通分量，剩下 $51 - 7 = 44$ 个顶点对应44个连通分量，共有45个连通分量。
12. B
强连通分量是极大强连通子图，任意两个顶点之间有方向相反的两条路径。由定义不难得出，若一个顶点只有出边或入边，则该顶点必定单独构成一个连通分量。图中，顶点 $B$ 只有出边，其他所有顶点都不可能有到顶点 $B$ 的路径，所以顶点 $B$ 单独构成一个强连通分量。在顶点 $A$、$C$、$D$、$E$ 中，任意两个顶点之间都有方向相反的两条路径，所以可构成一个强连通分量。
13. B
$n$ 个顶点的生成树是具有 $n - 1$ 条边的极小连通子图，因为 $n$ 个顶点构成的环共有 $n$ 条边，去掉任意一条边就是一棵生成树，所以共有 $n$ 种情况，所以可以有 $n$ 棵不同的生成树。
14. C
$n$ 个顶点的树有 $n - 1$ 条边，假设森林中有 $x$ 棵树，将每棵树的根连到一个添加的顶点，则成为一棵树，顶点数是 $n + 1$，边数是 $e + x$，从而可知 $x = n - e$。
【另解】设森林中有 $x$ 棵树，则再用 $x - 1$ 条边就可将所有的树连接成一棵树，此时边数 $+1 =$ 顶点数，即 $e + (x - 1) + 1 = n$，所以 $x = n - e$。
15. A
每条边都连接了两个顶点，在计算顶点的度之和时每条边都被计算了两次，所以所有顶点的度之和偶数。无向连通图对应的生成树也是无向连通图，但此时边数等于顶点数减1，说法Ⅱ错误。考虑2个或以上的顶点恰好构成一个环的情况，此时每个顶点的度都为2，说法Ⅲ错误。
16. C
题干要求无论如何分配边，都能使7个顶点连通，这不同于只要6条边两两相连就能构成一
<!-- page: 213 -->
第6章图
个连通图的情形。考虑最极端的情形，即图 $G$ 的某6个顶点构成一个完全无向图，此时若再添加一条边，则都将连通第7个顶点，使该图变成一个连通图。所以最少边数 $= 6 \times 5 / 2 + 1 = 16$ 。若边数 $n$ 小于或等于15，可以使这 $n$ 条边仅连接图 $G$ 中的某6个顶点，从而导致第7个顶点无法与这6个顶点构成连通图（不满足“在任何情况下”）。
为简单起见，以5个顶点为例，左边4个顶点和 $4\times 3 / 2 = 6$ 条边构成一个完全图，此时若再添加一条边（可以是虚线中的任意一条），则能保证这5个顶点在任何情况下都是连通的，如右图所示。若边数小于7，则不能保证5个顶点在任何情况下都是连通的。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
## 17. B 无向图边数的2倍等于各顶点度数的总和。要求至少的顶点数，应使每个顶点的度取最大，而其他顶点的度均小于3，因此可设它们的度都为2，并设它们的数量为 $x$ ，列出方程 $4\times 3 + 3\times 4 + 2x = 16\times 2$ ，解得 $x = 4$ 。因此至少包含 $4 + 4 + 3 = 11$ 个顶点。 ## 18. D 对于此类分析图的边数、顶点数与连通性问题，思路是寻找临界情况，在临界情况下任意增加或减少一条边，都会改变图的连通性。第一种临界情况如图1所示，此时若减少任意一条边，图就由连通变为不连通，即无向图连通的最小边数是 $|V| - 1$ ，因此，当 $|E| < |V| - 1$ 时，图一定不连通，选项C错误，选项D正确。第二种临界情况如图2所示，此时若增加任意一条边，则图就由不连通变为连通，即无向图不连通的最大边数是 $(|V| - 1)(|V| - 2)/2$ （此时 $|V| - 1$ 个顶点构成一个完全图），因此，仅当 $|E| \geqslant (|V| - 1)(|V| - 2)/2 + 1$ 时才能保证无向图一定连通，选项A、B错误。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图1
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图2
## 二、综合应用题
### 01. 【解答】
图 $G$ 是一个非连通无向图，当边数固定时，顶点数最少的情况是该图由两个连通子图构成，且其中之一只含一个顶点，另一个为完全图。其中只含一个顶点的子图没有边，另一个完全图的边数为 $n(n - 1) / 2 = 28$ ，得 $n = 8$ 。所以该图至少有 $1 + 8 = 9$ 个顶点。
## 6.2 图的存储及基本操作
图的存储必须要完整、准确地反映顶点集和边集的信息。针对不同的图结构和算法需求，选择合适的存储方式将显著影响程序的效率，因此所采用的存储结构应与待求解的问题相适应。
### 6.2.1 邻接矩阵法
邻接矩阵存储方法通过一个一维数组存储图中顶点的信息，并用一个二维数组存储边的信息（各顶点之间的邻接关系）。这个用于存储邻接关系的二维数组称为邻接矩阵。
顶点数为 $n$ 的图 $G = (V, E)$ 的邻接矩阵 $A$ 是 $n \times n$ 的，将图 $G$ 的顶点编号为 $\nu_{1}, \nu_{2}, \dots, \nu_{n}$ ，则
$$
A[i][j] =
\begin{cases}
1, & (v_{i}, v_{j}) \text{或} < v_{i}, v_{j} \rangle \text{是} E(G) \text{中的边} \\
0, & (v_{i}, v_{j}) \text{或} < v_{i}, v_{j} \rangle \text{不是} E(G) \text{中的边}
\end{cases}
$$
<!-- page: 214 -->
2027年数据结构考研复习指导
考点追查 ▶ 图的邻接矩阵存储及相互转换（2011、2015、2018）
对带权图而言，若顶点 $v_{i}$ 和 $v_{j}$ 之间有边相连，则邻接矩阵中对应位置存放该边的权值；若顶点 $v_{i}$ 和 $v_{j}$ 不相连，则通常用0或∞表示这两个顶点之间不存在边：
$$
A[i][j] = \begin{cases}
w_{ij}, & (v_{i}, v_{j}) \text{或} < v_{i}, v_{j} > \text{是 } E(G) \text{中的边} \\
0 \text{或} \infty, & (v_{i}, v_{j}) \text{或} < v_{i}, v_{j} > \text{不是 } E(G) \text{中的边}
\end{cases}
$$
图6.5展示了有向图、无向图及带权图（网）对应的邻接矩阵。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 有向图 $G_{1}$ 及其邻接矩阵
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 无向图 $G_{2}$ 及其邻接矩阵
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c) 网及其邻接矩阵（对角线元素也经常用0表示）
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图6.5 有向图、无向图及网的邻接矩阵 考点追查 ▶ （算法题）邻接矩阵的遍历及顶点的度的计算（2021、2023） 图的邻接矩阵存储结构定义如下： # 注意 ① 在简单应用中，可以直接使用二维数组作为图的邻接矩阵（顶点信息等均可省略）。 ② 当邻接矩阵元素仅表示相应边是否存在时，EdgeType 可用值为 0 和 1 的枕举类型。 ③ 邻接矩阵表示法的空间复杂度为 $O(n^{2})$，其中 $n$ 为图的顶点数[F]。 考点追查 ▶ 邻接矩阵的遍历的时间复杂度（2021） 邻接矩阵表示法具有以下特点： ① 无向图的邻接矩阵一定是对称矩阵，因此实际存储时只需保存上（或下）三角部分。在顶点编号固定的条件下，该邻接矩阵是唯一的。 考点追查 ▶ 基于邻接矩阵的顶点的度的计算（2013、2021、2023） ② 对于无向图，邻接矩阵第 $i$ 行（或第 $i$ 列）非零元素（或非∞元素）的数量正好是顶点 $i$ 的度 $\mathrm{TD}(v_i)$。 <!-- page: 215 --> 第6章图 ③ 对于有向图，邻接矩阵第 $i$ 行非零元素（或非 $\infty$ 元素）的数量是顶点 $i$ 的出度 $\mathrm{OD}(\nu_{i})$：第 $i$ 列非零元素（或非 $\infty$ 元素）的数量则是顶点 $i$ 的入度 $\mathrm{ID}(\nu_{i})$。 ④ 使用邻接矩阵存储图时，很容易判断任意两个顶点之间是否有边相连，但要确定图中有多少条边，通常需要遍历整个矩阵，时间代价较大。 ⑤ 稠密图（边数较多的图）更适合采用邻接矩阵存储。 **特点信息** ▶ 计算 A2 并说明 $\mathrm{An}[\mathrm{j}][\mathrm{j}]$ 的含义（2015） ⑥ 设图 $G$ 的邻接矩阵为 $A, A^n$ 的元素 $A^n[i][j]$ 代表从顶点 $i$ 到顶点 $j$ 长度为 $n$ 的路径数量。这一结论了解即可，具体证明可参考离散数学教材。 ## 6.2.2 邻接表法 当图为稀疏图时，使用邻接矩阵法显然会浪费大量存储空间。而邻接表法结合了顺序存储与链式存储的优点，能显著减少这种不必要的空间开销。 所谓邻接表，是指对图 $G$ 中的每个顶点 $\nu_{i}$ 建立一个单链表。第 $i$ 个单链表中的结点表示依附于顶点 $\nu_{i}$ 的边（对于有向图，这些边是以 $\nu_{i}$ 为尾的弧），该链表称为顶点 $\nu_{i}$ 的边表（有向图中也称出边表）。边表的头指针与顶点的数据信息采用顺序存储，称为顶点表。因此，邻接表中包含两类结点：顶点表结点和边表结点，如图 6.6 所示。 | 顶点域 | 边表头指针 | | --- | --- | | data | firstarc | | 顶点表结点 | | | 邻接点域 | 指针域 | | --- | --- | | adjvex | nextarc | | 边表结点 | | 图 6.6 顶点表和边表结点结构 顶点表结点由两个域组成：顶点域（data）存储顶点 $\nu_{i}$ 的相关信息，边表头指针域（firstarc）指向其第一条邻接边的边表结点。边表结点至少包含两个域：邻接点域（adjvex）存储与该顶点邻接的另一顶点编号，指针域（nextarc）指向下一条边的边表结点。 **特点信息** ▶ 图的邻接表存储的应用（2014） 无向图和有向图的邻接表表示分别如图 6.7 和图 6.8 所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 无向图 $G$
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 无向图 $G$ 的邻接表的表示
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 有向图 $G$
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 6.7 无向图的邻接表表示
(b) 有向图 $G$ 的邻接表的表示
图 6.8 有向图的邻接表表示
<!-- page: 216 -->
2027年数据结构考研复习指导
图的邻接表存储结构定义如下：
| #define MaxVertexNum 100 | //图中顶点数目的最大值 |
| --- | --- |
| typedef struct ArcNode{ | //边表结点 |
| int adjvex; | //该弧所指向的顶点的位置 |
| struct ArcNode *nextarc; | //指向下一条弧的指针 |
| //InfoType info; | //网的边权值 |
| }ArcNode; | |
| typedef struct VNode{ | //顶点表结点 |
| VertexType data; | //顶点信息 |
| ArcNode *firstarc; | //指向第一条依附该顶点的弧的指针 |
| }VNode,AdjList[MaxVertexNum]; | |
| typedef struct{ | |
| AdjList vertices; | //邻接表 |
| int vexnum,arcnum; | //图的顶点数和弧数 |
| }ALGraph; | //ALGraph 是以邻接表存储的图类型 |
邻接表表示法具有以下特点：
① 若 $G$ 为无向图，所需存储空间为 $O(|V| + 2|E)$；若为有向图，则为 $O(|V| + |E|)$。前者包含系数 2，是因为无向图中每条边在邻接表中会出现两次。
**修改进修** 邻接矩阵法和邻接表法的适用性分析（2011）
② 对于稀疏图（边数较少的图），采用邻接表表示能极大节省存储空间。
③ 在查找指定顶点的所有邻接点时，邻接表只需遍历对应的边表；而邻接矩阵则需扫描对应整行，效率较低。然而，若要判断两个顶点之间是否存在边，邻接矩阵支持 $O(1)$ 的直接访问；而邻接表需要线性查找对应的边表，效率较低。
④ 在无向图的邻接表中，顶点的度等于其邻接表中边表结点的个数。对于有向图，顶点的出度等于其邻接表中边表结点的个数；而入度则需遍历所有顶点的边表，统计所有边表中（adjvex）域等于该顶点编号的结点总数。
⑤ 邻接表的表示不唯一，因为每个顶点对应的边表中，各边结点的链接顺序可以是任意的，它取决于建立邻接表的算法及输入边的次序。