算法与数据结构答案第7章图文档格式.docx
《算法与数据结构答案第7章图文档格式.docx》由会员分享，可在线阅读，更多相关《算法与数据结构答案第7章图文档格式.docx（26页珍藏版）》请在冰点文库上搜索。
3，6>
3，7>
4，7>
4，8>
5，7>
6，7>
7，8>
}；
若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照顶点序号从小到大的次序链接的，则按教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列。
【解答】1-3-6-0-2-5-4-7-8
7.15一带权无向图的邻接矩阵如下图，试画出它的一棵最小生成树。
习题7.15的图
习题7.16的图
【解答】设顶点集合为{1，2，3，4，5，6}，
由下边的逻辑图可以看出，在{1，2，3}和{4，5，6}回路中，
各任选两条边，加上（2，4），则可构成9棵不同的最小生成树。
6
7.16如图所示是一带权有向图的邻接表法存储表示。
其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。
试求：
（1）．该带权有向图的图形；
（2）．从顶点V1为起点的广度优先遍历的顶点序列及对应的生成树；
（3）．以顶点V1为起点的深度优先遍历生成树；
（4）．由顶点V1到顶点V3的最短路径。
33
36
25
18
10
29
38
30
42
【解答】
（1）
（2）V1,V2,V4,V6,V3,V5
（3）
顶点集合V（G）={V1,V2,V3,V4,V5,V6}
边的集合E（G）={<
V1,V2>
<
V2,V3>
V1,V4>
V4,V5>
V5,V6>
}
（4）
V1到V3最短路径为67:
（V1—V4—V3）
迭代
集合S
选择
顶点
D[]
D[2]D[3]D[4]D[5]D[6]
初值
{v1}
33∞29∞25
{v1,v6}
v6
{v1,v6,v4}
v4
33672971
{v1,v6,v4,v2}
v2
336771
{v1,v6,v4,v2,v3}
v3
6771
{v1,v6,v4,v2,v3,v5}
v
71
7.17已知一有向网的邻接矩阵如下，如需在其中一个顶点建立娱乐中心，要求该顶点距其它各顶点的最长往返路程最短，相同条件下总的往返路程越短越好，问娱乐中心应选址何处？
给出解题过程。
习题7.18的图
习题7.17的图
【解答】下面用FLOYD算法求出任意两顶点的最短路径（如图A（6）所示）。
题目要求娱乐中心“距其它各结点的最长往返路程最短”，结点V1，V3，V5和V6最长往返路径最短都是9。
按着“相同条件下总的往返路径越短越好”，选顶点V5，总的往返路径是34。
A（0）=A
（1）=A
（2）=A（3）=A（4）=A（5）=A（6）=
7.18求出图中顶点1到其余各顶点的最短路径。
【解答】本表中DIST中各列最下方的数字是顶点1到顶点的最短通路。
所选顶点
S（已确定最短路径
的顶点集合）
T（尚未确定最短
路径的顶点集合）
DIST
[2]
[3]
[4]
[5]
[6]
[7]
[8]
初态
{1}
{2,3,4,5,6,7,8}
∞
60
5
{1,5}
{2,3,4,6,7,8}
17
{1,5,6}
{2,3,4,7,8}
20
{1,5,6,2}
{3,4,7,8}
7
{1,5,6,2,7}
{3,4,8}
31
28
35
{1,5,6,2,7,4}
{3,8}
{1,5,6,2,7,4,3}
{5,8}
8
{1,5,6,2,7,4,3,8}
{8}
顶点1到其它顶点的最短路径依次是20，31，28，10，17，25，35。
按Dijkstra算法所选顶点依次是5，6，2，7，4，3，8。
7.19对图示的AOE网络，计算各活动弧的e（ai）和l（ai）的函数值，各事件（顶点）的ve（vi）和vl（vi）的函数值，列出各条关键路径。
α
A
B
C
D
E
F
G
H
W
Ve（i）
24
13
39
22
52
Vl（i）
活动
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
e（i）
l（i）
34
40
，长52。
关键路径是：
活动与顶点的对照表：
a1<
α,A>
a2<
α,B>
a3<
α,C>
a4<
α,D>
a5<
A,E>
a6<
B,E>
a7<
B,W>
a8<
C,G>
a9<
C,F>
a10<
D,F>
a11<
E,G>
a12<
F,E>
a13<
F,W>
a14<
F,H>
a15<
G,W>
a16<
H,G>
a17<
H,W>
7.20
利用弗洛伊德算法，写出如图所示相应的带权邻接矩阵的变化。
9
【解答】A0=A1=A2=A3=A4=
二、算法设计题
7.21设无向图G有n个顶点，m条边。
试编写用邻接表存储该图的算法。
voidCreatGraph（AdjListg）∥建立有n个顶点和m条边的无向图的邻接表存储结构
{intn,m;
scanf（"
%d%d"
&
n,&
m）;
for（i=0,i<
n;
i++）∥输入顶点信息,建立顶点向量
{scanf（&
g[i].vertex）;
g[i].firstarc=null;
for（k=0;
k<
m;
k++）∥输入边信息
{scanf（&
v1,&
v2）;
∥输入两个顶点
i=GraphLocateVertex（g,v1）;
j=GraphLocateVertex（g,v2）;
∥顶点定位
p=（ArcNode*）malloc（sizeof（ArcNode））;
∥申请边结点
p->
adjvex=j;
p->
next=g[i].firstarc;
g[i].firstarc=p;
∥将边结点链入
p=（ArcNode*）malloc（sizeof（ArcNode））;
adjvex=i;
next=g[j].firstarc;
g[j].frstarc=p;
}∥for
}∥算法CreatGraph结束
7.22已知有向图有n个顶点，请编写算法，根据用户输入的偶对建立该有向图的邻接表。
voidCreatAdjList（AdjListg）∥建立有向图的邻接表存储结构
{intn;
scanf（"
%d"
n）;
for（i=0;
i<
j++）
}∥输入顶点信息,下标从0开始
scanf（&
v1,.&
while（v1&
&
v2）∥题目要求两顶点之一为0表示结束
{i=GraphLocateVertex（g,v1）;
p=（ArcNode*）malloc（sizeof（ArcNode））;
}∥while
7.23给出以十字链表作存储结构，建立图的算法，输入（i，j，v）其中i，j为顶点号，v为权值。
voidCreatOrthList（OrthListg）∥建立有向图的十字链表存储结构
{inti,j,v;
∥假定权值为整型
i++）∥建立顶点向量
{scanf（&
g[i].firstin=null;
g[i].firstout=null;
scanf（"
%d%d%d"
i,&
j,&
v）;
while（i&
j&
v）∥当输入i,j,v之一为0时,结束算法运行
{p=（OrArcNode*）malloc（sizeof（OrArcNode））;
∥申请结点
p->
headvex=j;
tailvex=i;
weight=v;
∥弧结点中权值域
headlink=g[j].firstin;
g[j].firstin=p;
tailink=g[i].firstout;
g[i].firstout=p;
}∥while
}∥算法结束
[算法讨论]本题已假定输入的i和j是顶点号,否则,顶点的信息要输入,且用顶点定位函数求出顶点在顶点向量中的下标。
图建立时，若已知边数（如上面1和2题），可以用for循环；
若不知边数，可用while循环（如本题），规定输入特殊数（如本题的零值）时结束运行。
本题中数值设为整型，否则应以和数值类型相容的方式输入。
7.24设有向图G有n个点（用1，2，…，n表示），e条边，写一算法根据G的邻接表生成G的反向邻接表，要求算法时间复杂性为O（n+e）。
voidInvertAdjList（AdjListgin,gout）∥将有向图的出度邻接表改为按入度建立的逆邻接表
{for（i=0;
i++）∥设有向图有n个顶点，建逆邻接表的顶点向量。
{gin[i].vertex=gout[i].vertex;
gin[i].firstarc=null;
}
for（i=0;
i++）∥邻接表转为逆邻接表。
{p=gout[i].firstarc;
∥取指向邻接点的指针
while（p!
=null）
{j=p->
adjvex;
s=（ArcNode*）malloc（sizeof（ArcNode））;
∥申请结点空间
s->
next=gin[j].firstarc;
gin[j].firstarc=s;
p=p->
next;
∥下一个邻接点。
7.25写出从图的邻接表表示转换成邻接矩阵表示的算法。
voidAdjListToAdjMatrix（AdjListgl,AdjMatrixgm）
∥将图的邻接表表示转换为邻接矩阵表示
{for（i=0;
i++）∥设图有n个顶点，邻接矩阵初始化
for（j=0;
j<
j++）gm[i][j]=0;
i++）∥取第一个邻接点，填邻接矩阵元素值，并求下一个邻接点
{p=gl[i].firstarc;
=null）
{gm[i][p->
adjvex]=1;
p=p->
}∥for
7.26试写出把图的邻接矩阵表示转换为邻接表表示的算法。
voidAdjMatrixToAdjList（AdjMatrixgm,AdjListgl）
∥将图的邻接矩阵表示转换为邻接表表示
i++）∥邻接表表头向量初始化。
gl[i].vertex）;
gl[i].firstarc=null;
i++）
if（gm[i][j]==1）
{p=（ArcNode*）malloc（sizeof（ArcNode））;
∥顶点I的邻接点是j
next=gl[i].firstarc;
gl[i].firstarc=p;
∥链入顶点i的邻接点链表中
}∥if
}∥end
7.27试编写建立有n个顶点，m条边且以邻接多重表为存储结构表示的无向图的算法。
voidCreatMGraph（AdjMulistg）
∥建立有n个顶点e条边的无向图的邻接多重表的存储结构
{intn,e;
e）;
for（i=0,i<
{scanf（&
g[i].firstedge=null;
for（k=0;
e;
k++）∥建立边结点
i=GraphLocateVertex（g,v1）;
j=GraphLocateVertex（g,v2）;
p=（ENode*）malloc（sizeof（ENode））;
ivex=i;
jvex=j;
ilink=g[i].firstedge;
jlink=g[j].firstedge;
g[i].firstedge=p;
g[j].firstedge=p;
7.28已知某有向图（n个结点）的邻接表，求该图各结点的入度数。
【题目分析】在有向图的邻接表存储结构中求顶点的入度，需要遍历整个邻接表。
voidIndegree（AdjListg）∥求以邻接表为存储结构的n个顶点有向图的各顶点入度
{num=0;
∥入度初始为0
for（j=0;
j++）∥遍历整个邻接表，求一个顶点的入度
if（i!
=j）
{p=g[j].firstarc;
while（p）
{if（p->
adjvex==i）num++;
printf（“顶点%d的入度为：
%d\n”,g[i].vexdata,num）;
∥设顶点数据为整型
}
7.29已知无向图G=（V，E），给出求图G的连通分量个数的算法。
【题目分析】使用图的遍历可以求出图的连通分量。
进入dfs或bfs一次，就可以访问到图的一个连通分量的所有顶点。
voiddfs（v）
{visited[v]=1;
printf（“%3d”,v）;
∥输出连通分量的顶点。
p=g[v].firstarc;
while（p!
{if（visited[p->
adjvex==0]）dfs（p->
adjvex）;
}∥while
}∥dfs
voidCount（）
∥求图中连通分量的个数
{intk=0;
staticAdjListg;
∥设无向图g有n个结点
i++）
if（visited[i]==0）{printf（"
\n第%d个连通分量:
\n"
++k）;
dfs（i）;
}∥if
}∥Count
【算法讨论】算法中visited[]数组是全程变量，每个连通分量的顶点集按遍历顺序输出。
这里设顶点信息就是顶点编号，否则应取其g[i].vertex分量输出。
7.30已知无向图采用邻接表存储方式，试写出删除边（i，j）的算法。
voidDeletEdge（AdjListg,inti,j）
∥在用邻接表方式存储的无向图g中，删除边（i,j）
{p=g[i].firstarc;
pre=null;
∥删顶点i的边结点（i,j）,pre是前驱指针
while（p）
if（p->
adjvex==j）
{if（pre==null）g[i].firstarc=p->
elsepre->
next=p->
free（p）;
}∥释放空间
else{pre=p;
}∥沿链表继续查找
p=g[j].firstarc;
∥删顶点j的边结点（j,i）
adjvex==i）
{if（pre==null）g[j].firstarc=p->
elsepre->
}∥DeletEdge
【算法讨论】算法中假定给的i，j均存在，否则应检查其合法性。
若未给顶点编号，而给出顶点信息，则先用顶点定位函数求出其在邻接表顶点向量中的下标i和j。
7.31假设有向图以邻接表存储，试编写算法删除弧<
Vi，Vj>
的算法。
voidDeleteArc（AdjListg,vertypevi,vj）
∥删除以邻接表存储的有向图g的一条弧<
vi,vj>
，假定顶点vi和vj存在
{i=GraphLocateVertex（g,vi）;
j=GraphLocateVertex（g,vj）;
∥顶点定位
p=g[i].firstarc;
{if（pre==null）g[i].firstarc=p->
free（p）;
}∥释放结点空间
}∥结束
7.32
设计一个算法利用遍历图的方法判别一个有向图G中是否存在从顶点Vi到Vj的长度为k的简单路径，假设有向图采用邻接表存储结构。
【题目分析】本题利用深度优先递归的搜索方法判断有向图G的顶点i到j是否存在长度为k的简单路径，先找到i的第一个邻接点m，再从m出发递归的求是否存在m到j的长度为k-1的简单路径。
intexistpathlen（AlGraphG,inti,intj,intk）
{//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径
if（i==j&
k==0）return1;
//找到了一条路径,且长度符合要求
elseif（k>
0）
{visited[i]=1;
for（p=G.vertices[i].firstarc;
p;
next）
{m=p->
if（!
visited[m]）
if（existpathlen（G,m,j,k-1））return1;
//剩余路径长度减一
visited[i]=0;
//本题允许曾经被访问过的结点出现在另一条路径中
return0;
//没找到
7.33
设有向图G采用邻接矩阵存储，编写算法求出G中顶点i到顶点j的不含回路的、长度为k的路径数。
intGetPathNum（AdjMatrixGA,inti,intj,intk,intn）
{//求邻接矩阵方式存储的有向图G的顶点i到j之间长度为k的简单路径条数
//n为顶点个数
//找到了一条路径,且长度符合要求
{sum=0;
//sum表示通过本结点的路径数
visited[i]=1;
for（k=0;
k++）
{if（GA[i][k]!
=0&
!
visited[k]）
sum+=GetPathNum（GA,k,j,k-1,n）//剩余路径长度减一
visited[i]=0;
returnsum;
7.34
设计算法求出以邻接表存储的有向图G中由顶点u到v的所有的简单路径。
voidAllSPdfs（AdjL
升级会员 