搜索
第七章图一、名词解释1.图2.无向完全图3.有向完全图4.子图5.连通分量6.图的遍历7.图的最小生成树8.拓扑排序一、填空题1.设x,y是图G中的两顶点，则（x,y）与（y,x）被认为________边，但x,y与y,x是________的两条弧。2.若顶点的偶对是有序的，此图为________图，有序偶对用________括号括起来；若顶点偶对是无序的，此图为________图，无序偶对用________括号括起来。3.设x,y∈V，若x,y∈E,则x,y表示有向图G中从x到y的一条________，x称为________点，y称为________点。若（x,y）∈E，则在无向图G中x和y间有一条________。4.在无向图中，若顶点x与y间有边（x,y），则x与y互称________，边（x,y）称为与顶点x和y________。5.一个具有n个顶点的完全无向图的边数为________。一个具有n个顶点的完全有向图的弧度数为________。6.图的边或弧附带的数值叫________。每条边或弧都带权的图称为________或________。7.无向图中的顶点V的度是________，记为________。若G是一个有向图，则把以顶点V为终点的弧的数目称为V的________，记为________；把以顶点V为始点的弧的数目称为V的________，称为________。有向图中顶点V的度定义为D（V）=________。8.路径长度定义为________。第一个顶点和最后一个顶点相同的路径称为________或________。序列中顶点不重复出现的路径称为________。除了第一个顶点和最后一个顶点外，其余顶点不重复的回路，称为________或________。9.在无向图中，如果从顶点v到顶点v’有路径，则称v和v’是_______的。如果对于图中的任意两个顶点vi,vj∈V，且vi和vj都是连通的，则称G为________。10.连通分量是无向图中的________连通子图。11.一个连通图的生成树是含有该连通图的全部顶点的一个________。12.若连通图G的顶点个数为n，则G的生成树的边数为________。如果G的一个子图G’的边数________，则G’中一定有环。相反，如果G’的边数________，则G’一定不连通。13.无向图的邻接矩阵是一个________矩阵，有向图的邻接矩阵不一定是________矩阵。14.对于无向图的邻接矩阵，顶点vi的度是________________。对于有向图的邻接矩阵，顶点vi的出度OD（vi）为________________，顶点vi的入度ID(vi)是________________。15.图的存储结构主要有________和________两种。16.邻接表表示法是借助________来反映顶点间的邻接关系，所以称这个单链表为邻接表。17.对无向图，若它有n顶点e条边，则其邻接表中需要________个结点。其中，________个结点构成邻接表，________个结点构成顶点表。18.对有向图，若它有n顶点e条边，则其邻接表中需要________个结点。其中，________个结点构成邻接表，________个结点构成顶点表。19.在邻接表上，无向图中顶点vi的度恰为________________。对有向图，顶点vi的出度是________________。为了求入度，必须遍历整个邻接表，在所有单链表中，其邻接点域的值为________的结点的个数是顶点vi的入度。20.遍历图的基本方法有________优先搜索和________优先搜索两种。21..以下是图的深度优先算法，请在________处填充适当的语句。Dfs(GraphTpg,intv){ArcNodeTp*p;printf(“%d”,v);visited[v]=1;p=________________;while(p!=NULL){if(!________________)Dfs(g,p-adjvex);22.以下是图的广度优先搜索算法，请在________处填充适当的语句。Bfs(GraphTpg,intv){QueptrTpQ;ArcNodeTp*p;InitQueue(&Q);printf(“%d”,v);visited[v]=1;________________p=________________;}}while(!EmptyQueue(Q)){________________;p=g.adjlist[v].firstarc;while(p!=NULL){if(!visited[p-adjvex]){printf(“%d”,p-adjvex);visited[[-adjvex]=1;EnQueue(&Q,p-adjvex);}________________;}}}23.深度优先搜索遍历类似于树的________遍历，它所用到的数据结构是________；广度优先搜索遍历类似于树的________遍历，它所用到的数据结构是________。24.任何连通图的连通分量只有一个，即________。25.对具有n个顶点的图其生成树有且仅有________条边，即生成树是图的边数________的连通图。26.一个图的________的表示法是惟一的，而________表示法是不惟一的。27.对无向图，其邻接矩阵是一个关于________对称的矩阵。28.在有向图的邻接矩阵上，由第i行可得到第________个结点的出度，而由第j列可得到第________个结点的入度。29.________的有向图，其全部顶点有可能排成一个拓扑序列。30.一个有向图G中若有弧,Vi,Vj、Vj,Vk和Vi,Vk,则在图G的拓扑序列中，顶点Vi、Vj和Vk的相对位置为________。二、单项选择题1.设有无向图G=（V，E）和G’=（V’,E’）,如G’为G的生成树，则下面不正确的说法是（）①G’为G的子图②G’为G的连通分量③G’为G的极小连通子图且V’=V④G’是G的无环子图2.任何一个带权的无向连通图的最小生成树（）①只有一棵②有一棵或多棵③一定有多棵④可能不存在3.设图G采用邻接表存储，则拓扑排序算法的时间复杂度为（）①O(n)②O(n+e)③O(n*n)④O(n*e)4.含n个顶点的连通图中的任意一条简单路径，其长度不可能超过（）①1②n/2③n-1④n5．一有向图G的邻接表存储结构如图单项选择5所示。现按深度优先遍历算法，从顶点V1出发，所得到的顶点序列是（）①V1,V3,V2,V4,V5②V1,V3,V4,V2,V5③V1,V2,V3,V4,V5④V1,V3,V4,V5,V26.在无向图中，所有顶点的度数之和是所有边数的（）倍。①0.5②1③2④47.在有向图中，所有顶点的入度之和是所有顶点出度之和的（）倍。（）①0.5②1③2④48．在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的（）①先根遍历②中根遍历③后根遍历④按层次遍历9．在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的（）①先根遍历②中根遍历③后根遍历④按层次遍历10．判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用（）①求关键路径方法②求最短路径的Dijkstra方法③广度优先遍历方法④深度优先遍历方法11．在图单项选择中，从顶点V1出发，按广度优先遍历图的顶点序列是（）①V1V3V5V4V2V6V7②V1V2V4V7V6V5V3③V1V5V3V4V2V7V6④V1V4V7V2V6V5V312.在图单项选择中，从顶点V1出发,广度遍历图的顶点序列是（）①V1V5V3V4V2V6V7②V1V5V3V4V2V7V6③V1V7V2V6V4V5V3④V1V2V4V7V6V5V313.设有6个结点的无向图，该图至少应有（）条边能确保是一个连通图。（）①5②6③7④814.以下说法正确的是（）①连通图的生成树，是该连通图的一个极小连通子图。②无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。③任何一个有向图，其全部顶点可以排成一个拓扑序列。④有回路的图不能进行拓扑排序。15以下说法错误的是（）①用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。②邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用。③存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角部分就可以了③用相邻矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查A的第i行第j列的元素是否为0即可。16．以下说法正确的是（）①连通分量是无向图中的极小连通子图。②强连通分量是有向图中的极大强连通子图。③在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧a,b。④对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。16.设有一无向图G=(V,E),其中V={1,2,3,4,5,6},E={(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5)}。（1）按上述顺序输入后，画出其相应的邻接表；（2）在该邻接表上，从顶点4开始，写出DFS序列和BFS序列。17．图简答题17-1所示为一无向连通网络，先要求根据prim算法构造出它的最小生成树。写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开始时间和最晚开始时间。【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下（1）求事件的最早发生时间ve(j),最晚发生时间vl(j);（2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6),最晚发生时间从vl(6)按逆拓扑排序向后递推到vl(0);（3）计算e(i),l(i)：设ai由弧j,k表示，持续时间记为dutj,k，则有下式成立e(i)=ve(j)l(i)=vl(k)-dut(j,k)（4）找出e(i)-l(i)=0的活动既是关键活动。【答案】关键路径为：a0-a4-a6-a98．拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。【解析】解题关键是弄清拓扑排序的步骤（1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。【答案】（1）0132465（2）01234659．给定带权有向图G和源点v1,利用迪杰斯特拉（Dijkstra）算法求从v1到其余各顶点的最短路径。【解析】求解该题的关键是掌握迪杰斯特拉（Dijkstra）算法的设计原理----从一个顶点v到另一顶点vk的最短路径或者是(v,vk)或者是(v,vj,vk),它的长度或者是从v到vk弧上的权值，或者是D[j]与vj到vk弧上的权值之和，其中D[j]是已经找到的从v到vj的最短路径。【答案】S是已找到最短路径的终点的集合。10．利用Floyd算法求下图中各对顶点之间的路径。【解析】Floyd算法是依次添加顶点来修改相应路径，也就是说,若（vi，．．．，vk）和(vk，．．．，vj)分别是从vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径，则将（vi，．．．vk，．．．，vj）和已经得到的从vi到vj且中间顶点序号不大于k-１的最短路径相比较，其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。经过n次比较后必求得vi到vj的最短路径，依次，可求得各对顶点间的最短路径。求解的关键是求解如下的一个n阶方阵序列：D(-1)，D(0)，D(1)，．．．，D(k)，D(n-1)其中D(-1)[i][j]=G．arcs[i][j]D(k)=Min{D(k-1)[i][j]，D(k-1)[i][k]