习题七 图
一、单项选择题
1.设有无向图G=（V，E）和G’=（V’,E’）,如G’为G的生成树，则下面不正确的说法是（ ）
A．G’为G的子图 B．G’为G的连通分量 C．G’为G的极小连通子图且V’=V D．G’是G的无环子图 2.任何一个带权的无向连通图的最小生成树（ ）
A．只有一棵 B．有一棵或多棵 C．一定有多棵 D．可能不存在 3．以下说法正确的是（ ）
A．连通分量是无向图中的极小连通子图。 B．强连通分量是有向图中的极大强连通子图。
C．在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。 D．对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。 4．图中有关路径的定义是（ ）。
A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 5．设无向图的顶点个数为n，则该图最多有（ ）条边。
2
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n 6．要连通具有n个顶点的有向图，至少需要（ ）条边。
A．n-l B．n C．n+l D．2n
7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。
A．1/2 B．2 C．1 D．4 8．下列哪一种图的邻接矩阵是对称矩阵？（ ）
A．有向图 B．无向图 C．AOV网 D．AOE网 9. 下列说法不正确的是（ ）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程
10．下面哪一方法可以判断出一个有向图是否有环（回路）：
A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径
11. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。
23
A. O(n) B. O(n+e) C. O(n) D. O(n) 12．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={
A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7
13. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。
A．G中有弧
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 15．下列关于AOE网的叙述中，不正确的是（ ）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成
二、填空题
1．具有10个顶点的无向图，边的总数最多为______。
2. 设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di（1<=i<=n），则e=______
3. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。
4．下图中的强连通分量的个数为______个。
5．N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。
6. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是__ ____。
7. 对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为______，邻接表的边结点个数为______。
8. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。
9．构造连通网最小生成树的两个典型算法是__ ____。
10. 有向图G可拓扑排序的判别条件是__ ____。
11. Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按__ ____次序依次产生，该算法弧上的权出现___ ___情况时，不能正确产生最短路径。
12.有向图G=(V,E),其中 V(G)={0,1,2,3,4,5}，用三元组表示弧及弧上的权d.E(G)为{<0,5,100>,<0,2,10><1,2,5><0,4,30><4,5,60><3,5,10><2,3,50><4,3,20>}，则
从源点0到顶点3的最短路径长度是______，经过的中间顶点是___ ___。
13．AOV网中,结点表示______,边表示______。AOE网中,结点表示______,边表示______。
14．在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为___ ___。
15．在 AOV网 中，存在环意味着___ ___，这是__ ____的；对程序的数据流图来说，它表明存在__ ____。
V2 16．如下为拓扑排序的C程序，
（1）．列出对右图执行该程序后的输出结果。 V1 V3 V5 __ ____
V4 V6 （2）．在程序空白处填上适当语句。 void topsort(hdnodes graph [],int n)
{int i,j,k,top; node_pointer ptr ; top=-1;
for (i=0; i if (!graph[i].count){graph[i].count=top; top=i; } for (i=0; i if(1)_ ___ {fprintf(stderr, \ exit(1); } else {j=top;(2)_ ____; printf( \ for (ptr=graph[j].link; ptr; ptr=ptr->link) {k=ptr->vertex; graph[k].count--; if((3)__ ___) {graph[k].count=top; top=k; } } } } 三、应用题 1．已知如图所示的有向图，请给出该图的： （1） 每个顶点的入度、出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表； （5） 强连通分量。 2．已知图的邻接矩阵为： V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V1 0 1 1 1 0 0 0 0 0 0 V2 0 0 0 1 1 0 0 0 0 0 V3 0 0 0 1 0 1 0 0 0 0 V4 0 0 0 0 0 1 1 0 1 0 V5 0 0 0 0 0 0 1 0 0 0 V6 0 0 0 0 0 0 0 1 1 0 V7 0 0 0 0 0 0 0 0 1 0 V8 0 0 0 0 0 0 0 0 0 1 V9 0 0 0 0 0 0 0 0 0 1 V10 0 0 0 0 0 0 0 0 0 0 当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出： （1）．以顶点V1为出发点的唯一的深度优先遍历； （2）．以顶点V1为出发点的唯一的广度优先遍历； （3）．该图唯一的拓扑有序序列。 3．已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。 20 1 2 5 11 9 6 14 6 3 10 10 4 6 5 18 4．已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、 伦敦(L) 、 东京(T) 、 墨西哥(M),下表给定了这六大城市之间的交通里程: 世界六大城市交通里程表(单位:百公里) PE N PA L T M PE N PA L T M 109 82 81 21 124 109 58 55 108 32 82 58 3 97 92 81 55 3 95 89 21 108 97 95 113 124 32 92 89 113 （1）．画出这六大城市的交通网络图; （2）．画出该图的邻接表表示法; （3）．画出该图按权值递增的顺序来构造的最小(代价)生成树. 5．下表给出了某工程各工序之间的优先关系和各工序所需时间 （1）．画出相应的AOE网 （2）．列出各事件的最早发生时间,最迟发生时间 （3）．找出关键路径并指明完成该工程所需最短时间. 工序代号 A B C D E F G H I J K L M N 所需时间 15 10 50 8 15 40 300 15 120 60 15 30 20 40 先驱工作 -- -- A,B B C,D B E G,I E I F,I H,J,K L G 四、算法设计题 1．已知有向图有n个顶点,请写算法,根据用户输入的偶对建立该有向图的邻接表。即接受用户输入的 2．设已给出图的邻接矩阵，要求将邻接矩阵转换为邻接表。 3．已知无向图采用邻接表存储方式，试写出删除边（i，j）的算法。 4．假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧） 5．给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。 2 12 1 9 5 6 3 10 4 4 2 6 6 7 3 2 4 6．对于一个使用邻接表存储的有向图G，可以利用深度优先遍历方法，对该图中结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减一，并对其未访问的、入度为0的邻接到的顶点进行递归。 （1）．给出完成上述功能的图的邻接表定义（结构）。 （2）．定义在算法中使用的全局辅助数组。 （3）．写出在遍历图的同时进行拓扑排序的算法。