第七章图 习题答案.docx
《第七章图 习题答案.docx》由会员分享，可在线阅读，更多相关《第七章图 习题答案.docx（43页珍藏版）》请在冰点文库上搜索。
第七章图习题答案
第七章图习题答案
基础知识：
7.1在图7.23所示的各无向图中：
（1）找出所有的简单环。
（2）哪些图是连通图?
对非连通图给出其连通分量。
（3）哪些图是自由树（或森林）?
答:
（1）所有的简单环：
（同一个环可以任一顶点作为起点）
（a）1231
（b）无
（c）1231、2342、12341
（d）无
（2）连通图：
（a）、（c）、（d）是连通图，
（b）不是连通图，因为从1到2没有路径。
具体连通分量为：
（3）自由树（森林）：
自由树是指没有确定根的树，无回路的连通图称为自由树：
（a）不是自由树，因为有回路。
（b）是自由森林，其两个连通分量为两棵自由树。
（c）不是自由树。
（d）是自由树。
7.2在图7.24（下图）所示的有向图中：
（1）该图是强连通的吗?
若不是，则给出其强连通分量。
（2）请给出所有的简单路径及有向环。
（3）请给出每个顶点的度，入度和出度。
（4）请给出其邻接表、邻接矩阵及逆邻接表。
答：
（1）该图是强连通的，所谓强连通是指有向图中任意顶点都存在到其他各顶点的路径。
（2）简单路径是指在一条路径上只有起点和终点可以相同的路径：
有v1v2、v2v3、v3v1、v1v4、v4v3、v1v2v3、v2v3v1、v3v1v2、v1v4v3、v4v3v1、v3v1v4、另包括所有有向环,有向环如下：
v1v2v3v1、v1v4v3v1（这两个有向环可以任一顶点作为起点和终点）
（3）每个顶点的度、入度和出度：
D（v1）=3 ID（v1）=1 OD（v1）=2
D（v2）=2 ID（v2）=1 OD（v2）=1
D（v3）=3 ID（v3）=2 OD（v3）=1
D（v4）=2 ID（v4）=1 OD（v4）=1
（4）邻接表：
（注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点的下标值-1）
vertexfirstedge next
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
0│v1│ ─→│1│ ─→│3│∧│
├─┼─┤ ├─┼─┤ └─┴─┘
1│v2│ ─→│2│∧│
├─┼─┤ ├─┼─┤
2│v3│ ─→│0│∧│
├─┼─┤ ├─┼─┤
3│v4│ ─→│2│∧│
└─┴─┘ └─┴─┘
逆邻接表：
┌─┬─┐ ┌─┬─┐
0│v1│ ─→│2│∧│
├─┼─┤ ├─┼─┤
1│v2│ ─→│0│∧│
├─┼─┤ ├─┼─┤ ┌─┬─┐
2│v3│ ─→│1│ ─→│3│∧│
├─┼─┤ ├─┼─┤ └─┴─┘
3│v4│ ─→│0│∧│
└─┴─┘ └─┴─┘
邻接矩阵：
0101
0010
1000
0010
7.3假设图的顶点是A,B...，请根据下述的邻接矩阵画出相应的无向图或有向图。
┌ ┓
┌ ┓ |01100|
|0111| |00010|
|1011| |00010|
|1101| |10001|
|1110| |01010|
┕ ┙┕ ┙
（a） （b）
答:
7.4假设一棵完全二叉树包括A,B,C...等七个结点，写出其邻接表和邻接矩阵。
解：
邻接表如下：
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
0│A│ ─→│1│ ─→│2│∧│
├─┼─┤ ├─┼─┤ ├─┼─┤ ┌─┬─┐
1│B│ ─→│0│ ─→│3│ ─→│4│∧│
├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤
2│C│ ─→│0│ ─→│5│ ─→│6│∧│
├─┼─┤ ├─┼─┤ └─┴─┘ └─┴─┘
3│D│ ─→│1│∧│
├─┼─┤ ├─┼─┤
4│E│ ─→│1│∧│
├─┼─┤ ├─┼─┤
5│F│ ─→│2│∧│
├─┼─┤ ├─┼─┤
6│G│ ─→│2│∧│
└─┴─┘ └─┴─┘
邻接矩阵如下：
0110000
1001100
1000011
0100000
0100000
0010000
0010000
7.5对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题?
（1）图中有多少条边?
（2）任意两个顶点i和j是否有边相连?
（3）任意一个顶点的度是多少?
答：
对于n个顶点的无向图和有向图，用邻接矩阵表示时：
（1）设m为矩阵中非零元素的个数
无向图的边数=m/2
有向图的边数=m
（2）无论是有向图还是无向图，在矩阵中第i行,第j列的元素若为非零值，则该两顶点有边相连。
（3）对于无向图，任一顶点i的度为第i行中非零元素的个数。
对于有向图，任一顶点i的入度为第i列中非零元素的个数，出度为第i行中非零元素的个数，度为入度出度之和。
当用邻接表表示时：
（1）对于无向图，图中的边数=边表中结点总数的一半。
对于有向图，图中的边数=边表中结点总数。
（2）对于无向图，任意两顶点间是否有边相连，可看其中一个顶点的邻接表，若表中的adjvex域有另一顶点位置的结点，则表示有边相连。
对于有向图，则表示有出边相连。
（3）对于无向图，任意一个顶点的度则由该顶点的边表中结点的个数来决定。
对于有向图，任意一个顶点的出度由该顶点的边表中结点的个数来决定，入度则需遍历各顶点的边表。
（用逆邻接表可容易地得到其入度。
）
7.6n个顶点的连通图至少有几条边?
强连通图呢?
答：
n个顶点的连通图至少有n-1条边，强连通图至少有2（n-1）条边。
7.7DFS和BFS遍历各采用什么样的数据结构来暂存顶点?
当要求连通图的生成树的高度最小，应采用何种遍历?
答：
DFS遍历采用栈来暂存顶点。
BFS采用队列来暂存顶点。
当要求连通图的生成树的高度最小时，应采用BFS遍历。
7.8画出以顶点v1为初始源点遍历图7.25（下图）所示的有向图所得到的DFS和BFS生成森林。
答：
7.9按顺序输入顶点对：
（1，2），（1，6），（2，6），（1，4），（6，4），（1，3），（3，4）,（6，5），（4，5），（1,5）,（3,5）,根据第7.2.2节中算法CreatALGraph画出相应的邻接表。
并写出在该邻接表上，从顶点4开始搜索所得的DFS和BFS序列，及DFS和BFS生成树。
答：
相应的邻接表如下：
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
1│1│ ─→│5│ ─→│3│ ─→│4│ ─→│6│ ─→│2│∧│
├─┼─┤ ├─┼─┤ ├─┼─┤ └─┴─┘ └─┴─┘ └─┴─┘
2│2│ ─→│6│ ─→│1│∧│
├─┼─┤ ├─┼─┤ ├─┼─┤ ┌─┬─┐
3│3│ ─→│5│ ─→│4│ ─→│1│∧│
├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤ ┌─┬─┐
4│4│ ─→│5│ ─→│3│ ─→│6│ ─→│1│∧│
├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤
5│5│ ─→│3│ ─→│1│ ─→│4│ ─→│6│∧│
├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤
6│6│ ─→│5│ ─→│4│ ─→│2│ ─→│1│∧│
└─┴─┘ └─┴─┘ └─┴─┘ └─┴─┘ └─┴─┘
根据上面的邻接表画出的图见下图:
从顶点4开始搜索所得的DFS序列是：
453162
从顶点4开始搜索所得的BFS序列是：
453612
相应的生成树见上图。
7.10什么样的图其最小生成树是唯一的?
用PRIM和Kruskal求最小生成树的时间各为多少?
它们分别适合于哪类图?
答：
当候选轻边集中的轻边数始终等于1条时，其最小生成树是唯一的。
用Prim和Kruskal求最小生成树的时间复杂度分别为O（n2）和O（elge）,前者适合于稠密图，后者适合于稀疏图.
7.11对图7.26（下图）所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。
答：
7.12对图7.27（下图）所示的有向图，试利用Dijkstra算法求出从源点1到其它各顶点的最短路径，并写出执行算法过程中扩充红点集的每次循环状态（见表7.2）.
答：
循环状态表如下：
循环 红点集 KD[1]D[2]D[3]D[4]D[5]D[6]P[1]P[2]P[3]P[4]P[5]P[6]
初始化 {1} - 0 20 15 ∞ ∞ ∞ -1 1 1 -1 -1 -1
1 {1,3} 3 0 19 15 ∞ ∞ 25 -1 3 1 -1 -1 3
2 {1,3,2} 2 0 19 15 ∞ 29 25 -1 3 1 -1 2 3
3 {1,3,2,6} 6 0 19 15 29 29 25 -1 3 1 6 2 3
4 {1,3,2,6,4} 4 0 19 15 29 29 25 -1 3 1 6 2 3
5{1,3,2,6,4,5} 5 0 19 15 29 29 25 -1 3 1 6 2 3
6 同上 - 同上 同上
从源点1到各点的路径如下所示：
1到2：
132
1到3：
13
1到4：
1364
1到5：
1325
1到6：
136
整个执行算法过程中的扩充红点集的每次循环状态见上表。
7.13试写出图7.28（下图）所示有向图的所有拓扑序列，并指出就用7.6节给出的NonPreFirstTopSort算法求得的是哪个序列，设邻接表的边表结点中的邻接点序号是递增有序的。
答：
上图中所有拓扑序列如下：
v0v1v5v2v3v6v4* v0v1v5v2v6v3v4 v0v1v5v6v2v3v4
v1v0v5v6v2v3v4 v1v0v5v2v3v6v4 v1v0v5v2v6v3v4
v1v5v0v2v3v6v4 v1v5v0v2v6v3v4 v1v5v0v6v2v3v4
v5v1v0v2v3v6v4 v5v1v0v2v6v3v4 v5v1v0v6v2v3v4
v5v0v1v2v3v6v4 v5v0v1v2v6v3v4 v5v0v1v6v2v3v4
v0v5v6v1v2v3v4 v1v5v6v0v2v3v4 v5v6v1v0v2v3v4
v5v6v0v1v2v3v4 v5v0v6v1v2v3v4 v5v1v6v0v2v3v4
用NonPreFirstTopSort算法求得的是v0v1v5v2v3v6v4也就是上面带*号的那个。
7.14什么样的DAG的拓扑序列是唯一的?
答：
确定了排序的源点，DAG图中无前趋顶点只有一个且从该点到终点只有一条路径时，它的拓扑序列才是唯一的。
7.15请以V0为源点，给出用DFS搜索图7.28（下图）得到的逆拓扑序列。
答：
逆拓扑序列是：
V4V2V1V0V1V6V5
算法设计：
7.16试在无向图的邻接矩阵和邻接链表上实现如下算法：
（1）往图中插入一个顶点
（2）往图中插入一条边
（3）删去图中某顶点
（4）删去图中某条边
解：
（一）用邻接矩阵表示
#defineMaxVertexNuml00//最大顶点数，应由用户定义
typedefcharVertexType；//顶点类型应由用户定义
typedefintEdgeType；//边上的权值类型应由用户定义
typedefstruct{
VextexTypevexs[MaxVertexNum]//顶点表
EdeTypeedges[MaxVertexNum][MaxVertexNum];
//邻接矩阵，可看作边表
intn，e；//图中当前的顶点数和边数
}MGragh；
（1）往图中插入一个顶点
voidAddVertexMGraph（MGraph*G,VertexTypex）
{//往无向图的邻接矩阵中插入顶点
if（G->n>=MaxVertexNum）
Error（"顶点数太多"）；
G->vexs[G->n]=x;//将新顶点输入顶点表
G->n++；//顶点数加1
}
（2）往图中插入一条边
voidAddedgeMGraph（MGraph*G,VertexTypex,VertexTypey）
{//往无向图的邻接矩阵中插入边（x,y）
inti,j,k;
i=-1;j=-1;
for（k=0;kn;k++）//查找X，Y的编号
{if（g->vexs[k]===x）i=k;
if（g->vexs[k]==y）j=k;
}
if（i==-1||j==-1）Error（"结点不存在"）;
else{//插入边（x,y）
g->vex[i][j]=1;
g->vex[j][i]=1;
G->e++;//边数加1
}
}
（3）删去图中某顶点
voidDeleteVertexMGraph（MGraph*G,VertexTypex）
{//无向图的邻接矩阵中删除顶点x
inti,k,j;
i=-1;
for（k=0;kn;k++）//查找X的编号
if（g->vexs[k]=x）i=k;
if（i==-1）Error（"结点不存在"）;
else{//删除顶点以及边
k=0;//求出与x结点相关联的边数k
for（j=0;jn;j++）
if（g->vexs[i][j]==0）k++;
G->e=G->e-k;//设置新的边数
for（k=i+1;kn;k++）//在邻接矩阵中删除第i行
for（j=0;jn;j++）
g->vexs[k-1][j]=g->vexs[k][j];
for（k=i+1;kn;k++）//在邻接矩阵中删除第i列
for（j=0;jn;j++）
g->vexs[j][k-1]=g->vexs[j][k];
G->n--;//总结点数-1
}
}
（4）删去图中某条边
voidDeleteedgeMGraph（MGraph*G,VertexTypex,VertexTypey）
{//无向图的邻接矩阵中删除边（x,y）
inti,j,k;
i=-1;j=-1;
for（k=0;kn;k++）//查找X，Y的编号
{if（g->vexs[k]=x）i=k;
if（g->vexs[k]=y）j=k;
}
if（i==-1||j==-1）Error（"结点不存在"）;
elseif（g->vexs[i][j]!
=1）
{//删除边（x,y）
g->vex[i][j]=0;
g->vex[j][i]=0;
G->e--;//边数加1
}
}
（二）用邻接表表示
typedefstructnode{//边表结点
intadjvex；//邻接点域
structnode*next；//链域
//若要表示边上的权，则应增加一个数据域
}EdgeNode;
typedefstructvnode{//顶点表结点
VertexTypevertex；//顶点域
EdgeNode*firstedge；//边表头指针
}VertexNode；
typedefVertexNodeAdjList[MaxVertexNum]；//AdjList是邻接表类型
typedefstruct{
AdjListadjlist；//邻接表
intn，e；图中当前顶点数和边数
}ALGraph；//对于简单的应用，无须定义此类型，可直接使用AdjList类型。
（1）往图中插入一个顶点
voidAddVertexALGraPh（ALGrahp*G,VertexTypex）
{//往无向图的邻接表表示中插入一个顶点
if（G->n>=MaxVertexNum）
Error（"顶点数太多"）；
G->adjlist[G->n].vertex=x;//将新顶点输入顶点表
G->adjlist[G->n].firstedge=NULL;//边表置为空表
G->n++；//顶点数加1
}
（2）往图中插入一条边
voidAddedgeALGraPh（ALGrahp*G,VertexTypex,VertexTypey）
{//往无向图的邻接表中插入边（x,y）
inti,j,k;
EdgeNode*s；
i=-1;j=-1;
for（k=0;kn;k++）//查找X，Y的编号
{if（G->adjlist[k].vertex==x）i=k;
if（G->adjlist[k].vertex==y）j=k;
}
if（i==-1||j==-1）Error（"结点不存在"）;
else{
s=G->adjlist[i].firstedge;
while（（s）&&（s->adjvex!
=j）//查看邻接表中有无（x,y）
s=s->next;
if（!
s）//当邻接表中无边（x,y）,插入边（x,y）
{
s=（EdgeNode*）malloc（sizeof（EdgeNode））；//生成边表结点
s->adjvex=j;//邻接点序号为j
s->next=G->adjlist[i].firstedge；
G->adjlist[i].firstedge=s；//将新结点*s插入顶点x的边表头部
s=（EdgeNode*）malloc（sizeof（EdgeNode））；
s->adjvex=i;//邻接点序号为i
s->next=G->adjlist[j].firstedge；
G->adjlist[j].firstedge=s；//将新结点*s插入顶点x的边表头部
G->e++;//边数加1
}
}
}
（3）删去图中某顶点
voidDeleteVertexALGraPh（ALGrahp*G,VertexTypex）
{//无向图的邻接表中删除顶点x
inti,k,j;
EdgeNode*s,*p,*q；
i=-1;
for（k=0;kn;k++）//查找X的编号
if（G->adjlist[k].vertex==x）i=k;
if（i==-1）Error（"结点不存在"）;
else{//删除与x相关联的边
s=G->adjlist[i].firstedge;
while（s）
{p=G->adjlist[s->adjvex].firstedge;//删除与i相关联的其他结点边表中表结点
if（p）&&（p->adjvex==i）//是第一个边表结点，修改头指针
{G->adjlist[s->adjvex].firstedge=p->next;
free（p）;
}
else//不是第一个边表结点，查找并删除
{while（p）&&（p->next）&&（p->next->adjvex==i）
升级会员 