问南广播电视大季现教中心 第七章图课后习题答案 1、单项这择题 (1)B书124页 (2)A书125 (3)B 书124页 (4)B 强连通图的性质决定的 (5)D 无向图的邻接表，月一条边在邻接表中出现了两次 (6)C (7)D n个项点的最小生成树是n-1条边，如果有n条边，一定有一个回路了 (8)B 书138页 (9)A (10)C 2、运算思 (1) 0 6 ② (aJ (b) ①采用智接矩阵表示 (a)深度优先搜索序列：0,1,28,34,5,6,7,9 广度优先搜索序列：0,1,4,2.7.3,8.65,9 (b) ②采用忽接表表示 (a》 (b)深度优先被索序列：0.4,7,5,8.3,6,1,2 "度优先变索序列：0.4.3,1.7.5,6,28 (2)首先要建立该图的边集数组。 000112233445 156263646566 6128124591020131615 遗权值最小的边。要求无问路。边依次为： (1,6)4,(2,3)5,(0,1)6,(2.6》9.(3,4)10,(0.5)12 权值为：46 图如下： 第1顶共3项 版权所有河南电大现教中心植额，都箱dpm恒cm
河南广播电视大学现教中心 第1页 共3页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 第七章 图 课后习题答案 1、 单项选择题 （1） B 书 124 页 （2） A 书 125 页 （3） B 书 124 页 （4） B 强连通图的性质决定的 （5） D 无向图的邻接表，同一条边在邻接表中出现了两次 （6） C （7） D n 个顶点的最小生成树是 n-1 条边，如果有 n 条边，一定有一个回路了 （8） B 书 138 页 （9） A （10） C 2、 运算题 （1） ①采用邻接矩阵表示 （a）深度优先搜索序列：0,1,2,8,3,4,5,6,7,9 广度优先搜索序列：0,1,4,2,7,3,8,6,5,9 （b） ②采用邻接表表示 （a） （b）深度优先搜索序列：0,4,7,5,8,3,6,1,2 广度优先搜索序列：0,4,3,1,7,5,6,2,8 （2）首先要建立该图的边集数组。 0 0 0 1 1 2 2 3 3 4 4 5 1 5 6 2 6 3 6 4 6 5 6 6 6 12 8 12 4 5 9 10 20 13 16 15 选权值最小的边，要求无回路，边依次为： （1，6）4，（2，3）5，（0，1）6，（2，6）9，（3，4）10，（0，5）12 权值为：46 图如下：
河南厂播电现大学现数中心 0 一12 说明：最短路轻长度不要求会做，了解即可 (3)1402365879 3、算法分析题 (1)按照图的深度优先搜常考历的方法，输出得到该图的生成树中的各条边。 (2)顺序输出邻接：库GA中的值。 4、算法设计题 (1)参考答案 根据有向图的客援矩阵求出序号为mb的顶点的度数 int degree(Graph TpA&ga.int numb) intij.d=0 求出质点umb的出度 forj-0:jcga.vexnum.j++) if(ga aresnumb0&&ga aresnumbll-MAXINT) d+4: 求出质点umb的入度 tort=0:ega.enum:++月 if(ga ares]Inumb]-o&s ga ares Inumb]l-MAXINT) d+材 W思国魔点umb的度 retum d; (2)参考答案： 根据无向图的忽报表求出序号为U的的膜点的度数 int degree3(GraphTpL&gl int numb) int d=0 AreNodeTp*p-gl.adjlistnumb]: while(p-NULL) d++. pp->nextsre. 1 reurn d: (3)参考答案： 第2风共3项 版权所有河南电大现教中心范额，邮箱5@m恒cm
河南广播电视大学现教中心 第2页 共3页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 0 5 1 6 2 3 4 6 12 4 9 5 10 说明：最短路径长度不要求会做，了解即可 （3）1 4 0 2 3 6 5 8 7 9 3、 算法分析题 （1）按照图的深度优先搜索遍历的方法，输出得到该图的生成树中的各条边。 （2）顺序输出邻接矩阵 GA 中的值。 4、 算法设计题 （1）参考答案： //根据有向图的邻接矩阵求出序号为 numb 的顶点的度数 int degree(GraphTpA& ga, int numb) { int i,j,d=0; //求出顶点 numb 的出度 for(j=0; jnextare; } return d; } （3）参考答案：
河南广播电视大学现黄中心 球出一个图中所有顶点的量大高度物 int maxOutDegree(GraphTpA&ga) r嘴im=0 求出所有顶点的最大出度值 for(0;iega.vexnum;H++) 将境南的出度置为0 int k=0: 院计出项点的出度 o0-0j小ga8 xnum.j++) (ga ares=08&ga.ares-MAXINT) ++ W若k的值大于m8氧则用它修改m8x的值 if(omax)maxk 返回所有顶点的最大出度的 retum max 第3项共3页 版权所有河南电大规教中心范隔，配箱@up恤m
河南广播电视大学现教中心 第3页 共3页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn //求出一个图中所有顶点的最大出度值 int maxOutDegree(GraphTpA& ga) { int i,j,max=0; //求出所有顶点的最大出度值 for(i=0; imax) max=k; } //返回所有顶点的最大出度值 return max; }