6.2 图的存储及基本操作·习题
复习入口
6.2 图的存储及基本操作 · 6.2.1 邻接矩阵法 · 6.2.2 邻接表法 · 6.2.3 十字链表 · 6.2.4 邻接多重表 · 6.2.5 图的基本操作
本节共28题:选择题20题,综合应用题8题。每题答案紧接题目折叠显示。
文字转录进度:28/28题。已转录题目的题干、选项和解析可编辑;示意图按需保留。
单项选择题
单项选择题 01
原书题目P211 · 解析P214 · 目视转录
下列关于图的存储结构的说法中,错误的是( )。
A. 使用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图中的顶点数有关,与边数无关
B. 邻接表只用于有向图的存储,邻接矩阵适用于有向图和无向图
C. 若一个有向图的邻接矩阵的对角线以下的元素为 0,则该图的拓扑序列必定存在
D. 存储无向图的邻接矩阵是对称的,所以只需存储邻接矩阵中的下(或上)三角部分
查看答案与解析
答案:B。
n 个顶点的图,若采用邻接矩阵表示,不考虑压缩存储,则存储空间大小为 ,选项 A 正确。邻接表可用于存储无向图,只是把每条边都视为两条方向相反的有向边,因此需要存储两次,选项 B 错误。因为邻接矩阵中对角线以下的元素全为 0,所以若存在〈i,j〉,则必有 i<j,由连通性可知图中路径的顶点编号是依次递增的。假设存在环 k→……→j→k,由题设可知 k<j<k,矛盾,所以环不存在,拓扑序列必定存在,选项 C 正确。选项 D 显然正确。
注意:若邻接矩阵对角线以下(或以上)的元素为 0,则图中必然不存在环,即拓扑序列一定存在,但这并不能说明拓扑序列是唯一的。
单项选择题 02
原书题目P211 · 解析P214 · 目视转录
若图的邻接矩阵中主对角线上的元素皆为 0,其余元素全为 1,则该图一定( )。
A. 是无向图
B. 是有向图
C. 是完全图
D. 不是带权图
查看答案与解析
答案:C。
除主对角线上的元素外,其余元素全为 1,说明任意两个顶点之间都有边相连,因此该图一定是完全图。
单项选择题 03
原书题目P211 · 解析P215 · 目视转录
在含有 n 个顶点和 e 条边的无向图的邻接矩阵中,零元素的个数为( )。
A. e
B. 2e
C.
D.
查看答案与解析
答案:D。
在无向图的邻接矩阵中,矩阵大小为 ,非零元素的个数为 2e,所以零元素的个数为 。读者应掌握此题的变体,即当无向图变为有向图时,能够求出零的个数和非零的个数。
单项选择题 04
原书题目P211 · 解析P215 · 目视转录
带权有向图 G 用邻接矩阵存储,则 的入度等于邻接矩阵中( )。
A. 第 i 行非∞的元素个数
B. 第 i 列非∞的元素个数
C. 第 i 行非∞且非 0 的元素个数
D. 第 i 列非∞且非 0 的元素个数
查看答案与解析
答案:D。
带权有向图的邻接矩阵中,0 和∞表示的都不是有向边,而入度是由邻接矩阵的列中元素计算出来的,出度是由邻接矩阵的行中元素计算出来的。
单项选择题 05
原书题目P211 · 解析P215 · 目视转录
一个有 n 个顶点的图用邻接矩阵 A 表示,若图为有向图,顶点 的入度是( );若图为无向图,顶点 的度是( )。
A.
B.
C.
D. 或
查看答案与解析
答案:B、D。
有向图的入度是其第 i 列的非 0 元素之和,无向图的度是第 i 行或第 i 列的非 0 元素之和。
单项选择题 06
原书题目P211 · 解析P215 · 目视转录
从邻接矩阵
可以看出,该图共有(①)个顶点;若是有向图,则该图共有(②)条弧;若是无向图,则共有(③)条边。
①
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. 以上答案均不正确
查看答案与解析
答案:B、B、D。
邻接矩阵的顶点数等于矩阵的行(列)数,有向图的边数等于矩阵中非零元素的个数,无向图的边数等于矩阵中非零元素个数的一半。
注意:本题中所给的矩阵为对称矩阵,若不是对称矩阵,则必然不可能是无向图。
单项选择题 07
原书题目P211 · 解析P215 · 目视转录
以下关于图的存储结构的叙述中,正确的是( )。
A. 一个图的邻接矩阵表示唯一,邻接表表示唯一
B. 一个图的邻接矩阵表示唯一,邻接表表示不唯一
C. 一个图的邻接矩阵表示不唯一,邻接表表示唯一
D. 一个图的邻接矩阵表示不唯一,邻接表表示不唯一
查看答案与解析
答案:B。
邻接矩阵表示唯一是因为图中边的信息在矩阵中有确定的位置,邻接表不唯一是因为邻接表的建立取决于读入边的顺序和边表中的插入算法。
单项选择题 08
原书题目P211 · 解析P215 · 目视转录
矩阵 A 是有向图 G 的邻接矩阵,若矩阵 的某元素 ,则说明( )。
A. 从顶点 i 到 j 存在 3 条长度为 2 的路径
B. 从顶点 i 到 j 存在 3 条长度不超过 2 的路径
C. 从顶点 i 到 j 存在 2 条长度为 3 的路径
D. 从顶点 i 到 j 存在 2 条长度不超过 3 的路径
查看答案与解析
答案:A。
设图 G 的邻接矩阵为 A, 的元素 等于从顶点 i 到 j 的长度为 n 的路径的数目,因此 表示从顶点 i 到 j 存在 3 条长度为 2 的路径。该结论记住即可。
单项选择题 09
原书题目P212 · 解析P215 · 目视转录
用邻接表法存储图所用的空间大小( )。
A. 与图的顶点数和边数有关
B. 只与图的边数有关
C. 只与图的顶点数有关
D. 与边数的平方有关
查看答案与解析
答案:A。
邻接表存储时,顶点数 n 决定了顶点表的大小,边数 e 决定了边表结点的个数,且无向图的每条边存储两次,总存储空间为 。而邻接矩阵只与图的顶点数有关,为 。
单项选择题 10
原书题目P212 · 解析P215 · 目视转录
若邻接表中有奇数个边表结点,则( )。
A. 图中有奇数个结点
B. 图中有偶数个结点
C. 图为无向图
D. 图为有向图
查看答案与解析
答案:D。
无向图采用邻接表表示时,每条边存储两次,所以其边表结点的个数为偶数。题中边表结点为奇数个,所以必然是有向图,且有奇数条边。
单项选择题 11
原书题目P212 · 解析P215 · 目视转录
在有向图的邻接表存储结构中,顶点 v 在边表中出现的次数是( )。
A. 顶点 v 的度
B. 顶点 v 的出度
C. 顶点 v 的入度
D. 依附于顶点 v 的边数
查看答案与解析
答案:C。
题中的边表是不包括顶点表的。因为任何顶点 u 对应的边表中存放的都是以 u 为起点的边所对应的另一个顶点 v。从而 v 在边表中出现的次数也就是它的入度。
单项选择题 12
原书题目P212 · 解析P215 · 目视转录
n 个顶点的无向图的邻接表最多有( )个边表结点。
A.
B.
C.
D.
查看答案与解析
答案:B。
最多有 n(n-1)/2 条边,每条边在邻接表中存储两次,因此边表结点最多为 n(n-1) 个。
单项选择题 13
原书题目P212 · 解析P215 · 目视转录
设某无向图中有 n 个顶点和 e 条边,则建立该图的邻接表的时间复杂度是( )。
A.
B.
C.
D.
查看答案与解析
答案:A。
建立图的邻接表需要遍历所有的顶点和边,每个顶点有一个顶点表结点,每条边需要创建一个边表结点并插入到相应的链表中。因此,共需 n+2e 次操作,时间复杂度为 。
单项选择题 14
原书题目P212 · 解析P215 · 目视转录
假设有 n 个顶点、e 条边的有向图用邻接表表示,则删除与某个顶点 v 相关的所有边的时间复杂度为( )。
A.
B.
C.
D.
查看答案与解析
答案:C。
与顶点 v 相关的边包括出边和入边,对于出边,只需遍历 v 的顶点表结点和其指向的边表;对于入边,则需遍历整个边表。先删除出边:删除 v 的顶点表结点的单链表,出边数最多为 n-1,时间复杂度为 ;再删除入边:扫描整个边表(扫描剩余全部顶点表结点及其指向的边表),删除所有的顶点 v 的入边,时间复杂度为 。因此总时间复杂度为 。
单项选择题 15
原书题目P212 · 解析P216 · 目视转录
设 n 个顶点、e 条边的有向图用邻接表表示,则求某个顶点 v 的入度的时间复杂度为( )。
A.
B.
C.
D.
查看答案与解析
答案:C。
为了求顶点 v 的入度,只需要遍历邻接表中的所有边表,检查每条边是否指向顶点 v,这相当于遍历整个邻接表,因此算法的时间复杂度为 。
单项选择题 16
原书题目P212 · 解析P216 · 目视转录
对邻接表的叙述中,( )是正确的。
A. 无向图的邻接表中,第 i 个顶点的度为第 i 个链表中结点数的两倍
B. 邻接表比邻接矩阵的操作更简便
C. 邻接矩阵比邻接表的操作更简便
D. 求有向图结点的度,必须遍历整个邻接表
查看答案与解析
答案:D。
无向图的邻接表中,第 i 个顶点的度为第 i 个链表中的结点数,所以选项 A 错。邻接表和邻接矩阵对于不同的操作各有优势,选项 B 和 C 都不准确。有向图结点的度包括出度和入度,对出度,需要遍历顶点表结点所对应的边表,对入度,则需要遍历剩下的全部边表。
单项选择题 17
原书题目P212 · 解析P216 · 目视转录
邻接多重表是( )的存储结构。
A. 无向图
B. 有向图
C. 无向图和有向图
D. 都不是
查看答案与解析
答案:A。
邻接多重表是无向图的存储结构。
单项选择题 18
原书题目P212 · 解析P216 · 目视转录
十字链表是( )的存储结构。
A. 无向图
B. 有向图
C. 无向图和有向图
D. 都不是
查看答案与解析
答案:B。
十字链表是有向图的存储结构。
单项选择题 19
原书题目P212 · 解析P216 · 目视转录
【2013 统考真题】设图的邻接矩阵 A 如下所示,各顶点的度依次是( )。
A. 1,2,1,2
B. 2,2,1,1
C. 3,4,2,3
D. 4,4,2,2
查看答案与解析
答案:C。
邻接矩阵 A 为非对称矩阵,说明图是有向图,度为入度与出度之和。各顶点的度是矩阵中此结点对应的行(对应出度)和列(对应入度)的非零元素之和。
单项选择题 20
原书题目P212 · 解析P216 · 目视转录
【2024 统考真题】若无向图 的邻接多重表如下图所示,则 G 中顶点 b 与 d 的度分别是( )。

