2023年图习题参考答案

习题六参考答案一、选择题在一个有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（A）。A.sB.s-1C.s一个有向图有n个顶点，则每个顶点的度也许的最大值是（B）。A.n-1B.2(n-1)C.nD.2n具有6个顶点的无向图至少应有（A）条边才干保证是一个连通图。A.5B.6C.7D.8一个有n个顶点的无向图最多有（C）条边。A.nB.nn-1C.对某个无向图的邻接矩阵来说，下列叙述对的的是（A）。A.第i行上的非零元素个数和第i列上的非零元素个数一定相等B.矩阵中的非零元素个数等于图中的边数C.第i行与第i列上的非零元素的总数等于顶点viD.矩阵中非全零行的行数等于图中的顶点数已知一个有向图的邻接矩阵，要删除所有以第i个顶点为孤尾的边，应当（B）。A.将邻接矩阵的第i行删除B.将邻接矩阵的第i行元素所有置为0C.将邻接矩阵的第i列删除D.将邻接矩阵的第i列元素所有置为0下面关于图的存储的叙述中，哪一个是对的的？……（A）A．用邻接矩阵存储图，占用的存储空间只与图中顶点数有关，而与边数无关B．用邻接矩阵存储图，占用的存储空间只与图中边数有关，而与顶点数无关C．用邻接表存储图，占用的存储空间只与图中顶点数有关，而与边数无关D．用邻接表存储图，占用的存储空间只与图中边数有关，而与顶点数无关对图的深度优先遍历，类似于对树的哪种遍历？……（A）A.先根遍历B.中根遍历C．后根遍历D．层次遍历任何一个无向连通图的最小生成树（B）。A.只有一棵B.有一棵或多棵C.一定有多棵D.也许不存在下面是三个关于有向图运算的叙述：（1）求两个指向结点间的最短途径，其结果必然是唯一的（2）求有向图结点的拓扑序列，其结果必然是唯一的（3）求AOE网的关键途径，其结果必然是唯一的其中哪个（些）是对的的？……（D）A.只有（1）B.（1）和（2）C.都对的D.都不对的二、填空题若用n表达图中顶点数，则有nn-若一个无向图有100条边，则其顶点总数最少为15个。n个顶点的连通无向图至少有n-1条边，至多有n若有向图G的邻接矩阵为：v则顶点v4的入度是3对于一个有向图，若一个顶点的度为k1，出度为k2，则相应逆邻接表中该顶点单链表中的边结点数为k1-k2图的遍历算法BFS中用到辅助队列，每个顶点最多进队1次。在求最小生成树的两种算法中，克鲁斯卡尔算法适合于稀疏图。数据结构中的迪杰斯特拉算法是用来求某个源点到其余各顶点的最短途径。除了使用拓扑排序的方法，尚有深度优先搜索方法可以判断出一个有向图是否有回路。在用邻接表表达图时，拓扑排序算法的时间复杂度为On+e三、应用题已知如图6.28所示的有向图，请给出该图的123123456图6.28有向图(1)每个顶点的出/入度；(2)邻接矩阵；(3)邻接表；(4)逆邻接表。答：(1)每个顶点的出/入度是：出度入度103222321431512632(2)邻接矩阵：(3)邻接表：4401231234Λ503Λ124565Λ5Λ0Λ014Λ(4)逆邻接表：4401231234525Λ3Λ1Λ56323Λ145Λ5Λ试对如图6.29所示的非连通图，画出其广度优先生成森林。图图STYLEREF1\s6.29非连通图GIKHEDACFBLJM答：GGIKHEDACFBLJM已知图的邻接矩阵如图6.30所示。试分别画出自顶点A出发进行遍历所得的深度优先生成树和广度优先生成树。A图图STYLEREF1\s6.30邻接矩阵答：IHEIHEDABFGJCIHDABFGJCE请对如图6.31所示的无向网：(1)写出它的邻接矩阵，并按克鲁斯卡尔算法求其最小生成树；(2)写出它的邻接表，并按普里姆算法求其最小生成树。5534655图STYLEREF1\s6.31无向网5437ABEFDC9GH526答：(1)A克鲁斯卡尔算法求其最小生成树克鲁斯卡尔算法求其最小生成树ABEFDCGH23ABEFDCGH23ABEFDCGH23343ABEFDCGH23443ABEFDCGH234543ABEFDCGH234543ABEFDC9GH52(2)AABCD0123EFGH456714Λ32042535Λ941525475665Λ47031535Λ571937Λ353643Λ263552Λ672534Λ66普里姆算法求其最小生成树普里姆算法求其最小生成树，从A开始3ABEFDCGH43ABEFDCGH543ABEFDCGH4543ABEFDCGH4543ABEFDCGH54543ABEFDCGH5234543ABEFDCGH52试列出图6.32中所有也许的拓扑有序序列。aabce图6.32有向图fd答：abcdef、abcef、abecdf、bacdef、bacedf、baecdf、beacdf四、算法设计题编写算法，从键盘读入有向图的顶点和弧，创建有向图的邻接表存储结构。参考答案:publicstaticALGraphcreateDG(){ Scannersc=newScanner(System.in); System.out.println("请分别输入有向图的顶点数和边数:"); intvexNum=sc.nextInt(); intarcNum=sc.nextInt(); VNode[]vexs=newVNode[vexNum]; System.out.println("请分别输入有向图的各个顶点:"); for(intv=0;v<vexNum;v++) //构造顶点向量 vexs[v]=newVNode(sc.next()); ALGraphG=newALGraph(GraphKind.DG,vexNum,arcNum,vexs); System.out.println("请输入各个边的起点和终点:"); for(intk=0;k<arcNum;k++){ intv=G.locateVex(sc.next()); intu=G.locateVex(sc.next()); G.addArc(v,u,0); } returnG; }无向图采用邻接表存储结构，编写算法输出图中各连通分量的顶点序列。参考答案:publicstaticvoidCC_BFS(IGraphG)throwsException{ boolean[]visited=newboolean[G.getVexNum()];//访问标志数组 for(intv=0;v<G.getVexNum();v++) //访问标志数组初始化 visited[v]=false; LinkQueueQ=newLinkQueue();//辅助队列Q LinkQueueP=newLinkQueue();//辅助队列P,用于记录连通分量的顶点 inti=0;//用于记数连通分量的个数 for(intv=0;v<G.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();//队头元素出队列并赋值给u for(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(); } } }编写算法判别以邻接表方式存储的无向图中是否存在由顶点QUOTEuu到顶点v的途径（QUOTEu≠vu≠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;w<G.getVexNum();w++) //访问标志数组初始化 visited[w]=false; find_DFS(G,u,v); if(find) System.out.println(G.getVex(u)+"和"+G.getVex(v)+"之间至少存在一条途径！"); else System.out.println(G.getVex(u)+"和"+G.getVex(v)+"之间不存在途径！"); } privatevoidfind_DFS(IGraphG,intu,intv)thro