发布时间 : 星期六 文章数据结构第七章课后习题答案更新完毕开始阅读f0aea16eb84ae45c3b358cbf
数据结构
{typedef struct queuetype{int qa; int qe; int item[MAXN]; }QTYPE; int v,w;L_NODE *t; QTYPE queue; printf(\visit[u]=1; queue.qa=0; queue.qe=0;
queue.item[0]=u;
while(queue.qa<=queue.qe) {v=queue.item[queue.qa++]; t=head[v]; while(t!=NULL) {w=t->ver;
if(visit[w]==0) {printf(\ visit[w]=1;
queue.item[++queue.qe]=w; }
t=t->link; } } }
测试报告： void main()
{L_NODE *head[MAXN]; int visit[MAXN],n,m,u; E_NODE e[12];
e[0].ver1=1;e[0].ver2=3; e[1].ver1=1;e[1].ver2=4; e[2].ver1=1;e[2].ver2=2; e[3].ver1=2;e[3].ver2=4; e[4].ver1=2;e[4].ver2=5; e[5].ver1=3;e[5].ver2=6; e[6].ver1=3;e[6].ver2=4; e[7].ver1=4;e[7].ver2=6; e[8].ver1=4;e[8].ver2=7; e[9].ver1=4;e[9].ver2=5; e[10].ver1=5;e[10].ver2=7; e[11].ver1=6;e[11].ver2=7; creat_adj_list(head,7,e,12);
5
数据结构
init(visit,7); bfs(1,head,visit); printf(\}
输出结果：1 3 4 2 6 7 5
7_3
对于图题7.3的有向图，给出：
（1） 表示该图的邻接矩阵。 （2） 表示该图的邻接表。
（3） 图中每个顶点的入度和出度。
解：（1） 邻接矩阵如下：
0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 (2) 邻接表如下： 1 2 4 ^ 2 5 ^ 3 1 ^ 4 5 6 ^ 5 7 ^ 3 ^
6
6 ^ 1 2 3 4 5 6 7 图题7.3 数据结构
6 7 （4） 设各顶点入度和出度分别为ri,ci:
r1=1,c1=2 r2=1,c2=1 r3=1,c3=1 r4=1,c4=2 r5=2,c5=1 r6=2,c6=1 r7=1,c7=1
7_4
对于图题7.3的有向图，给出：
（1） 从顶点1出发，按深度优先搜索法遍历图时的所得的顶点序列。 （2） 从顶点1出发，按广度优先搜索法遍历图时的所得的定点序列。 解：（1） 1－2－5－7－6－3－4 （2） 1－2－4－5－6－7－3
7_5
对于图题7.1的无向图，试问它是（1）连通图吗？（2）完全图吗？
1 2
3 4 5 6 7
（1） 该图是连通图。判断无向图是否为连通图，即判断该图中是否
每对顶点之间都有路径。
（2） 该图不是完全图。判断无向图是否为完全图，即判断图中是否
每对顶点之间都有边。
7_6
对于图题 7.3的有向图，试问它是（1）弱连通图吗？（2）强连通图吗？
1 2
7
数据结构
3 4 5
6 7
(1) 该图是弱连通图。判断有向图是否为弱连通图，即需判断图中是否
每对顶点v和w之间有一个由不同顶点组成的顶点序列（v0,v1,……vk），其中v0=v，vk=w，且（vi，vi+1）或（vi+1，vi）属于图的边集。
(2) 该图是强连通图。判断有向图是否为强连通图，即需判断图中是否
每对顶点之间有一条路径。
7_7
图题7-7是有向图，试问其中哪个图是 （1） 弱连通的？ （2） 强连通的？
1 2
3 4
1 2 3 4
(a) (b)
[解]（1）(b) 图是弱连通的。 （2）( a) 图是强连通的。
7_8
具有N个顶点的连通无向图至少有几条边？
[解]具有N个顶点的连通无向图至少应有N—1条边。
7_9
具有N个顶点的强连通有向图至少有几条边？ 2N条边。
7_10
分别写出用深度和广度优先搜索法遍历具有六个顶点的完全无向图的顶点序列。（假设都以顶点1出发）。
深度优先：1，2，3，4，5，6 广度优先：1，2，3，4，5，6
8