第5章图
5.1　考纲要求及分析
【考纲要求】

(一)图的基本概念
(二)图的存储及基本操作

1. 邻接矩阵
2. 邻接表
3. 邻接多重表、十字链表
(三)图的遍历
1. 深度优先搜索
2. 广度优先搜索
(四)图的基本应用
1. 最小(代价)生成树
2. 最短路径
3. 拓扑排序
4. 关键路径
【考纲分析】

本章的特点是概念多、算法多、难度大、应用广,因此,需要深刻理解每个知识点,反复练


第5章
图

习,抓住规律,强化记忆,才能很好地解答这部分试题。本章要求如下。

(1)深刻理解图的定义和基本术语。图的基本概念比较复杂,复习时注意与线性结构
和树结构进行比较。
(2)掌握图的邻接矩阵、邻接表、邻接多重表、十字链表等存储结构,重点是邻接矩阵和
邻接表存储结构下基本操作的实现方法。
(3)熟练掌握图的深度优先遍历和广度优先遍历,以及遍历的算法实现。
(4)对于图的基本应用,掌握经典算法的基本思想和求解过程,包括Prim算法、
Kruskal算法、Dijkstra算法、Floyd算法、拓扑排序算法和关键路径算法等。
【试题分析】

从历年考题情况看,图是每年必考的内容,而且考试内容几乎覆盖本章所有知识点,出
题形式包括单项选择题和综合应用题。单项选择题的主要出题点是图的基本概念(不是单
纯考概念,而是在理解的基础上进行辨析)、图的存储结构(邻接矩阵和邻接表)、图的遍历、
图的基本应用(根据算法思想和求解过程回答问题); 综合应用题的主要出题点是根据给定
的实际应用问题(例如网络拓扑结构)综合运用图的定义、图的存储结构、图的基本应用等知
识点求解问题。图是最复杂的数据结构,也是应用最广的数据结构,出题频度最高,出题分
值最大,因此考生要特别关注本章,投入一定的精力进行复习,有针对性地多做习题。

5.2　图的基本概念
5.1 
考核知识点
2.
知识点名称重要程度难易程度出题情况(年份用后两位表示) 
图的定义★★★★☆ ◆◆◇◇◇ 单选:19 
综合(应用):11 、14 
图的基本术语★★★★★ ◆◆◆◇◇ 单选:09-11 、17 
综合(应用):18 

课件

123


全国硕士研究生招生考试计算机科学与技术学科联考
数据结构复习指导与真题解析

2.典型题解析
5.2 

【试题点拨】主要考查图中各顶点的度、入度和出度之和与边数的关系(握手定理)、路
径和路径长度的含义、连通图、连通分量的含义、生成树的含义、完全图的特点等,需要在透
彻理解图基本概念的基础上回答问题。

一、单项选择题

在一个无向图中,所有顶点的度数之和等于所有边数的() 倍。

A.1/
2 
B.
1 
C.
2 
D.
4 C 
n 

握手定理:设无向图中含有
n 
个顶点
e 
条边,则ΣD(vi 
)=2e 
。

i=1

n 
个顶点的强连通图至少有() 条边,其形状是( )。

A. n 
B. n 
+
1 
C. n 
-
1 
D. n 
×(
n 
-1) 
E. 
无回路F. 
有回路G. 
环状H. 
树状
A,
G 
例如,4 
个顶点的强连通图含有边数最少的情况如图5-1(a)所示,有回路的强连通
图含有的边数不一定最少。
1. 
2. 
图5-1　强连通图分析

3. 
4. 
具有10 
个顶点的无向连通图最少有() 条边,最多有() 条边。

A.
0 
B.
9 
C.45 
D.90 
B,
C n 
个顶点的无向连通图最少含有
n 
-
1 
条边,最多含有n(
n 
-1)/
2 
条边。
在含有
n 
个顶点的连通图中,任意一条简单路径的长度不可能超过( )。

A.
1 
B. 
n/
2 
C. n 
-
1 
D. n C 
若路径长度超过
n 
-1,则路径中必存在重复的顶点。
124


第5章
图

设无向图
G 
=

误的是( )。
(V,
E 
)和G=

'

' 

是
G 
的生成树,则下面的说法中错

5. 
6. 
7. 
8. 
(V,E), 如果G

