第6章-图习题参考答案

习题六参考答案一、选择题1.在一个有个顶点的有向图中，若所有顶点的出度之和为，则所有顶点的入度之和为（A）。A.B.C.D.2.一个有向图有个顶点，则每个顶点的度可能的最大值是（B）。A.B.C.D.3.具有6个顶点的无向图至少应有（A）条边才能确保是一个连通图。A.5B.6C.7D.84.一个有n个顶点的无向图最多有（C）条边。A.B.C.D.5.对某个无向图的邻接矩阵来说，下列叙述正确的是（A）。A.第行上的非零元素个数和第列上的非零元素个数一定相等B.矩阵中的非零元素个数等于图中的边数C.第行与第列上的非零元素的总数等于顶点的度数D.矩阵中非全零行的行数等于图中的顶点数6.已知一个有向图的邻接矩阵，要删除所有以第个顶点为孤尾的边，应该（B）。A.将邻接矩阵的第行删除B.将邻接矩阵的第行元素全部置为0C.将邻接矩阵的第列删除D.将邻接矩阵的第列元素全部置为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.若用表示图中顶点数，则有条边的无向图称为完全图。2.若一个无向图有100条边，则其顶点总数最少为15个。3.个顶点的连通无向图至少有条边，至多有条边。4.若有向图的邻接矩阵为：则顶点的入度是3。5.对于一个有向图，若一个顶点的度为，出度为，则对应逆邻接表中该顶点单链表中的边结点数为。6.图的遍历算法BFS中用到辅助队列，每个顶点最多进队1次。7.在求最小生成树的两种算法中，克鲁斯卡尔算法适合于稀疏图。8.数据结构中的迪杰斯特拉算法是用来求某个源点到其余各顶点的最短路径。9.除了使用拓扑排序的方法，还有深度优先搜索方法可以判断出一个有向图是否有回路。10.在用邻接表表示图时，拓扑排序算法的时间复杂度为。三、应用题1.已知如图6.28所示的有向图，请给出该图的(1)每个顶点的出/入度；(2)邻接矩阵；(3)邻接表；(4)逆邻接表。答：(1)每个顶点的出/入度是：出度入度103222321431512632(2)邻接矩阵：(3)邻接表：(4)逆邻接表：401231234Λ503Λ124565Λ5Λ0Λ014Λ123456图6.28有向图2.试对如图6.29所示的非连通图，画出其广度优先生成森林。答：3.已知图的邻接矩阵如图6.30所示。试分别画出自顶点A出发进行遍历所得的深度优先生成树和广度优先生成树。答：图错误!文档中没有指定样式的文字。.30邻接矩阵GIKHEDACFBLJM图错误!文档中没有指定样式的文字。.29非连通图GIKHEDACFBLJM401231234525Λ3Λ1Λ56323Λ145Λ5Λ4.请对如图6.31所示的无向网：(1)写出它的邻接矩阵，并按克鲁斯卡尔算法求其最小生成树；(2)写出它的邻接表，并按普里姆算法求其最小生成树。答：(1)534655图错误!文档中没有指定样式的文字。.31无向网5437ABEFDC9GH526IHDABFGJCEIHEDABFGJC(2)ABCD0123EFGH456714Λ32042535Λ941525475665Λ47031535Λ571937Λ353643Λ263552Λ672534Λ66克鲁斯卡尔算法求其最小生成树ABEFDCGH23ABEFDCGH23ABEFDCGH23343ABEFDCGH23443ABEFDCGH234543ABEFDCGH234543ABEFDC9GH525.试列出图6.32中全部可能的拓扑有序序列。答：abcdef、abcef、abecdf、bacdef、bacedf、baecdf、beacdf四、算法设计题1.编写算法，从键盘读入有向图的顶点和弧，创建有向图的邻接表存储结构。参考答案:publicstaticALGraphcreateDG(){Scannersc=newScanner(System.in);System.out.println(请分别输入有向图的顶点数和边数:);intvexNum=sc.nextInt();intarcNum=sc.nextInt();VNode[]vexs=newVNode[vexNum];System.out.println(请分别输入有向图的各个顶点:);for(intv=0;vvexNum;v++)//构造顶点向量vexs[v]=newVNode(sc.next());ALGraphG=newALGraph(GraphKind.DG,vexNum,arcNum,vexs);System.out.println(请输入各个边的起点和终点:);for(intk=0;karcNum;k++){abce图6.32有向图fd普里姆算法求其最小生成树，从A开始3ABEFDCGH43ABEFDCGH543ABEFDCGH4543ABEFDCGH4543ABEFDCGH54543ABEFDCGH5234543ABEFDCGH52intv=G.locateVex(sc.next());intu=G.locateVex(sc.next());G.addArc(v,u,0);}returnG;}2.无向图采用邻接表存储结构，编写算法输出图中各连通分量的顶点序列。参考答案:publicstaticvoidCC_BFS(IGraphG)throwsException{boolean[]visited=newboolean[G.getVexNum()];//访问标志数组for(intv=0;vG.getVexNum();v++)//访问标志数组初始化visited[v]=false;LinkQueueQ=newLinkQueue();//辅助队列QLinkQueueP=newLinkQueue();//辅助队列P,用于记录连通分量的顶点inti=0;//用于记数连通分量的个数for(intv=0;vG.getVexNum();v++){P.clear();//队列清空if(!visited[v]){//v尚未访问visited[v]=true;P.offer(G.getVex(v));Q.offer(v);//v入队列while(!Q.isEmpty()){intu=(Integer)Q.poll();//队头元素出队列并赋值给ufor(intw=G.firstAdjVex(u);w=0;w=G.nextAdjVex(u,w)){if(!visited[w]){//w为u的尚未访问的邻接顶点visited[w]=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的路径（u≠v）。可以采用深度优先搜索遍历策略。当顶点u和顶点v在无向图的同一连通分量中时，从顶点u到顶点v一定有路径，可从顶点u（v）进行深度优先搜索，一定可以遍历至顶点v（u）。否则，遍历不能成功，不存在由顶点u到顶点v的路径。参考答案:privateboolean[]visited;//访问标志数组privatebooleanfind=false;//标示是否已找到了指定长度的路径publicvoidfindPath(IGraphG,intu,intv)throwsException{visited=newboolean[G.getVexNum()];for(intw=0;wG.getVexNum();w++)//访问标志数组初始化visited[w]=false;find_DFS(G,u,v);if(find)System.out.println(G.getVex(u)+和+G.getVex(v)+之间至少存在一条路径！);elseSystem.out.println(G.getVex(u)+和+G.getVex(v)+之间不存在路径！);}privatevoidfind_DFS(IGraphG,intu,intv)throwsException{if(u==v){find=true;}elseif(!find){visited[u]=true;for(intw=G.firstAdjVex(u);w=0;w=G.nextAdjVex(u,w))if(!visited[w])find_DFS(G,w,v);//对v的尚未访问的邻接顶点w递归调用find_DFS}}4.编写算法求距离顶点的最短路径长度为的所有顶点。参考答案://用迪杰斯特拉算法，当发现新顶点与顶点的距离大于时算法终止publicfinalstaticintINFINITY=Integer.MAX_VALUE;//用Dijkstra算法求vi顶点到其余顶点v的最短长度D[v]publicvoidfindVex_DIJ(MGraphG,intvi,intk)throwsException{intvexNum=G.getVexNum();int[]R=newint[vexNum];//存放距离vi距离为k的顶点int[]D=newint[vexNum];//vi到其余顶点的最短长度booleanisHaveVex=false;//记录是否存在距离到vi距离为k的点boolean[]finish=newboolean[vexNum];for(intv=0;vvexNum;v++){finish[v]=false;R[v]=-1;D[v]=G.getArcs()[vi][v];}D[vi]=0;//初始化，vi顶点属于S集finish[vi]=true;intv=-1;intj=0;//距离vi长度为k的点的增量//开始主循环，每次求得vi到某个v顶点的最短路径，并加v到S集for(inti=1;ivexNum;i++){//其余G.getVexNum-1个顶点intmin=INFINITY;//当前所知离vi顶点的最近距离for(intw=0;wvexNum;w++){if(!finish[w])if(D[w]min){v=w;min=D[w];}}if(min==k){R[j++]=v;isHaveVex=true;}elseif(mink)break;finish[v]=true;//离vi顶点最近的v加入S集//更新当前最短路径及距离for(intw=0;wvexNum;w++){if(!finish[w]&&G.getArcs()[v][w]INFINITY&&(min+G.getArcs()[v][w]D[w])){//修改D[w]和P[w],w属于V-SD[w]=min+G.getArcs()[v][w];}}}if(isHaveVex){System.out.println(距离vi长度为k的顶点为：);for(inti=0;iR.length;i++){if(R[i]!=-1)System.out.print(G.getVex(R[i])+\t);elsebrea