数据结构(第二版)习题答案第8章
第
8章图
8.1选择题
（1）如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是（ D ）。
A．有向完全图 B．连通图 C．强连通图 D．有向无环图
（2）若邻接表中有奇数个表结点，则一定（ D ）。
A．图中有奇数个顶点 B．图中有偶数个顶点
C．图为无向图 D．图为有向图
（3）下列关于无向连通图特性的叙述中，正确的是（ A ）。
Ⅰ．所有顶点的度之和为偶数
Ⅱ．边数大于顶点个数减 1
Ⅲ．至少有一个顶点的度为 1
A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ
（4）假设一个有 n个顶点和 e条弧的有向图用邻接表表示，则删除与某个顶点 vi相关的
所有弧的时间复杂度是（ B ）。
A．O(n) B．O(e) C．O(n+e) D．O(n*e)
（5）已知一个有向图 8.30所示，则从顶点 a出发进行深度优先偏历，不可能得到的 DFS
序列为（ A ）。
A．a d b e f c B．a d c e f b C．a d c b f e D．a d e f c b
b
a c e f
d
图 8.30有向图
（6）无向图 G=（V，E），其中： V={a,b,c,d,e,f}，E={（a,b），（a,e），（a,c），（b,e），（c,f），
（f,d），（e,d）}，对该图进行深度优先遍历，得到的顶点序列正确的是（ D ）。
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b
（7）下列哪一个选项不是图 8.31所示有向图的拓扑排序结果（ C ）。
A．AFBCDE B．FABCDE C．FACBDE D．FADBCE
图 8.31 AOV网
（8）判断一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（ D ）。
A．单源最短路 Dijkstra算法 B．所有顶点对最短路 Floyd算法
C．广度优先遍历算法 D．深度优先遍历算法
（9）在一个带权连通图 G中，权值最小的边一定包含在 G的（ A ）。
A．最小生成树中 B．深度优先生成树中
C．广度优先生成树中 D．深度优先生成森林中
（10）下图所示带权无向图的最小生成树的权为（ C ）。
A．14 B．15 C．17 D．18
图8.32 带权无向图
8.2对于如图 8.33所示的无向图，试给出：
（1）图中每个顶点的度；
（2）该图的邻接矩阵；
（3）该图的邻接表与邻接多重表；
（4）该图的连通分量。
图8.33无向图图8.34有向图
【答】：
（1）D(V0)=2；D（V1）=2；D（V2）=3；D（V3）=3；D（V4）=2；D（V5）=2；D（V6）
=1。
（2）该图的邻接矩阵如图 8.33.1所示。
图 8.33.2 邻接表
图 8.33.1邻接矩阵
（3）该图的邻接表如图 8.30.2所示；该图的邻接多重表如图 8.30.3所示。
图 8.33.3 邻接多重表
（4）该图的两个连通分量如图 8.33.4所示。
图 8.33.4 两个连通分量
8.3对于如图 8.34所示的有向图，试给出：
（1）顶点 D的入度与出度；
（2）该图的出边表与入边表；
（3）该图的强连通
分量。
【答】：
（1）顶点 D的入度是 2；顶点 D的出度为 1。
（2）该图的出边表如图 8.34.1所示，该图的入边表如图 8.34.2所示。
图8.34.1 出边表图8.34.1 出边表
图8.34.2 入边表
（3）该图的两个强连通分量如图
8.34.3所示。
A
B
C
D
E
图8.34.3 两个强连通分量
8.4试回答下列关于图的一些问题。
（1）有
n个顶点的有向强连通图最多有多少条边？最少有多少条边？
（2）表示一个有
500个顶点，
500条边的有向图的邻接矩阵有多少个非零元素？
（3）G是一个非连通的无向图，共有
28条边，则该图至少有多少个顶点？
【答】：
（1）有
n个顶点的有向强连通图昨多有
n(n-1)条边；最少有
n-1条边。
（2）500个。
（3）9个顶点。
8.5图
8.35所示的是某个无向图的邻接表，试：
（1）画出此图；
（2）写出从顶点
A开始的
DFS遍历结果；
（3）写出从顶点
A开始的
BFS遍历结果。
【答】：
（1）图
8.35邻接表对应的无向图如图
8.35.1所示。
图
8.35 题
8.5的邻接表
图8.35.1
（2）从顶点
A开始的
DFS遍历结果是：A，B，C，F，E，G，D
（3）从顶点
A开始的
BFS遍历结果是：A，B，C，D，F，E，G
8.6证明，用
Prim算法能正确地生成一棵最小生成树。
【证明】：
78
Prim算法是按照逐边加入的方法来构造最小生成树过程的。记构造过程中生成的子图为
G’，显然
G’始终是一棵树。这是因为初始时
V(G’)={u0}，E（G’）=Ф，是一棵树。随后每一
步都是向
G’中添加一个顶点同时添加一条边，始终保持
G’中所有顶点连通。这样，当
G’有
n
个顶点时是仅有
n-1条边的连通图，所以
G’是一棵树。
Prim算法在执行过程中，始终能保证
G’=（V’，E’）是无向连通网络
G=（V，E）上某个最小代价生成树的连通图，如果该结论正
确，则随着
V(G’)顶点不断增加，当
V(G’)=V(G)时，G’=(V’,E’)就是
G=(V,E)上的最小代价生
成树。
下面证明
Prim算法的每一步都能保证
G’=(V’,E’)是无向连通网络
G=(V,E)上某个代价生成
树的子连通图。
初始时，G’仅有一个顶点
V（G’）={u0}，E（G’）=Ф，设该树为
T1，此时
G’显然是
G
的某个最小生成树的子连通图。现假设第
i步
G’=(V’,E’)中含有
i个顶点，不妨设该树为
Ti，
在
G（V，E）中存在一棵最小生成树包含着
Ti，在第
i+1步，存在
uTi，v.Ti,且(u,v)是最
∈
小两栖边，将顶点
{v}，边（
u,v）添加到树
Ti中，所得树
Ti+1是包含
V（Ti）+{v}顶点集的生
成树，且具有
i+1个顶点。根据
MST性质，此时在
G=(V,E)中必存在一棵最小生成树包含着
Ti+1
。由此可知，当
i=n时，G’(Tn)即为无向图
G含有
n个顶点的最小生成树。
当然在进行最小两栖边选择时，如果同时存在几个具有相同代价的最小两栖边，则可任选
一条，因些
Prim算法构造的最小生成树不是唯一的。但它们的最小（代价）总和是相等的。
8.7证明，用
Kruskal算法能正确地生成一棵最小生成树。
【证明】：
算法首先构造具有
n个不同顶点的
n个连通分量，然后在
E（G）中选择边(u,v)，若
u,v
顶点属于不同的两个连通分量，则把该边添加到树
T中，每添加一条边就减少一个连通分量。
当添加了共
n-1条边时，就把
n个连通分量变成一个连通分量，此时
T就是具有
n个顶点
n-1
条边的树。由于
n是有限数，
E（G）中边数也是有限的，所以算法具有有穷性。
不妨设
T的边为（u1,v1）,(u2,v2)，…，(un-1,vn-1)，按权值从小到大排列，若存在一棵
树
T’的代价总和小于
T的代价总和，则必在
T’中存在一条边（
u’,v’）∈TE’，（u’,v’）
.TE，
且(u’,v’)的代价小于(un-1,vn-1)的代价，这就说明(u’,v’)边没有选取的原因是因为
u’,v’在同一个
连通分量，添加（
u’,v’）将产生回路，说明
T’不可能是树（添加一条边没有减少一个连通分
量，这样
T’的边数将大于
n-1）。这与
T’是一棵树的假设
相矛盾。证毕。
8.8对如图
8.36所示的连通图，分别用
Prim和
Kruskal
算法构造其最小生成树。
【答】：
（1）采用
Prim算法求解最小生成树的过程如图
8.36.1
所示。
图
8.36无向连通网
（b）选取（D,F）
4
4
2
ABCDEFG（b）选取（D,F）
4
4
2
ABCDEFG
CDEFG34
4
1
2
4
（c）选取（C,F）
3
14
（e）选取（
D,E）
图
8.36.1 Prim算法求解最小生成树过程
（2）采用
Kruskal算法求解最小生成树时首先要对边进行由小到大进行排序，本题对边进行
排序的结果是：（D,F）1、（C,F）2、（A,F）3、（A,C）4、（F,G）4、（D,E）4、（D,B）4、（C,D）
5、（E,G）5、（A,D）6、（D,G）6、（A,B）7 。根据
Kruskal算法，构造最小生成树的过程如图
8.33.2所示。
（a）选取（A，F）
（d）选取（F,G）
A
B
（f）选取（D,B）
（a）选取（D，F）
（d）选取（F,G）
（b）选取（C,F）（c）选取（A,F）
4
2
ABCDFG3
4
1
E
A
B
3
DE4
CF
4
1
2
4
G
（e）选取（
D,E）（f）选取（D,B）
图
8.36.2 Kruskal算法求解最小生成树过程
8.9对于如图 8.37所示的有向网，用 Dijkstra方法求从顶点 A到图中其他顶点的最短路径，
并写出执行算法过程中距离向量 d与路径向量 p的状态变化情况。
BACEDGF28
15
3320
94318
3323
12
48
13
40
ABGCDFHIE
图 8.37有向网 图8.38 题8.10的AOV网
【答】：对于如图 8.37所示的有向网， Dijkstra方法求从顶点 A到图中其它顶点的最短径时，
距离向量与路径向量的状态变化如下表示：
循环集合
S v
距离向量
d 路径向量
p
0 1 2 3 4 5 6 0 1 2 3 4 5 6
初始化
{A } -0 48 ∞ 15 28 ∞
40 -1 0 -1 0 0 -1 0
1 { AD} 3 0 48 ∞ 15 28 48 38 -1 0 -1 0 0 3 3
2 {ADE } 4 0 48 61 15 28 48 38 -1 0 4 0 0 3 3
3 { ADG} 6 0 48 61 15 28 48 38 -1 0 4 0 0 3 3
4 {ADGB } 1 0 48 60 15 28 48 38 -1 0 1 0 0 3 3
5 {ADGBF} 5 0 48 57 15 28 48 38 -1 0 5 0 0 3 3
6 {ADGBFC } 2 0 48 57 15 28 48 38 -1 0 5 0 0 3 3
从表中可以看出源点 A到其它各顶点的最短距离及路径为：
A→B：48 路径：A→B
A→C：57 路径：A→D→F→C
A→D：15 路径：A→D
A→E：28 路径：A→E
A→F：48 路径：A→D→F
A→G：38 路径：A→D→G
8.10试写出如图 8.38所示的 AOV网的 4个不同的拓扑序列。
【答】：图 8.38所示的 AOV网的 4个不同的拓扑序列为：
（1）ABDCEFGIH
（2）ABDECFGIH
（3）DABCEFGIH
（4）DAECBFGIH
8.11计算如图 8.39所示的 AOE网中各顶点所表示的事件的发生时间 ve(j)，vl(j)，各边所表
示的活动的开始时间 e(i)，l(i)，并找出其关键路径。
【答】：为描述方便，将 AOE网中的所有边事件记为 a0-a7，如图 8.39所示。按照关键路径算
法，求得各顶事件的最早与最晚开始时间如下表所示。
v0v1v2v3v5v46
4
7
3
8
20
9
10
a0
a1
a2 a5
a3
a4
a6
a7
图 8.39 题 8.10的 AOE网
顶点 ve vl活动
e l l-e关键活动
v0 0 0 a0 0 0 0 √
v1 6 6 a1 0 1 1
v2 4 5 a2 6 6 0 √
v3 13 13 a3 4 5 1
v4 22 22 a4 4 5 1
v5 25 25 a5 13 13 0 √
a6 13 15 2
a7 22 22 0 √
可见，该 AOE网的关键路径是 a0,a2,a5,a7。（注：图中箭头指示求解的顺序）
8.12无向图采用邻接表作为存储结构，试写出以下算法
（1）求一个顶点的度；
（2）往图中插入一个顶点；
（3）往图中插入一条边；
（4）删去图中某顶点；
（5）删去图中某条边。
【答】：本题的参考解答基于以下的存储结构：
#define m 20 /*预定义图的最大顶点数 */
typedef char datatype; /*顶点信息数据类型 */
typedef struct node{ /*边表结点*/
int adjvex; /*邻接点*/
struct node *next;
}edgenode;
typedef struct vnode{ /*头结点类型*/
datatype vertex; /*顶点信息*/
edgenode *firstedge; /*邻接链表头指针 */
}vertexnode;
typedef struct{ /*邻接表类型*/
vertexnode adjlist [m]; /*存放头结点的顺序表
*/
int n,e; /*图的顶点数与边数
*/
}adjgraph;
（1）求一个顶点的度；
/*求无向图
g的第
i个顶点的度
*/
int d(adjgraph g ,int i)
{int k=0;
edgenode *p;
p=g.adjlist[i].firstedge;
while (p)
{k++;
p=p->next;
}
return k;
}
（2）往图中插入一个顶点；
void insertvex(adjgraph *g,datatype x)
{ int i=0,flag=0;
/*查找待插入的结点是否存在
*/
while (!flag&&i
{if (g->adjlist[i].vertex==x) flag=1;
i++;
}
if (flag) {
printf("结点已存在
!");
getch();
exit(0);
}
if (g->n>m) { printf("邻接表已满！");
exit(0);
}
g->adjlist[g->n].vertex=x;
g->adjlist[g->n].firstedge=NULL;
g->n++;
}
（3）往图中插入一条边；
/*在无向图
g中插入无向边（
i,j）*/
void insertedge(adjgraph *g,int i,int j)
{ edgenode *p,*s;
int flag=0;
if (i
{ p=g->adjlist[i].firstedge;
while (!flag&&p)
{if (p->adjvex==j) flag=1;
p=p->next;
}
if (flag) {printf("边已存在!");
getch();
exit(0);
}
/*插入无向边
(i,j)*/
s=(edgenode *)malloc(sizeof(edgenode));
s->adjvex=j; /*邻接点序号为
j*/
s->next=g->adjlist[i].firstedge;
g->adjlist[i].firstedge=s; /*将新结点*s插入顶点
vi的边表头部*/
s=(edgenode *)malloc(sizeof(edgenode));
s->adjvex=i; /*邻接点序号为
i*/
s->next=g->adjlist[j].firstedge;
g->adjlist[j].firstedge=s; /*将新结点*s插入顶点
vj的边表头部*/
}
else
printf("插入边不合法
!");
}
（4）删去图中某顶点；
/*下面的函数删除无向图中顶点编号为
i的顶点。由于该顶点被删除，与这个顶点相关联
的边也应该被删除，具体做法是，通过邻接表查找与顶点
i邻接的其它所有顶点，在这些顶点
的邻接边链表中删除编号为
i的边结点，再将邻接表中最后一个顶点移动到第
i个顶点在邻接
表中的位置，相应地修改最后一个顶点在邻接表中的顶点编号为
i*/
void deletevex(adjgraph *g,int i)
{ int k;
edgenode *pre,*p,*s;
if (i>=0 && i
*/
{ /*删除与原顶点
i有关的所有边*/
s=g->adjlist[i].firstedge;
while (s)
{k=s->adjvex;
pre=NULL;
p=g->adjlist[k].firstedge;
while (p)
{if (p->adjvex==i) /*结点编号是
i,应该删除*/
if (!pre) /*边链表的第一个边结点
*/
{g->adjlist[k].firstedge=p->next;
free(p);
p=g->adjlist[k].firstedge;
}
else /*不是第一个边结点*/
{pre->next=p->next;
free(p);
p=pre->next;
}
else /*结点编号不是
i*/
{pre=p;
p=p->next;
}
}
g->adjlist[i].firstedge=s->next;
free(s); /*释放顶点
i边链表上的结点
*/
s=g->adjlist[i].firstedge;
}
g->adjlist[i]=g->adjlist[g->n-1]; /*将最后一个结点换到第
i个结点的位置
*/
p=g->adjlist[i].firstedge;
/*由于第
n-1个结点的编号被改为
i，所以调整所有与这个结点关联的边信息
*/
while (p)
{ k=p->adjvex;
s=g->adjlist[k].firstedge;
while (s)
{if (s->adj
vex==g->n-1) /*将最后一个结点的编号改为
i*/
s->adjvex=i;
s=s->next;
}
p=p->next;
}
g->n--; /*结点个数减
1*/
}
else
printf("不存在指定的结点
!\n");
}
（5）删去图中某条边。
void deleteedge(adjgraph *g,int i,int j)
{ edgenode *pre,*p;
int k;
if (i>=0 && i
*/
{ pre=NULL; /*找无向边(i,j)并删除*/
p=g->adjlist[i].firstedge;
while (p && p->adjvex!=j)
{pre=p;
p=p->next;
}
if (p) /*找到了被删除边结点
*/
{ if (!pre) /*是第一个边结点
*/
g->adjlist[i].firstedge=p->next;
else
pre->next=p->next;
free(p);
pre=NULL; /*找无向边(j,i)并删除*/
p=g->adjlist[j].firstedge;
while (p&& p->adjvex!=i)
{pre=p;
p=p->next;
}
if (!pre)
g->adjlist[j].firstedge=p->next;
else
pre->next=p->next;
free(p);
g->e--; /*边的个数减
1*/
}
else {
printf("找不到指定的边
!");
getch();
exit(0);
}
}
else
{ printf("边不合法
!\n");
exit(0);
}
}
8.13设有向图采用邻接表的存储结构（出边表），试写出求图中一个顶点的入度的算法。
【答】：
/*求有向图
g中顶点
i的入度，
g的存储结构为出边表，结构定义同题
8.11*/
int id(adjgraph *g,int i)
{int j,count=0;
edgenode *p;
for (j=0;j
{p=g->adjlist[j].firstedge;
while (p)
{if (p->adjvex==i) count++;
p=p->next;
}
}
return count;
}
8.14设计一个算法，不利用拓扑排序判断有向图中是否存在环。
【答】：对于有向图进行深度优先遍历，如果从有向图上某个顶点
v出发的遍历，
dfs(v)结束之
前出现一条从顶点
u到顶点
v的回边，由于
u在生成树上是
v的子孙，则有向图中必定存在包
含顶点
v到顶点
u的环。因此判断有一个有向图中是否有环可以借助图的深度优先遍历算法。
int visited[m];
void dfs(adjgraph g,int i)
{ edgenode *p;
visited[i]=1;
p=g.adjlist[i].firstedge;
while (p)
{ if (!visited[p->adjvex])
dfs(g,p->adjvex);
else /*深度优先遍历到已访问的结点，出现环
*/
{
printf(" found a circle!");
getch();
exit(0);
}
p=p->next;
}
}
void findcircle(adjgraph g)
{ int i;
for (i=0;i
*/
for (i=0;i
dfs(g,i);
}
8.15编写一个非递归深度优先遍历图的函数。
【答】：图的深度优先遍历类似于二叉树的前序遍历，非递归实现时可以用一个栈保存已访问
过的结点，这些结点的邻接点可能还没有全部访问完成，遍历过程中可能需要回溯。
参考程序如下：
#define MAXVEX 100 /*定义栈的最大容量
*/
int visited[m];
void dfs(adjgraph g,int i)
{ /*以
vi为出发点对邻接表表
示的图
g进行深度优先遍历
*/
edgenode *p;
edgenode * stack[MAXVEX]; /*栈用来保存回溯点
*/
int top=-1;
printf("visit vertex: %c ",g.adjlist[i].vertex); /*访问顶点
i*/
visited[i]=1;
p=g.adjlist[i].firstedge;
while (top>-1 || p) /*当栈不空或
p不空时
*/
{ if (p) /*优先处理
p不空的情况*/
if (visited[p->adjvex])
p=p->next;
else
{printf("%c ",g.adjlist[p->adjvex].vertex);
visited[p->adjvex]=1;
stack[++top]=p;
p=g.adjlist[p->adjvex].firstedge;
}
else /*从栈中进行回溯
*/
if (top>-1)
{p=stack[top--];
p=p->next;
}
}
}
void dfstraverse(adjgraph g)
{ int i;
for (i=0;i
*/
for (i=0;i
*/
dfs(g,i);
}
8.16编写两个函数分别计算
AOE网中所有活动的最早开始时间与最晚允许开始时间。
【答】：为了记录
AOE网中所有活动的最早开始时间与最晚允许开始时间，定义边结点结构
edge如下，其中
vi,vj存放边的起点与终点，e存放该边表示的活动的最早开始时间，l存放该
边表示的活动的最晚允许开始时间。
typedef struct
{ int vi,vj;
e,l;
} edge; /*定义边结构类型，存放每个活动的最早开始时间与最晚允许开始时间
*/
若活动
ak的尾事件是
vi，头事件是
vj，则
e(k)就是
vi的最早发生时间，
l(k)是
vj所允许的
最晚开始时间减去活动
ak的持续的时间。求解
AOE网络事件的最早发生时间与最晚允许发生
时间的算法参见教材算法
8.10。
/*求
AOE网中各活动的最早开始时间
*/
void e(aoegraph *gout,int ve[],edge active[])
{int i,k=0;
edgenode* p;
for (i=0;i
*/
{ p=gout->adjlist[i].firstedge;
while (p)
{ active[k].vi=i; /*边的起点*/
active[k].vj=p->adjvex; /*边的终点*/
active[k].e=ve[i];
k++;
p=p->next;
}
}
}
/*求
AOE网中各活动的最晚允许开始时间
*/
void l(aoegraph *gout,int vl[],edge active[])
{int i,k=0;
edgenode *p;
for (i=0;i
{ p=gout->adjlist[i].firstedge;
while (p)
{active[k].l=vl[p->adjvex]-p->len;
p=p->next;
k++;
}
}
}