第7章 图
习 题
一、选择题
1、无向图G=(V,E),其中
V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 2、一个n个顶点的连通无向图，其边的个数至少为（ ）。
A．n-1 B．n C．n+1 D．nlogn；
3、在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。
23
A. O(n) B. O(n+e) C. O(n) D. O(n) 4、要连通具有n个顶点的有向图，至少需要（ ）条边。
A．n-l B．n C．n+l D．2n 5、求解最短路径的Floyd算法的时间复杂度为( )。
A．O（n） B. O（n+c） C. O（n*n） D. O（n*n*n）
6、一个有n个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。
A．0 B．1 C．n-1 D．n
7、在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。
A．1/2 B．2 C．1 D．4 8、一个有向无环图的拓扑排序序列（ ）是唯一的。
A．一定 B．不一定 9、关键路径是事件结点网络中（ ）。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 10、下列关于AOE网的叙述中，不正确的是（ ）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成 二、填空题
1、克鲁斯卡尔算法的时间复杂度为______,它对______图较为适合。
2、为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需______存放被访问的结点以实现遍历。
3、具有n个顶点e条边的有向图和无向图用邻接表表示，则邻接表的边结点个数分别为 和 条。
4、在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是______。 5、若n个顶点的连通图是一个环，则它有 棵生成树。
6、N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。
7、有N个顶点的有向图，至少需要量______条弧才能保证是连通的。 8、有向图G可拓扑排序的判别条件是______。
9、若要求一个稠密图的最小生成树，最好用 算法求解。
10、AOV网中,结点表示______,边表示______。AOE网中,结点表示______,边表示______。 三、判断题
1、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。 2、在n个结点的无向图中，若边数大于n-1,则该图必是连通图。
3、在AOE图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。 4、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。 5、在图G的最小生成树G1中，可能会有某条边的权值超过未选边的权值。 6、强连通图的各顶点间均可达。
7、带权的连通无向图的最小代价生成树是唯一的。 8、广度遍历生成树描述了从起点到各顶点的最短路径。 9、邻接多重表是无向图和有向图的链式存储结构。
10、 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。 四、应用题
1.设一有向图为G=(V,E)，其中V={a,b,c,d,e},E={,
2．对n个顶点的无向图G，采用邻接矩阵表示，判别下列有关问题： (1)图中有多少条边？
(2)任意两个顶点i和j是否有边相连？ (3)任意一个顶点的度是多少？ V5 V1 3．如图所示为一个有向图，试给出：
V6 (1)每个顶点的入度和出度
(2)邻接距阵
V2 V4 (3)邻接表 (4)逆邻接表 V3 (5)强连同分量
4．已知一有向图的邻接表如图所示。 (1) 画出该有向图。
(2) 写出从顶点a开始的深度优先和广度优先遍历序列。
(3) 画出从顶点a出发的深度优先和广度优先生成树(或森林)。
3 ? 2 1 a 0
5 ? 1 b c 2 4 ? 3 d 3 5 ? 4 2 5 ? e 4
20 10 10 f 5 3 ? 11 2 6 1 5．(1)画出下图所示图的邻接矩阵表示。
3 3 (2)画出此图的邻接表表示。
5 3 (3)如果每个指针需要4个字节，每个顶点的信息15 占两个字节，每条边的权占2个字节，顶点的下标占1个字节。此图采用哪种表示法所需要的空间较多？
6．对于下面的带权有向图，写出其相邻矩阵表示，并画出其邻接表表示。
v0 6 v1 1 v4 9 v6 1 2 3 5 8 v8 4 v2 v3 2 v5 4 v7
7．给出下图所示图(a)和图(b)，按照下列条件分别写出从顶点v0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 (1)假定它们采用邻接矩阵表示；
(2)假定它们采用邻接表表示，并且假定每个顶点邻接表中的节点是按顶点序号从大到小的次序链接的。 2 1 0 0
4 1 5 6
5 3 4 7 9
8
3 2 6 7 8
8.设有一无向图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)}。
12 (1) 按上述顺序输入后，画出其相应的邻接表。 5 0 15 (2) 在该邻接表上，从顶点4开始，写出DFS序列和BFS
6 8 13 序列。
16 4 1 6 4 9.对于下图：
(1)画出最小生成树并求它的权； 10 920 12 (2)从顶点v0出发，按照Prim算法求出最小生成树时得
5 3 2 到的各边的次序写出各条边；
(3)按照Kruskal算法求出最小生成树时所得到的各边的次序写出各条边。
10．拓扑排序的结构不是唯一的，对下图进行拓扑排序，写出全部不同的拓扑排序序列。 对于下图所示的有向图，试利用Dijkstra算法求源点1到其他各顶点的最短路径，要求给出相应的求解步骤。
1 2 4 7
6 8 5
3 9
11． 试应用Floyd算法求上图所示有向图的各对顶点之间的最短路径，并写出在执行算法过程中所得到的最短路径长度矩阵Ai序列和最短路径矩阵nextvexi序列 五、算法设计题
1．求出一个邻接矩阵表示的图中所有顶点的最大出度数。 2．试在无向图的邻接矩阵和邻接链表上实现如下算法： （1）往图中插入一个顶点； （2）往图中插入一条边； （3）删去图中某顶点； （4）删去图中某条边
3.试以邻接表和邻接矩阵为存储结构，分别写出基于DFS和BFS遍历的算法来判别顶点vi和vj（i<>j）之间是否有路径。
4.试分别写出求DFS和BFS生成树（或生成森林）的算法，要求打印出所有的树边。 5.设图中各边的权值都相等，试以邻接矩阵和邻接表为存储结构，分别写出算法： （1）求顶点vi到顶点vj（i<>j）的最短路径 （2）求源点vi到其余各顶点的最短路径
要求输出路径上的所有顶点（提示：利用BFS遍历的思想）
6.以邻接表为存储结构，写一个基于DFS遍历策略的算法，求图中通过某顶点vk的简单回路（若存在）。
7.利用拓扑排序算法的思想写一算法判别有向图中是否存在有向环，当有向环存在时，输出构成环的顶点。
8.设有向G图有n个点(用1,2,…,n表示),e条边,写一算法根据其邻接表生成其反向邻接表,要求算法复杂性为O(n+e)。