《算法与数据结构 C语言版 第二版 (陈守孔 孟佳娜 武秀川 著) 机械工业出版社课后答案 第7章 图》由会员分享，可在线阅读，更多相关《算法与数据结构 C语言版 第二版 (陈守孔 孟佳娜 武秀川 著) 机械工业出版社课后答案 第7章 图（19页珍藏版）》请在金锄头文库上搜索。
1、第 7 章 图一、基础知识题 7.1设无向图的顶点个数为n，则该图最多有多少条边？【解答】n(n-1)/27.2一个n个顶点的连通无向图，其边的个数至少为多少？【解答】n-1 7.3要连通具有n个顶点的有向图，至少需要多少条弧?【解答】n7.4 n个顶点的完全有向图含有弧的数目是多少?【解答】n(n-1)7.5一个有n个顶点的无向图，最少有多少个连通分量，最多有多少个连通分量。【解答】1, n7.6图的BFS生成树的树高要小于等于同图DFS生成树的树高，对吗？【解答】对7.7无向图G=(V,E)，其中：V=a,b,c,d,e,f，E=(a,b),(a,e),(a,c),(b,e),(c,f),
2、(f,d),(e,d)，写出对该图从顶点a出发进行深度优先遍历可能得到的全部顶点序列。【解答】abedfc, acfdeb, aebdfc, aedfcb7.8 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度是多少？【解答】O(n+e)7.9若一个具有n个顶点，e条边的无向图是一个森林，则该森林中必有多少棵树？【解答】n-e7.10 n个顶点的无向图的邻接矩阵至少有多少非零元素？【解答】07.11证明:具有n个顶点和多于n-1条边的无向连通图G一定不是树。【证明】具有n个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要
3、连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树。7.12证明对有向图顶点适当编号，使其邻接矩阵为下三角形且主对角线为全零的充要条件是该图是无环图。【证明】该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧，所以邻接矩阵主对角元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非零元素（Aij=1）自然是落到下三角矩阵中；命题的必要条件是要使上三角为0，则不允许出现弧头顶点编号大于弧尾顶点编号的弧，否则，就必然存在环路。（对该类有向无环图顶点编号，应按顶点出度的
4、大小进行顺序编号。）7.13设G=(V，E)以邻接表存储，如图所示，试画出从顶点1出发所得到的深度优先和广度优先生成树。 习题7.13 的图【解答】深度优先生成树12345宽度优先生成树：123457.14 已知一个图的顶点集V和边集E分别为：V=0，1，2，3，4，5，6，7；E=，；若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照顶点序号从小到大的次序链接的，则按教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列。【解答】1-3-6-0-2-5-4-7-8 7.15一带权无向图的邻接矩阵如下图 ，试画出它的一棵最小生成树。 习题7.15 的图 习题7.16 的图【解答】设顶点集合为
5、1，2，3，4，5，6， 由下边的逻辑图可以看出，在1，2，3和4，5，6回路中，各任选两条边，加上（2，4），则可构成9棵不同的最小生成树。121111131234567.16如图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：（1）该带权有向图的图形；（2）从顶点V1为起点的广度优先遍历的顶点序列及对应的生成树；（3）以顶点V1为起点的深度优先遍历生成树；（4）由顶点V1到顶点V3的最短路径。333625181029383042143265【解答】(1) (2)V1,V2,V4,V6
6、,V3,V5124635(3) 顶点集合V(G)=V1,V2,V3,V4,V5,V6 边的集合 E(G)=,(4) V1到V3最短路径为67: (V1V4V3) 迭代 集合 S选择顶点 D D2 D3 D4 D5 D6初值 v1 33 29 251v1, v6v6 33 29 252 v1, v6, v4v433 67 29 71 3 v1, v6, v4, v2v233 67 71 4v1,v6, v4, v2,v3v3 67 71 5v1,v6,v4, v2,v3,v5v 717.17已知一有向网的邻接矩阵如下，如需在其中一个顶点建立娱乐中心，要求该顶点距其它各顶点的最长往返路程最短，相同
7、条件下总的往返路程越短越好，问娱乐中心应选址何处？给出解题过程。习题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(尚未确定最短
8、路径的顶点集合) DIST2345678初态12,3,4,5,6,7,83060105 1,52,3,4,6,7,82560101761,5,62,3,4,7,8 203360172521,5,6,23,4,7,82033602571,5,6,2,73,4,83128253541,5,6,2,7,43,831283531,5,6,2,7,4,35,8313581,5,6,2,7,4,3,8835顶点1到其它顶点的最短路径依次是20，31，28，10，17，25，35。按Dijkstra算法所选顶点依次是5，6，2，7，4，3，8。 7.19对图示的AOE网络，计算各活动弧的e(ai)和l(ai
9、)的函数值，各事件（顶点）的ve（vi）和vl (vi)的函数值，列出各条关键路径。【解答】顶点ABCDEFGHWVe(i)016342413392252Vl(i)02924373113392252活动a1a2a3a4a5a6a7a8a9a10a11a12a13a14a15a16a17e(i)000016633424131313392222l(i)281803292431343731203613392240aCFHGW，长52。 关键路径是： 活动与顶点的对照表：a1 a2 a3 a4 a5 a6 a7 a8a9 a10 a11 a12 a13 a14 a15 a16 a177.20 利用弗洛
10、伊德算法，写出如图所示相应的带权邻接矩阵的变化。3214596823110【解答】A0= A1= A2= A3= A4= 二、算法设计题7.21 设无向图G有n个顶点，m条边。试编写用邻接表存储该图的算法。void CreatGraph (AdjList g)建立有n个顶点和m 条边的无向图的邻接表存储结构int n,m; scanf(%d%d,&n,&m);for(i=0,in;i+)输入顶点信息,建立顶点向量 scanf(&gi.vertex); gi.firstarc=null;for(k=0;kadjvex=j; p-next=gi.firstarc; gi.firstarc=p; 将边结点链入 p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=i;p-next=gj.firstarc;gj.frstarc=p;for