A. 0、2
B. 2、4
C. 2、5
D. 3、4
查看答案与解析
答案:B。
在邻接多重表中,统计一个结点的入度、出度或度数(入度+出度)时,只需考虑所有的边结点。原书边结点的结构为 ivex | ilink | jvex | jlink | info。
其中,ivex 表示弧头的编号,ilink 域指向下一个弧头相同的边结点,jvex 表示弧尾的编号,jlink 域指向下一个弧尾相同的边结点。根据定义可知:求 x 号结点的入度时,只需统计 jvex 域等于 x 的边结点个数;求 x 号结点的出度时,只需统计 ivex 域等于 x 的边结点个数;x 号结点的度数为入度和出度之和。
顶点 b 的编号为 1,统计可知:入度为 1,出度为 1,度数为 2。顶点 d 的编号为 3,统计可知:入度为 1,出度为 3,度数为 4。
转录核对:题干为无向图,其邻接多重表中的 ivex、jvex 表示边的两个端点,不定义弧头/弧尾或入度/出度。原解析借用了有向图术语;实际只需统计两端点编号中 b、d 分别出现的次数,仍得到 2、4。
综合应用题
综合应用题 01
原书题目P213 · 解析P216 · 目视转录
已知带权有向图 G 的邻接矩阵如下所示,请画出该带权有向图 G。
查看答案与解析
带权有向图 G 如下图所示,顶点按矩阵顺序记为 a、b、c、d、e、f、g。

