6.2.3 十字链表
## 6.2.3 十字链表
十字链表是有向图的一种链式存储结构。在十字链表中，每条弧用一个结点（称为弧结点）表示，每个顶点也用一个结点（称为顶点结点）表示。这两种结点的结构如下所示。
| 弧结点 | | | | | 顶点结点 | | |
| --- | --- | --- | --- | --- | --- | --- | --- |
| tailvex | headvex | hlink | tlink | {info} | data | firstin | firstout |
弧结点包含五个域：tailvex 和 headvex 域分别存放弧尾顶点和弧头顶点的编号；头链域 hlink 指向弧头相同的下一条弧；尾链域 tlink 指向弧尾相同的下一条弧；info 域存放该弧的相关信息。这样，弧头相同的弧在同一个链表上，弧尾相同的弧也在同一个链表上。
顶点结点包含三个域：data 域存放该顶点的数据信息，如顶点名称；firstin 域指向以该顶点为弧头的第一条弧；firstout 域指向以该顶点为弧尾的第一条弧。
图 6.9 为有向图的十字链表表示法。
<!-- page: 217 -->
第6章图
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b)
图6.9 有向图的十字链表表示（弧结点省略info域）
注意，顶点结点之间是顺序存储的，弧结点省略了info域。
在十字链表中，既容易找到以 $V_{i}$ 为尾的弧，也容易找到以 $V_{i}$ 为头的弧。因此，很容易求得顶点的出度和入度。图的十字链表的表示形式不唯一，取决于弧的输入顺序。
## 6.2.4 邻接多重表
邻接多重表是无向图的一种链式存储结构。虽然邻接表可以方便地获取顶点和边的信息，但在执行如判断两个顶点之间是否存在边等操作时，需分别遍历两个顶点的边表，效率较低。邻接多重表通过将每条边仅用一个结点表示，从而在判断边时只需遍历一次，提升了效率。
与十字链表类似，在邻接多重表中，每条边用一个结点表示，其结构如下。
| ivex | ilink | jvex | jlink | (info) |
| --- | --- | --- | --- | --- |
其中，ivex 和 jvex 域存放该边依附的两个顶点的编号；ilink 域指向依附于顶点 ivex 的下一条边；jlink 域指向依附于顶点 jvex 的下一条边，info 域存放该边的相关信息。
每个顶点也用一个结点表示，包含如下所示的两个域。
| data | firstedge |
| --- | --- |
其中，data 域存放该顶点的相关信息，firstedge 域指向依附于该顶点的第一条边。
在邻接多重表中，所有依附于同一顶点的边串联在同一链表中。由于每条边依附于两个顶点，其对应的边结点同时链接在两个链表中。对无向图而言，其邻接多重表与邻接表的主要区别在于：邻接表用两个结点表示同一条无向边，而邻接多重表仅用一个。
**特点设计** ▶ 图的邻接多重表表示的分析（2024）
图6.10为无向图的邻接多重表表示。邻接多重表的基本操作与邻接表类似。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图6.10 无向图的邻接多重表表示（边结点省略info域）
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图的四种存储方式的总结如表6.1所示。
<!-- page: 218 -->
2027年数据结构考研复习指导
表 6.1 图的四种存储方式的总结
| | 邻接矩阵 | 邻接表 | 十字链表 | 邻接多重表 |
| --- | --- | --- | --- | --- |
| 空间复杂度 | O([l]²) | 无向图：O([l] + 2|E])
有向图：O([l] + |E]) | O([l] + |E]) | O([l] + |E]) |
| 找相邻边 | 遍历对应行或列的时间
复杂度为 O([l]) | 找有向图的入度必须遍历
整个邻接表 | 很方便 | 很方便 |
| 删除边或顶点 | 删除边很方便，删除顶
点需要大量移动数据 | 无向图中删除边或顶点都
不方便 | 很方便 | 很方便 |
| 适用于 | 稠密图 | 稀疏图和其他 | 只能存有向图 | 只能存无向图 |
| 表示方式 | 唯一 | 不唯一 | 不唯一 | 不唯一 |
## 6.2.5 图的基本操作
图的基本操作独立于其存储结构，但不同存储方式下的具体实现算法性能会有所不同。在设计具体算法时，应根据需求选择合适的存储方式以提高效率。
图的基本操作主要包括（仅抽象地考虑，所以忽略各变量的类型）：
- Adjacent(G, x, y)：判断图 G 中是否存在边 <x, y=""> 或 (x, y)。
- Neighbors(G, x)：列出图 G 中与顶点 x 邻接的所有边。
- InsertVertex(G, x)：在图 G 中插入顶点 x。
- DeleteVertex(G, x)：从图 G 中删除顶点 x 及其相关的所有边。
- AddEdge(G, x, y)：若无向边(x, y)或有向边<x, y="">不存在，则将其添加到图 G 中。
- RemoveEdge(G, x, y)：若无向边(x, y)或有向边<x, y="">存在，则从图 G 中删除该边。
- FirstNeighbor(G, x)：查找图 G 中顶点 x 的第一个邻接点。若存在则返回顶点号；若 x 没有邻接点或图中不存在 x，则返回 -1。
- NextNeighbor(G, x, y)：假设顶点 y 是顶点 x 的一个邻接点，返回除 y 外顶点 x 的下一个邻接点的顶点号。若 y 是 x 的最后一个邻接点，则返回 -1。
- Get_edge_value(G, x, y)：获取图 G 中边(x, y)或<x, y="">对应的权值。
- Set_edge_value(G, x, y, v)：设置图 G 中边(x, y)或<x, y="">对应的权值为 v。
此外，还有图的遍历算法：按照某种顺序访问图中的每个顶点且仅访问一次。常见的图遍历算法包括深度优先遍历（DFS）和广度优先遍历（BFS），具体内容将在下一节详细讨论。
## 6.2.6 本节试题精选
### 一、单项选择题
01. 下列关于图的存储结构的说法中，错误的是（）。
A. 使用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点数有关，与边数无关
B. 邻接表只用于有向图的存储，邻接矩阵适用于有向图和无向图
C. 若一个有向图的邻接矩阵的对角线以下的元素为 0，则该图的拓扑序列必定存在
D. 存储无向图的邻接矩阵是对称的，所以只需存储邻接矩阵的下（或上）三角部分
02. 若图的邻接矩阵中主对角线上的元素皆为 0，其余元素全为 1，则该图一定（）。
A. 是无向图
B. 是有向图
C. 是完全图
D. 不是带权图</x,></x,></x,></x,>
<!-- page: 219 -->
第6章 图
207
03. 在含有 $n$ 个顶点和 $e$ 条边的无向图的邻接矩阵中，零元素的个数为（）。
A. $e$
B. $2e$
C. $n^{2} - e$
D. $n^{2} - 2e$
04. 带权有向图 $G$ 用邻接矩阵存储，则 $v_{i}$ 的入度等于邻接矩阵中（）。
A. 第 $i$ 行非 $\infty$ 的元素个数
B. 第 $i$ 列非 $\infty$ 的元素个数
C. 第 $i$ 行非 $\infty$ 且非0的元素个数
D. 第 $i$ 列非 $\infty$ 且非0的元素个数
05. 一个有 $n$ 个顶点的图用邻接矩阵 $A$ 表示，若图为有向图，顶点 $v_{i}$ 的入度是（）；若图为无向图，顶点 $v_{i}$ 的度是（）。
A. $\sum_{i = 1}^{n}A[i][j]$
B. $\sum_{j = 1}^{n}A[j][i]$
C. $\sum_{i = 1}^{n}A[j][i]$
D. $\sum_{j = 1}^{n}A[j][i]$ 或 $\sum_{j = 1}^{n}A[i][j]$
06. 从邻接矩阵 $A = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}$ 可以看出，该图共有（①）个顶点；若是有向图，则该图共有（②）条弧；若是无向图，则共有（③）条边。
① A. 9 B. 3 C. 6 D. 1 E. 以上答案均不正确
② A. 5 B. 4 C. 3 D. 2 E. 以上答案均不正确
③ A. 5 B. 4 C. 3 D. 2 E. 以上答案均不正确
07. 以下关于图的存储结构的叙述中，正确的是（）。
A. 一个图的邻接矩阵表示唯一，邻接表表示唯一
B. 一个图的邻接矩阵表示唯一，邻接表表示不唯一
C. 一个图的邻接矩阵表示不唯一，邻接表表示唯一
D. 一个图的邻接矩阵表示不唯一，邻接表表示不唯一
08. 矩阵 $A$ 是有向图 $G$ 的邻接矩阵，若矩阵 $A^2$ 的某元素 $a_{i,j}^2 = 3$，则说明（）。
A. 从顶点 $i$ 到 $j$ 存在 3 条长度为 2 的路径
B. 从顶点 $i$ 到 $j$ 存在 3 条长度不超过 2 的路径
C. 从顶点 $i$ 到 $j$ 存在 2 条长度为 3 的路径
D. 从顶点 $i$ 到 $j$ 存在 2 条长度不超过 3 的路径
09. 用邻接表法存储图所用的空间大小（）。
A. 与图的顶点数和边数有关
B. 只与图的边数有关
C. 只与图的顶点数有关
D. 与边数的平方有关
10. 若邻接表中有奇数个边表结点，则（）。
A. 图中有奇数个顶点
B. 图中有偶数个顶点
C. 图为无向图
D. 图为有向图
11. 在有向图的邻接表存储结构中，顶点 $v$ 在边表中出现的次数是（）。
A. 顶点 $v$ 的度
B. 顶点 $v$ 的出度
C. 顶点 $v$ 的入度
D. 依附于顶点 $v$ 的边数
12. $n$ 个顶点的无向图的邻接表最多有（）个边表结点。
A. $n^{2}$
B. $n(n - 1)$
C. $n(n + 1)$
D. $n(n - 1) / 2$
13. 设某无向图中有 $n$ 个顶点和 $e$ 条边，则建立该图的邻接表的时间复杂度为（）。
A. $O(n + e)$
B. $O(n^{2})$
C. $O(ne)$
D. $O(n^{3})$
<!-- page: 220 -->
2027年数据结构考研复习指导
14. 假设有 $n$ 个顶点、$e$ 条边的有向图用邻接表所示，则删除与某个顶点 $v$ 相关的所有边的时间复杂度为（）。
A. $O(n)$
B. $O(e)$
C. $O(n + e)$
D. $O(ne)$
15. 设 $n$ 个顶点、$e$ 条边的有向图用邻接表表示，则求某顶点 $v$ 的入度的时间复杂度为（）。
A. $O(n)$
B. $O(e)$
C. $O(n + e)$
D. $O(ne)$
16. 对邻接表的叙述中，（）是正确的。
A. 无向图的邻接表中，第 $i$ 个顶点的度为第 $i$ 个链表中结点数的两倍
B. 邻接表比邻接矩阵的操作更简便
C. 邻接矩阵比邻接表的操作更简便
D. 求有向图顶点的度，必须遍历整个邻接表
17. 邻接多重表是（）的存储结构。
A. 无向图
B. 有向图
C. 无向图和有向图
D. 都不是
18. 十字链表是（）的存储结构。
A. 无向图
B. 有向图
C. 无向图和有向图
D. 都不是
19. 【2013统考真题】设图的邻接矩阵 $A$ 如下所示，各顶点的度依次是（）。
$$
A = \left[ \begin{array}{cccc}
0 & 1 & 0 & 1 \\
0 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 \\
1 & 0 & 0 & 0
\end{array} \right]
$$
A. $1, 2, 1, 2$
B. $2, 2, 1, 1$
C. $3, 4, 2, 3$
D. $4, 4, 2, 2$
20. 【2024统考真题】若无向图 $G = (V, E)$ 的邻接多重表如下图所示，则 $G$ 中顶点 $b$ 与 $d$ 的度分别是（）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
A. 0, 2 B. 2, 4 C. 2, 5 D. 3, 4 ## 二、综合应用题 01. 已知带权有向图 $G$ 的邻接矩阵如下图所示，请画出该带权有向图 $G$ 。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 221 --> 第6章 图 209 02. 设图 $G = (V, E)$ 以邻接表存储，如下图所示。画出其邻接矩阵存储及图 $G$。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
03. 对 $n$ 个顶点的无向图和有向图，分别采用邻接矩阵和邻接表表示时，试问： 1）如何判别图中有多少条边？ 2）如何判别任意两个顶点 $i$ 和 $j$ 是否有边相连？ 3）任意一个顶点的度是多少？ 04. 如何对无环有向图中的顶点重新编号，使得该图的邻接矩阵中所有的 1 都集中到对角线以上？ 05. 写出从图的邻接表表示转换成邻接矩阵表示的算法。 06.【2015统考真题】已知含有5个顶点的图 $G$ 如右图所示。 请回答下列问题： 1）写出图 $G$ 的邻接矩阵 $A$ （行，列下标从0开始）。 2）求 $A^2$，矩阵 $A^2$ 中位于0行3列元素值的含义是什么？ 3）若已知具有 $n (n \geqslant 2)$ 个顶点的图的邻接矩阵为 $B$，则 $B^m (2 \leqslant m \leqslant n)$ 中非零元素的含义是什么？
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
07.【2021统考真题】已知无向连通图 $G$ 由顶点集 $V$ 和边集 $E$ 组成， $|E| > 0$，当 $G$ 中度为奇数的顶点个数为不大于2的偶数时，$G$ 存在包含所有边且长度为 $|E|$ 的路径（称为EL路径）。设图 $G$ 采用邻接矩阵存储，类型定义如下： 请设计算法 int IsExistEL(MGraph G)，判断 G 是否存在 EL 路径，若存在，则返回 1，否则返回 0。要求： 1）给出算法的基本设计思想。 2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。 3）说明你所设计算法的时间复杂度和空间复杂度。 08.【2023统考真题】已知有向图 $G$ 采用邻接矩阵存储，类型定义如下： 将图中出度大于入度的顶点称为K顶点。例如，在右图中，顶点 $a$ 和 $b$ 为K顶点。 请设计算法 int printVertices(MGraph G)，对给定的任意非空有向图G，输出G中所有的K顶点，并返回K顶点的个数。要求：
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 222 -->
2027年数据结构考研复习指导
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
## 6.2.7 答案与解析
### 一、单项选择题
#### 01. B
对于有 $n$ 个顶点的图，若采用邻接矩阵表示，不考虑压缩存储，则存储空间大小为 $O(n^{2})$，选项 A 正确。邻接表可用于存储无向图，只是把每条边都视为两条方向相反的有向边，因此需要存储两次，选项 B 错误。因为邻接矩阵中对角线以下的元素全为 0，所以若存在 $<i, j="">$，则必有 $i < j$，由传递性可知图中路径的顶点编号是依次递增的，假设存在环 $k \rightarrow \cdots \rightarrow j \rightarrow k$，由题设可知 $k < j < k$，矛盾，所以不存在环，拓扑序列必定存在，选项 C 正确。选项 D 显然正确。
### 注意
若邻接矩阵对角线以下（或以上）的元素全为 0，则图中必然不存在环，即拓扑序列一定存在，但这并不能说明拓扑序列是唯一的。
#### 02. C
除主对角线上的元素外，其余元素全为 1，说明任意两个顶点之间都有边相连，因此该图一定是完全图。
#### 03. D
在无向图的邻接矩阵中，矩阵大小为 $n^2$，非零元素的个数为 $2e$，所以零元素的个数为 $n^2 - 2e$。读者应掌握此题的变体，即当无向图变为有向图时，能够求出零的个数和非零的个数。
#### 04. D
带权有向图的邻接矩阵中，0 和 $\infty$ 表示的都不是有向边，而入度是由邻接矩阵的列中元素计算出来的；出度是由邻接矩阵的行中元素计算出来的。
#### 05. B、D
有向图的入度是其第 $i$ 列的非 0 元素之和，无向图的度是第 $i$ 行或第 $i$ 列的非 0 元素之和。
#### 06. B、B、D
邻接矩阵的顶点数等于矩阵的行（列）数，有向图的边数等于矩阵中非零元素的个数，无向图的边数等于矩阵中非零元素个数的一半。
### 注意
本题中所给的矩阵为对称矩阵，若不是对称矩阵，则必然不可能是无向图。
#### 07. B
邻接矩阵表示唯一是因为图中边的信息在矩阵中有确定的位置，邻接表不唯一是因为邻接表的建立取决于读入边的顺序和边表中的插入算法。
#### 08. A
设图 $G$ 的邻接矩阵为 $A$，$A^n$ 的元素 $a_{i,j}^n$ 等于从顶点 $i$ 到 $j$ 的长度为 $n$ 的路径的数目，因此 $a_{i,j}^2 = 3$ 表示从顶点 $i$ 到 $j$ 存在 3 条长度为 2 的路径。该结论记住即可。
#### 09. A
邻接表存储时，顶点数 $n$ 决定了顶点表的大小，边数 $e$ 决定了边表结点的个数，且无向图的</i,>
<!-- page: 223 -->
第6章 图
211
每条边存储两次，总存储空间为 $O(n + 2e)$。而邻接矩阵只与图的顶点数有关，为 $O(n^2)$。
10. D
无向图采用邻接表表示时，每条边存储两次，所以其边表结点的个数为偶数。题中边表结点为奇数个，所以必然是有向图，且有奇数条边。
11. C
题中的边表是不包括顶点表的。因为任何顶点 $u$ 对应的边表中存放的都是以 $u$ 为起点的边所对应的另一个顶点 $v$。从而 $v$ 在边表中出现的次数也就是它的入度。
12. B
最多有 $n(n - 1) / 2$ 条边，每条边在邻接表中存储两次，因此边表结点最多为 $n(n - 1)$ 个。
13. A
建立图的邻接表需要遍历所有的顶点和边，每个顶点有一个顶点表结点，每条边需要创建一个边表结点并插入到相应的链表中。因此，共需 $n + 2e$ 次操作，时间复杂度为 $O(n + e)$。
14. C
与顶点 $v$ 相关的边包括出边和入边，对于出边，只需遍历 $v$ 的顶点表结点和其指向的边表；对于入边，则需遍历整个边表。先删除出边；删除 $v$ 的顶点表结点的单链表，出边数最多为 $n - 1$，时间复杂度为 $O(n)$；再删除入边；扫描整个边表（扫描剩余全部顶点表结点及其指向的边表），删除所有的顶点 $v$ 的入边，时间复杂度为 $O(n + e)$。因此总时间复杂度为 $O(n + e)$。
15. C
为了求顶点 $v$ 的入度，只需要遍历邻接表中的所有边表，检查每条边是否指向顶点 $v$，这相当于遍历整个邻接表，因此算法的时间复杂度为 $O(n + e)$。
16. D
无向图的邻接表中，第 $i$ 个顶点的度为第 $i$ 个链表中的结点数，所以选项 A 错。邻接表和邻接矩阵对于不同的操作各有优势，选项 B 和 C 都不准确。有向图顶点的度包括出度和入度，对于出度，需要遍历顶点表结点所对应的边表；对于入度，则需要遍历剩下的全部边表。
17. A
邻接多重表是无向图的存储结构。
18. B
十字链表是有向图的存储结构。
19. C
邻接矩阵 $A$ 为非对称矩阵，说明图是有向图，度为入度与出度之和。各顶点的度是矩阵中此顶点对应的行（对应出度）和列（对应入度）的非零元素之和。
20. B
在邻接多重表中，统计一个顶点的入度、出度或度数（入度+出度）时，只需考虑所有的边结点。下图是邻接多重表的边结点的结构：
| ivex | ilink | jvex | jlink | info |
| --- | --- | --- | --- | --- |
其中，ivex表示弧头的编号，ilink域指向下一个弧头相同的边结点，jvex表示弧尾的编号，jlink域指向下一个弧尾相同的边结点。根据定义可知：求 $x$ 号顶点的入度时，只需统计jvex域等于 $x$ 的边结点个数；求 $x$ 号顶点的出度时，只需统计ivex域等于 $x$ 的边结点个数； $x$ 号顶点的度
<!-- page: 224 -->
2027年数据结构考研复习指导
数为入度和出度之和。顶点 $b$ 的编号为1，统计可知：入度为1，出度为1，度数为2。顶点 $d$ 的编号为3，统计可知：入度为1，出度为3，度数为4。