数据结构第5章-图

第6章图1．选择题（1）在一个图中，所有顶点的度数之和等于图的边数的（）倍。A．1/2B．1C．2D．4（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A．1/2B．1C．2D．4（3）具有n个顶点的有向图最多有（）条边。A．nB．n(n-1)C．n(n+1)D．n2（4）n个顶点的连通图用邻接距阵表示时，该距阵至少有（）个非零元素。A．nB．2(n-1)C．n/2D．n2（5）G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。A．7B．8C．9D．10（6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。A．非连通B．连通C．强连通D．有向（7）下面（）算法适合构造一个稠密图G的最小生成树。A．Prim算法B．Kruskal算法C．Floyd算法D．Dijkstra算法（8）用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。A．栈B.队列C.树D．图（9）用邻接表表示图进行深度优先遍历时，通常借助（）来实现算法。A．栈B.队列C.树D．图（10）深度优先遍历类似于二叉树的（）。A．先序遍历B．中序遍历C．后序遍历D．层次遍历（11）广度优先遍历类似于二叉树的（）。A．先序遍历B．中序遍历C．后序遍历D．层次遍历（12）图的BFS生成树的树高比DFS生成树的树高（）。A．小B．相等C．小或相等D．大或相等（13）已知图的邻接矩阵如图6.25所示，则从顶点0出发按深度优先遍历的结果是（）。A．0243156B．0136542C．0134256D．03615420100011101100001011010110011001000110010011011110图6.25邻接矩阵（14）已知图的邻接表如图6.26所示，则从顶点0出发按广度优先遍历的结果是（），按深度优先遍历的结果是（）。图6.26邻接表（15）下面（）方法可以判断出一个有向图是否有环。A．深度优先遍历B．拓扑排序C．求最短路径D．求关键路径2．应用题（1）已知如图6.27所示的有向图，请给出：①每个顶点的入度和出度；②邻接矩阵；③邻接表；④逆邻接表。图6.27有向图A．0132B．0231C．0321D．0123（2）已知如图6.28所示的无向网，请给出：①邻接矩阵；②邻接表；③最小生成树a→b4→c3b→a4→c5→d5→e9^c→a3→b5→d5→h5^d→b5→c5→e7→f6→g5→h4^e→b9→d7→f3^f→d6→e3→g2^g→d5→f2→h6^h→c5→d4→g6^（3）已知图的邻接矩阵如6.29所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。图6.28无向网6456252363794567555553955434（4）有向网如图6.30所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表6.9。D终点i=1i=2i=3i=4i=5i=6b15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)c2(a,c)d12(a,d)12(a,d)11(a,c,f,d)11(a,c,f,d)e∞10(a,c,e)10(a,c,e)f∞6(a,c,f)g∞∞16(a,c,f,g)16(a,c,f,g)14(a,c,f,d,g)S终点集{a,c}{a,c,f}{a,c,f,e}{a,c,f,e,d}{a,c,f,e,d,g}{a,c,f,e,d,g,b}（5）试对图6.31所示的AOE-网：①求这个工程最早可能在什么时间结束；②求每个活动的最早开始时间和最迟开始时间；③确定哪些活动是关键活动图6.29邻接矩阵图6.31AOE-网图6.30有向网【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l-e=0?来确定关键活动，从而确定关键路径。123456Ve01915293843Vl019153738431,21,33,22,42,53,54,65,6e00151919152938l170152719273738l-e1700801280此工程最早完成时间为43。关键路径为1,33,22,55,63．算法设计题（1）分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作：①增添一个新顶点v，InsertVex(G,v)；②删除顶点v及其相关的边，DeleteVex(G,v);③增加一条边v，w，InsertArc(G,v,w);④删除一条边v，w，DeleteArc(G,v,w)。//本题中的图G均为有向无权图,其余情况容易由此写出StatusInsert_Vex(MGraph&G,charv)//在邻接矩阵表示的图G上插入顶点v{if(G.vexnum+1)MAX_VERTEX_NUMreturnINFEASIBLE;G.vexs[++G.vexnum]=v;returnOK;}//Insert_VexStatusInsert_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上插入边(v,w){if((i=LocateVex(G,v))0)returnERROR;if((j=LocateVex(G,w))0)returnERROR;if(i==j)returnERROR;if(!G.arcs[j].adj){G.arcs[j].adj=1;G.arcnum++;}returnOK;}//Insert_ArcStatusDelete_Vex(MGraph&G,charv)//在邻接矩阵表示的图G上删除顶点v{n=G.vexnum;if((m=LocateVex(G,v))0)returnERROR;G.vexs[m]-G.vexs[n];//将待删除顶点交换到最后一个顶点for(i=0;in;i++){G.arcs[m]=G.arcs[n];G.arcs[m]=G.arcs[n];//将边的关系随之交换}G.arcs[m][m].adj=0;G.vexnum--;returnOK;}//Delete_Vex分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加.StatusDelete_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上删除边(v,w){if((i=LocateVex(G,v))0)returnERROR;if((j=LocateVex(G,w))0)returnERROR;if(G.arcs[j].adj){G.arcs[j].adj=0;G.arcnum--;}returnOK;}//Delete_Arc//为节省篇幅,本题只给出Insert_Arc算法.其余算法请自行写出.StatusInsert_Arc(ALGraph&G,charv,charw)//在邻接表表示的图G上插入边(v,w){if((i=LocateVex(G,v))0)returnERROR;if((j=LocateVex(G,w))0)returnERROR;p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-nextarc=NULL;if(!G.vertices.firstarc)G.vertices.firstarc=p;else{for(q=G.vertices.firstarc;q-q-nextarc;q=q-nextarc)if(q-adjvex==j)returnERROR;//边已经存在q-nextarc=p;}G.arcnum++;returnOK;}//Insert_Arc（2）一个连通图采用邻接表作为存储结构，设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。数据结构考研指导232页7.3.7（3）设计一个算法，求图G中距离顶点v的最短路径长度最大的一个顶点，设v可达其余各个顶点。数据结构考研指导232页7.3.8（4）试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。解1：intvisited[MAXSIZE];//指示顶点是否在当前路径上intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0{if(i==j)return1;//i就是jelse{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p-nextarc){k=p-adjvex;if(!visited[k]&&exist_path(k,j))return1;//i下游的顶点到j有路径}//for}//else}//exist_path_DFS解2：（以上算法似乎有问题：如果不存在路径，则原程序不能返回0。我的解决方式是在原程序的中引入一变量level来控制递归进行的层数。具体的方法我在程序中用红色标记出来了。）intvisited[MAXSIZE];//指示顶点是否在当前路径上intlevel＝1;//递归进行的层数intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0{if(i==j)return1;//i就是jelse{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p-nextarc，level--){level++;k=p-adjvex;if(!visited[k]&&exist_path(k,j))return1;//i下游的顶点到j有路径}//for}//elseif(level==1)return0;}//exist_path_DFS（5）采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为为k的简单路径。（注1：一条路径为简单路径指的是其顶点序列中不含有重现的顶点。注2：此题可参见严题集P207-208中有关按“路径”遍历的算法基本框架。）intvisited[MAXSIZE];intexist_path_len(ALGraphG,inti,intj,intk)//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径{{if(i==j&&k==0)return1;//找到了一条路径,且长度符合要求elseif(k0){visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p-nextarc){l=p-adjvex;if(!visited[l])if(exist_path_len(G,l,j,k-1))return1;//剩余路径长度减一}//forvisited[i]=0;//本题允许曾经被访问过的结点出现在另一条路径中}//elsereturn0;//没找到}//exist_path_len