| 弧 | 权值 |
|---|---|
| a→b | 15 |
| a→c | 2 |
| a→d | 12 |
| b→e | 6 |
| c→e | 8 |
| c→f | 4 |
| d→g | 3 |
| e→g | 9 |
| f→d | 5 |
| f→g | 10 |
| g→b | 4 |
综合应用题 02
原书题目P213 · 解析P216 · 目视转录
设图 以邻接表存储,如下所示。画出其邻接矩阵存储及图 G。
1 → 2 → 3 → 4 → NULL
2 → 1 → 3 → 4 → 5 → NULL
3 → 1 → 2 → 4 → NULL
4 → 1 → 2 → 3 → 5 → NULL
5 → 2 → 4 → NULL
每行最左端为顶点表结点,其右侧为依次链接的边表结点。
查看答案与解析
其邻接矩阵存储如下所示。
在邻接表中,每条边存储了 2 次,在没有特殊说明时,通常默认其为无向图(当然,无向图也可视为具有对边的有向图)。该邻接表对应的图 G 如下所示。

综合应用题 03
原书题目P213 · 解析P217 · 目视转录
对 n 个顶点的无向图和有向图,分别采用邻接矩阵和邻接表表示时,试问:
- 如何判别图中有多少条边?
- 如何判别任意两个顶点 i 和 j 是否有边相连?
- 任意一个顶点的度是多少?
查看答案与解析
1)对于邻接矩阵表示的无向图,边数等于矩阵中 1 的个数除以 2;对于邻接表表示的无向图,边数等于边结点的个数除以 2。对于邻接矩阵表示的有向图,边数等于矩阵中 1 的个数;对于邻接表表示的有向图,边数等于边结点的个数。
2)在邻接矩阵表示的无向图或有向图中,对于任意两个顶点 i 和 j,邻接矩阵中 arcs[i][j] 或 arcs[j][i] 为 1 表示有边相连,否则表示无边相连。在邻接表表示的无向图或有向图中,对于任意两个顶点 i 和 j,若从顶点表结点 i 出发找到编号为 j 的边表结点或从顶点表结点 j 出发找到编号为 i 的边表结点,表示有边相连;否则无边相连。
3)对于邻接矩阵表示的无向图,顶点 i 的度等于第 i 行中 1 的个数;对于邻接矩阵表示的有向图,顶点 i 的出度等于第 i 行中 1 的个数,入度等于第 i 列中 1 的个数,度数等于它们的和。对于邻接表表示的无向图,顶点 i 的度等于顶点表结点 i 的单链表中边表结点的个数;对于邻接表表示的有向图,顶点 i 的出度等于顶点表结点 i 的单链表中边表结点的个数,顶点 i 的入度等于邻接表中所有编号为 i 的边表结点数;度数等于入度与出度之和。
综合应用题 04
原书题目P213 · 解析P217 · 目视转录
如何对无环有向图中的顶点重新编号,使得该图的邻接矩阵中所有的 1 都集中到对角线之上?
查看答案与解析
按各顶点的出度进行排序。n 个顶点的有向图,其顶点的最大出度是 n-1,最小出度为 0。这样排序后,出度最大的顶点编号为 1,出度最小的顶点编号为 n。之后,进行调整,即只要存在弧〈i,j〉,就不管顶点 j 的出度是否大于顶点 i 的出度,都把 i 编号在顶点 j 的编号之前,因为只有 i<j,弧〈i,j〉对应的 1 才能出现在邻接矩阵的上三角。
通过后面小节的学习,会发现采用拓扑排序并依次编号是一种更为简便的方法。
综合应用题 05
原书题目P213 · 解析P217 · 目视转录
写出从图的邻接表表示转换成邻接矩阵表示的算法。
查看答案与解析
整理注记
转换邻接表为邻接矩阵时,先将整个矩阵初始化为0,再遍历边并置相应元素为1。原书文字说明包含初始化要求,代码片段中使用时需落实。
算法思想:设图的顶点分别存储在数组 v[n] 中。首先初始化邻接矩阵。遍历邻接表,在依次遍历顶点 v[i] 的边链表时,修改邻接矩阵的第 i 行的元素值。若链表边结点的值为 j,则置 arcs[i][j]=1。遍历完邻接表时,整个转换过程结束。此算法对于无向图、有向图均适用。
void Convert(ALGraph &G,int arcs[M][N]){
// 此算法将邻接表方式表示的图G转换为邻接矩阵arcs
for(i=0;i<n;i++){ // 依次遍历各顶点链结点为头的边链表
p=(G->v[i]).firstarc; // 取出顶点i的第一条出边
while(p!=NULL){ // 遍历边链表
arcs[i][p->adjvex]=1;
p=p->nextarc; // 取下一条出边
} // while
} // for
}
综合应用题 06
原书题目P213 · 解析P217 · 目视转录
【2015 统考真题】已知含有 5 个顶点的图 G 如下所示。