'
' 
A.
6 
B.
7 
C.
8 
D.
9 
()≤≥1/228 
8设个顶点的无向图含有条边则将代入有现已-=,,,,neennen 
。有边每个顶点构成一个连通分量, 

B 

' 
。9知无向图非连通则=, 
n 

D 

'

'
'A. 
GGB. 
GG为的子图为的连通分量
'C. 
GGVVD. 
GG为的极小连通子图且是的一个无环子图
连通分量是无向图的极大连通子图其中极大的含义是包含依附于连通分量中顶,
。点的所有边所以连通分量中可能存在回路,, 
() 。G28 
是一个非连通无向图共有条边则该图至少有个顶点,, 
() () 一个具有个顶点的无向图最少有个连通分量最多有个连通,,
n 
A.
0 
B.
1 
C. 
1D. 
-nn 
(), ;无向图的连通分量最少只有一个是其自身该图是连通的最多有个该图没,
n 
()。以下关于有向图的说法中正确的是, 
A. 
强连通图中任何顶点到其他所有顶点都有弧
D. 
边集的子集和顶点集的子集可构成原有向图的子图
;强连通图中任何顶点到其他所有顶点都有路径但不一定都有弧有向图中所有,
;顶点的入度之和等于出度之和如果边集的子集中某条边的顶点不在顶点集的子

分量。
B,
D 

B. 
有向完全图一定是强连通图
C. 
某顶点的入度等于出度
B 
=

'

'

