第6章 图习题参考答案.doc

习题六参考答案一、选择题1. 在一个有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（A）。A. sB. s-1C. s+1D. n2. 一个有向图有n个顶点，则每个顶点的度可能的最大值是（B）。A.n-1B.2(n-1) C.nD.2n3. 具有6个顶点的无向图至少应有（A）条边才能确保是一个连通图。A.5B.6C.7D.84. 一个有n个顶点的无向图最多有（C）条边。A.nB.nn-1C.nn-1/2D.2n5. 对某个无向图的邻接矩阵来说，下列叙述正确的是（A）。A.第i行上的非零元素个数和第i列上的非零元素个数一定相等B.矩阵中的非零元素个数等于图中的边数C.第i行与第i列上的非零元素的总数等于顶点vi的度数D.矩阵中非全零行的行数等于图中的顶点数6. 已知一个有向图的邻接矩阵，要删除所有以第i个顶点为孤尾的边，应该（B）。A.将邻接矩阵的第i行删除B.将邻接矩阵的第i行元素全部置为0C.将邻接矩阵的第i列删除D.将邻接矩阵的第i列元素全部置为07. 下面关于图的存储的叙述中，哪一个是正确的？（A）A用邻接矩阵存储图，占用的存储空间只与图中顶点数有关，而与边数无关B用邻接矩阵存储图，占用的存储空间只与图中边数有关，而与顶点数无关C用邻接表存储图，占用的存储空间只与图中顶点数有关，而与边数无关D用邻接表存储图，占用的存储空间只与图中边数有关，而与顶点数无关8. 对图的深度优先遍历，类似于对树的哪种遍历？（A）A.先根遍历B.中根遍历C后根遍历D层次遍历9. 任何一个无向连通图的最小生成树（B）。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在10. 下面是三个关于有向图运算的叙述：（1）求两个指向结点间的最短路径，其结果必定是唯一的（2）求有向图结点的拓扑序列，其结果必定是唯一的（3）求AOE网的关键路径，其结果必定是唯一的其中哪个（些）是正确的？（D）A.只有（1）B.（1）和（2）C.都正确D.都不正确二、填空题1. 若用n表示图中顶点数，则有nn-1/2条边的无向图称为完全图。2. 若一个无向图有100条边，则其顶点总数最少为15个。3. n个顶点的连通无向图至少有n-1条边，至多有nn-1/2条边。4. 若有向图G的邻接矩阵为：v0v1v2v3v4v0v1v2v3v40110010101110110000001100则顶点v4的入度是3。5. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单链表中的边结点数为k1-k2。6. 图的遍历算法BFS中用到辅助队列，每个顶点最多进队1次。7. 在求最小生成树的两种算法中，克鲁斯卡尔算法适合于稀疏图。8. 数据结构中的迪杰斯特拉算法是用来求某个源点到其余各顶点的最短路径。9. 除了使用拓扑排序的方法，还有深度优先搜索方法可以判断出一个有向图是否有回路。10. 在用邻接表表示图时，拓扑排序算法的时间复杂度为On+e。三、应用题1. 已知如图6.28所示的有向图，请给出该图的123456图 6.28有向图(1) 每个顶点的出/入度；(2) 邻接矩阵；(3) 邻接表；(4) 逆邻接表。答：(1) 每个顶点的出/入度是：出度入度103222321431512632(2) 邻接矩阵：123456123456001000010000010000100111101100000010(3) 邻接表：40123123450312456550014(4) 逆邻接表：401231234525315632314552. 试对如图6.29所示的非连通图，画出其广度优先生成森林。图 Error! No text of specified style in document.29非连通图GIKHEDACFBLJM答：GIKHEDACFBLJM3. 已知图的邻接矩阵如图6.30所示。试分别画出自顶点A出发进行遍历所得的深度优先生成树和广度优先生成树。ABCDEFGHIJABCDEFGHIJ0000010000000001001010100001000000001100100010000010000100000011000100000001000010010001001010000010图 Error! No text of specified style in document.30邻接矩阵答：IHEDABFGJC IHDABFGJCE4. 请对如图6.31所示的无向网：(1) 写出它的邻接矩阵，并按克鲁斯卡尔算法求其最小生成树；(2) 写出它的邻接表，并按普里姆算法求其最小生成树。534655图Error! No text of specified style in document.31无向网5437ABEFDC9GH526答：(1)ABCDEFGHABCDEFGH043405350555509576549765540330220660克鲁斯卡尔算法求其最小生成树ABEFDCGH23ABEFDCGH23ABEFDCGH23343ABEFDCGH23443ABEFDCGH234543ABEFDCGH234543ABEFDC9GH52(2)ABCD0123EFGH456714320425359415254756654703153557193735364326355267253466普里姆算法求其最小生成树，从A开始3ABEFDCGH43ABEFDCGH543ABEFDCGH4543ABEFDCGH4543ABEFDCGH54543ABEFDCGH5234543ABEFDCGH525. 试列出图6.32中全部可能的拓扑有序序列。abce图 6.32有向图fd答：abcdef、abcef、abecdf、bacdef、bacedf、baecdf、beacdf四、算法设计题1. 编写算法，从键盘读入有向图的顶点和弧，创建有向图的邻接表存储结构。参考答案:public static ALGraph createDG() Scanner sc = new Scanner(System.in);System.out.println(请分别输入有向图的顶点数和边数:);int vexNum = sc.nextInt();int arcNum = sc.nextInt();VNode vexs = new VNodevexNum;System.out.println(请分别输入有向图的各个顶点:);for (int v = 0; v vexNum; v+)/ 构造顶点向量vexsv = new VNode(sc.next();ALGraph G = new ALGraph(GraphKind.DG, vexNum, arcNum, vexs);System.out.println(请输入各个边的起点和终点:);for (int k = 0; k arcNum; k+) int v = G.locateVex(sc.next();int u = G.locateVex(sc.next();G.addArc(v, u, 0);return G; 2. 无向图采用邻接表存储结构，编写算法输出图中各连通分量的顶点序列。参考答案:public static void CC_BFS(IGraph G) throws Exception boolean visited = new booleanG.getVexNum();/ 访问标志数组for (int v = 0; v G.getVexNum(); v+)/ 访问标志数组初始化visitedv = false;LinkQueue Q = new LinkQueue();/ 辅助队列QLinkQueue P = new LinkQueue();/ 辅助队列P,用于记录连通分量的顶点int i = 0;/ 用于记数连通分量的个数for (int v = 0; v = 0; w = G.nextAdjVex(u,w) if (!visitedw) / w为u的尚未访问的邻接顶点visitedw = true;P.offer(G.getVex(w);Q.offer(w);System.out.println(图的第 + +i + 个连通分量为：);while (!P.isEmpty()System.out.print(P.poll().toString() + );System.out.println();3. 编写算法判别以邻接表方式存储的无向图中是否存在由顶点u到顶点v的路径（uv）。可以采用深度优先搜索遍历策略。当顶点u和顶点v在无向图的同一连通分量中时，从顶点u到顶点v一定有路径，可从顶点u（v）进行深度优先搜索，一定可以遍历至顶点v（u）。否则，遍历不能成功，不存在由顶点u到顶点v的路径。参考答案:private boolean visited;/ 访问标志数组private boolean find = false;/ 标示是否已找到了指定长度的路径publ