请回答下列问题:
- 写出图 G 的邻接矩阵 A(行、列下标从 0 开始)。
- 求 ,矩阵 中位于 0 行 3 列元素值的含义是什么?
- 若已知具有 n()个顶点的图的邻接矩阵为 B,则 ()中非零元素的含义是什么?
查看答案与解析
考查图的邻接矩阵的性质。
1)图 G 的邻接矩阵 A 如下:
2) 如下:
0 行 3 列的元素值 3 表示从顶点 0 到顶点 3 之间长度为 2 的路径共有 3 条。
3)()中位于 i 行 j 列()的非零元素的含义是,图中从顶点 i 到顶点 j 的长度为 m 的路径条数。
综合应用题 07
原书题目P214 · 解析P218 · 目视转录
【2021 统考真题】已知无向连通图 G 由顶点集 V 和边集 E 组成,,当 G 中度为奇数的顶点个数为不大于 2 的偶数时,G 存在包含所有边且长度为 的路径(称为 EL 路径)。设图 G 采用邻接矩阵存储,类型定义如下:
typedef struct{ // 图的定义
int numVertices,numEdges; // 图中实际的顶点数和边数
char VerticesList[MAXV]; // 顶点表。MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
}MGraph;
请设计算法 int IsExistEL(MGraph G),判断 G 是否存在 EL 路径,若存在,则返回 1,否则返回 0。要求:
- 给出算法的基本设计思想。
- 根据设计思想,采用 C 或 C++ 语言描述算法,关键之处给出注释。
- 说明你所设计算法的时间复杂度和空间复杂度。
查看答案与解析
1)算法的基本设计思想。
本算法题属于送分题,题干已经告诉我们算法的思想。对于采用邻接矩阵存储的无向图,在邻接矩阵的每一行(列)中,非零元素的个数为本行(列)对应顶点的度。可以依次计算连通图 G 中各顶点的度,并记录度为奇数的顶点个数,若个数为 0 或 2,则返回 1,否则返回 0。
2)算法实现。
int IsExistEL(MGraph G){
// 采用邻接矩阵存储,判断图是否存在EL路径
int degree,i,j,count=0;
for(i=0;i<G.numVertices;i++){
degree=0;
for(j=0;j<G.numVertices;j++)
degree+=G.Edge[i][j]; // 依次计算各个顶点的度
if(degree%2!=0)
count++; // 对度为奇数的顶点计数
}
if(count==0||count==2)
return 1; // 存在EL路径,返回1
else
return 0; // 不存在EL路径,返回0
}
3)时间复杂度和空间复杂度。
算法需要遍历整个邻接矩阵,所以时间复杂度为 ,空间复杂度为 。
综合应用题 08
原书题目P214 · 解析P218 · 目视转录
【2023 统考真题】已知有向图 G 采用邻接矩阵存储,类型定义如下:
typedef struct{ // 图的类型定义
int numVertices,numEdges; // 图的顶点数和有向边数
char VerticesList[MAXV]; // 顶点表。MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
}MGraph;
将图中出度大于入度的顶点称为 K 顶点。例如,有向图中顶点 a、b、c、d,弧为 a→b、a→d、b→d、b→c、c→d,则顶点 a 和 b 为 K 顶点。
请设计算法 int printVertices(MGraph G),对给定的任意非空有向图 G,输出 G 中所有的 K 顶点,并返回 K 顶点的个数。要求:
- 给出算法的基本设计思想。
- 根据设计思想,采用 C 或 C++ 语言描述算法,关键之处给出注释。
查看答案与解析
1)算法的基本设计思想。
采用邻接矩阵表示有向图时,一行中 1 的个数为该行对应顶点的出度,一列中 1 的个数为该列对应顶点的入度。使用一个初值为零的计数器记录 K 顶点的个数。对图 G 的每个顶点,根据邻接矩阵计算其出度 outdegree 和入度 indegree,若 outdegree-indegree>0,则输出该顶点且计数器加 1。最后返回计数器的值。
2)用 C 语言描述的算法:
int printVertices(MGraph G){
// 采用邻接矩阵存储,输出K顶点,返回个数
int indegree,outdegree,k,m,count=0;
for(k=0;k<G.numVertices;k++){
indegree=outdegree=0;
for(m=0;m<G.numVertices;m++) // 计算顶点的出度
outdegree+=G.Edge[k][m];
for(m=0;m<G.numVertices;m++) // 计算顶点的入度
indegree+=G.Edge[m][k];
if(outdegree>indegree){
printf("%c",G.VerticesList[k]);
count++;
}
}
return count; // 返回K顶点的个数
}