集中,则不能构成一个图,例如图G=(V, 
E),
V 
={1, 
2, 
3, 
4, 
5},
4, 
5)},V={1, 
2, 
3},E={(1, 
2)
不能构成
G 
的子图。

E 
={(1, 
2)
, 
(1, 
3)
, , 
(1, 
3)
, 
(2, 
3)
, 
(3, 

''

'

'

(1, 
4)
, 
(2, 
3)
, 
(3, 
4)
, 
(3, 
5)
, 
(
4)},满足V.
V 
且E.
E 
,但V和E

9. 
无向图
G 
有16 
条边,度为
4 
的顶点有
3 
个,度为
3 
的顶点有
4 
个,其余顶点的度

125


全国硕士研究生招生考试计算机科学与技术学科联考
数据结构复习指导与真题解析

均小于3,则图
G 
至少有() 个顶点。

A.10 
B.11 
C.12 
D.13 B 
设图
G 
至少有
x 
个顶点,根据顶点的度数之和与边数之间的关系,可以列出不等
式:3×4+4×3+(
x 
-3-4)×2≥16×2,解得
x 
至少为11 
。
-
2 
所示的有向图中,强连通分量的个数为( )。

A.
1 
B.
2 
C.
3 
D.
4 D 
该有向图的强连通分量如图5-
3 
所示。需要注意的是,强连通分量实际上是对有
向图的一种划分,设有向图G={V, 
E},V1, 
V2, 
…
, 
Vk 
是
V 
的
k 
个子集,则满足
: 
①
Vi 
≠.(1≤
i 
≤k);②Vi 
∩Vj 
=.(1≤i≠j≤k);③
V 
=V1 
∪V2 
∪…∪Vk 
。
10. 在如图5
图5-2　一个有向图图5-3　有向图的
4 
个强连通分量

二、综合应用题
【试题点拨】本节证明题要求掌握结论及证明过程。此类题目可能会以单项选择题的

形式给出。

1. 
证明:生成树中最长路径的起点和终点的度均为1。

用反证法证明。设v1, 
v2, 
…
, 
vk 
是生成树的一条最长路径,其中,v1 
为起点,vk 
为终点。若vk 
的度为2,取vk 
的另一个邻接点
v 
,由于生成树中无回路,所以,
v 
在最长路径上,显然v1, 
v2, 
…
, 
vk, v 
的路径最长,与假设矛盾。所以生成树中最
长路径的终点的度为1。同理可证起点v1 
的度不能大于1,只能为1。

2. 
证明:若无向图中各顶点的度均大于或等于2,则该图必然存在回路。

设无向图
G 
中含有
n 
个顶点
e 
条边,顶点vi 
的度为TD(vi 
), 则: 

Σ(n) TD(vi 
)=2e 
(1)

i=1

由于无向图中各顶点的度均大于或等于2,则
: 

Σ(n) TD(vi 
)≥2n 
(2)

i=1

126


第5章图
由式(1)和式(2),得: 
e ≥ n 
具有n 个顶点的无向连通图最少有n -1 条边,多于n -1 条边必然存在回路,该
图至少有n 条边,因而一定存在回路。
5.3　图的存储结构
5.3.1 考核知识点
知识点名称重要程度难易程度出题情况(年份用后两位表示) 
邻接矩阵★★★★★ ◆◆◇◇◇ 
单选:11-13 
综合(应用):11、15 
综合(算法):21 
邻接表★★★★★ ◆◆◆◇◇ 单选:11、12、16 
综合(应用):14 
邻接多重表★☆☆☆☆ ◆◆◆◆◇ 
十字链表★☆☆☆☆ ◆◆◆◆◇ 
5.3.2 典型题解析
一、单项选择题
【试题点拨】 主要考查邻接矩阵和邻接表的存储方法、存储特点、所需存储空间,以及
基于邻接矩阵和邻接表存储结构基本操作的实现方法及时空性能分析。
1. 有一个图的邻接矩阵为
0 2 5 
1 0 6 
2 6 0 
.
è
... 
.
.
÷÷÷
,则该图共有( )个顶点。
A. 3 B. 6 
C. 9 D. 以上答案均不正确
A 
127 
课件

全国硕士研究生招生考试计算机科学与技术学科联考
数据结构复习指导与真题解析

邻接矩阵是
3 
阶非对称方阵,则该图一定是具有
3 
个顶点的有向图。

具有
n 
个顶点
e 
条边的无向图采用邻接矩阵存储,则零元素的个数为( )。

A. e 
B.2e 
C. 
n2 
-
e 
D. 
n2 
-2e D 
无向图的邻接矩阵共有n2 
个元素,每条边在邻接矩阵中表示为对称位置,即非零
元素的个数为2e 
,则零元素的个数为n2 
-2e 
。
用邻接表存储图所用的空间大小( )。

A. 
与图的顶点数和边数都有关B. 
只与图的边数有关系
C. 
只与图的顶点数有关D. 
与边数的平方有关
A 
设图具有
n 
个顶点
e 
条边,则图的邻接表存储所需的存储空间为O(
n 
+e)。
下列() 的邻接矩阵是对称矩阵。

A. 
有向图B. 
无向图C. 
AOV 
网D. 
AOE 
网
B 
AOV 
网和AOE 
网都是有向图,有向图的邻接矩阵不一定对称。
在有向图的邻接表存储结构中,顶点
v 
在边表中出现的次数是( )。

A. 
顶点
v 
的度B. 
顶点
v 
的出度
C. 
顶点
v 
的入度D. 
依附于顶点
v 
的边数
C 
在有向图的邻接表存储结构中,顶点
v 
的出度是该顶点出边表中的结点个数,顶
点
v 
的入度是该顶点在所有边表中的出现次数。
具有
n 
个顶点的无向图,其邻接表最多有() 个边表结点。

2

A. n 
B. 
n(
n 
-1) C. 
n(
n 
+1) D. 
n(
n 
-1)/
2 B 
无向图最多有n(
n 
-1)/
2 
条边,在邻接表中每条边对应两个边表结点,即最多有
n(
n 
-1)个边表结点。
带权有向图
G 
采用邻接矩阵存储,则顶点
i 
的入度等于邻接矩阵中( )。

128

2. 
3. 
4. 
5. 
6. 
7. 

第5章
图

A. 
第
i 
行非∞的元素之和B. 
第
i 
列非∞的元素之和
C. 
第
i 
行非∞且非
0 
的元素个数D. 
第
i 
列非∞且非
0 
的元素个数
D 
在带权有向图的邻接矩阵中,主对角线是0,其他元素是对应边上的权值,则顶点
i 
的入度等于邻接矩阵中第
i 
列非∞且非
0 
的元素个数。
假设一个有向图具有
n 
个顶点
e 
条边,该有向图采用邻接矩阵存储,则删除与顶
点
i 
相关联的所有边的时间复杂度是( )。

A. 
O(n) B. 
O(e) C. 
O(
n 
+e) D. 
O(
n 
*e) 
A 
只需要将邻接矩阵第
i 
行和第
i 
列的所有元素置为0。
假设一个有向图具有
n 
个顶点
e 
条边,该有向图采用邻接表存储,则删除与顶点
i 
相关联的所有边的时间复杂度是( )。

A. 
O(n) B. 
O(e) C. 
O(
n 
+e) D. 
O(
n 
*e) 
C 
首先需要删除该顶点的出边表中的所有结点,然后遍历所有边表,删除边表中邻
接点域为该顶点的所有结点,最坏情况下的时间复杂度是O(
n 
+e)。

二、综合应用题

【试题点拨】主要考查给定一个图,写出其邻接矩阵和邻接表存储示意图;给定一个邻
接矩阵或邻接表,画出对应的图;计算图的某种存储结构具体需要多少存储空间等。此类题
目可能以单项选择题的形式给出。

8. 
9. 
1. 
已知一个连通图如图5-
4 
所示,试给出图的邻接矩阵和
邻接表存储示意图。
邻接矩阵表示如图5-
5 
所示,邻接表表示如图5-
6 
所示。图5-4　第1题图


图5-5　图的邻接矩阵表示图5-6　图的邻接表表示

129


全国硕士研究生招生考试计算机科学与技术学科联考数据结构复习指导与真题解析
2. 设无向网图G 含有n 个顶点e 条边,每个顶点的信息(假设只存储编号)占用2 字
节,每条边的权值信息占用4 字节,每个指针占用4 字节,计算采用邻接矩阵和邻
接表分别占用多少存储空间? 
邻接矩阵存储顶点信息的一维数组需要2n 字节,存储权值信息的二维数组需要
4n 2 字节,因此,邻接矩阵共需要4n 2 +2n 字节。邻接表的顶点表存储顶点信息
和边表的头指针,需要(2+4)×n =6n 字节,边表中共2e 个结点,每个结点需要
存储顶点编号、权值和指针信息,需要(2+4+4)×2e =20e 字节,因此,邻接表共
需要6n +20e 字节。
三、算法设计题
【试题点拨】 主要考查在邻接矩阵和邻接表存储结构下,图的基本操作的实现。邻接
矩阵的算法本质上是对二维数组的操作,邻接表的算法本质上是对单链表的操作,因此,只
要理解了图的邻接矩阵和邻接表存储结构,这部分的算法并不难。由于图的存储结构定义
篇幅较大,一般题目会给出相关定义,本节算法省略图的存储结构定义,请参考相关教材或
本书附带课件。
1. 设有向图G 采用邻接表存储,设计算法求图G 中每个顶点的入度。
由于有向图的邻接表存储了出边的信息,因此求某顶点i 的入度需要扫描所有出
边表,统计出边表中顶点i 的出现次数。为此,设一个累加器数组indegree[n],数
组下标为顶点的编号。 
void CountIn(ALGraph &G, int indegree[ ]) 
{ 
for (int i = 0; i < G.vertexNum; i++) //初始化各顶点的入度 
indegree[i] = 0; 
for (i = 0; i < G.vertexNum; i++) //依次遍历每个边表 
{ 
Node *p = G.adjlist[i].firstedge; 
while (p != NULL) 
{ 
indegree[p->adjvex]++; //将编号为p->adjvex 的顶点的入度加1 
p = p->next; 
} 
} 
} 
2. 设计算法,计算图中出度为零的顶点个数。
130

第5章图
在有向图的邻接矩阵中,顶点的出度等于该行非零元素的个数。据此,从第一行
开始,判断每行的非零元素个数是否为零,若是则计数器加1。 
int SumZero(MGraph &G) 
{ 
int count = 0, i, j; //记载出度为0 的顶点个数 
for (i = 0; i < G.vertexNum; i++) 
{ 
for (j = 0; j < G.vertexNum; j++) 
if (arcs[i][j] != 0) break; //该顶点的出度不为0 
if (j == G.vertexNum) count++; 
} 
return count; 
} 
5.4　图的遍历
5.4.1 考核知识点
知识点名称重要程度难易程度出题情况(年份用后两位表示) 
图的深度优先遍历操作★★★★☆ ◆◆◆◇◇ 单选:15、16、20 
图的广度优先遍历操作★★★★☆ ◆◆◆◇◇ 单选:13 
图的深度优先遍历算法★★☆☆☆ ◆◆◆◆◇ 
图的广度优先遍历算法★★☆☆☆ ◆◆◆◆◇ 单选:12 
5.4.2 典型题解析
一、单项选择题
【试题点拨】 图的遍历是本章的重点,主要考查给定一个图或图的存储结构,写出图的
深度优先遍历序列和广度优先遍历序列;判断是否为图的深度优先遍历序列和广度优先遍
131 
课件