第6章 图
1．选择题
（1）在一个图中，所有顶点的度数之和等于图的边数的（ ）倍。 A．1/2 B．1 C．2 D．4
（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A．1/2 B．1 C．2 D．4 （3）具有n个顶点的有向图最多有（ ）条边。
A．n B．n(n-1) C．n(n+1) D．n2
（4）n个顶点的连通图用邻接距阵表示时，该距阵至少有（ ）个非零元素。 A．n B．2(n-1) C．n/2 D．n2
（5）G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。 A．7 B．8 C．9 D．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出发按深度优先遍历的结果是
?0?1??1??1?1??0??111110011000010010011101?01??00??10?10??01?10??0011000A．0 2 4 3 1 5 6
B．0 1 3 6 5 4 2 C．0 1 3 4 2 5 6 D．0 3 6 1 5 4 2
（ ）。
图6.25 邻接矩阵
（14）已知图的邻接表如图6.26所示，则从顶点0出发按广度优先遍历的结果是（ ），按深度优先遍历的结果是（ ）。
A．0 1 3 2 B．0 2 3 1
C．0 3 2 1 D．0 1 2 3
图6.26 邻接表
（15）下面（ ）方法可以判断出一个有向图是否有环。
A．深度优先遍历 B．拓扑排序 C．求最短路径 D．求关键路径 2．应用题
（1）已知如图6.27所示的有向图，请给出： ① 每个顶点的入度和出度； ② 邻接矩阵； ③ 邻接表；
④ 逆邻接表。
图6.27 有
（2）已知如图6.28所示的无向网，请给出： ① 邻接矩阵； ② 邻接表； ③ 最小生成树
??43?????? ? 4 ? 5 59?????? ? ? 5 ? ? ? 5 ? 3 5?? ??55?7654???9?7?3??? ????63?2???? ????5?2?6??????54??6??? ? a b c d e f g h → b 4 → c 3 → a 4 → c 5 → a 3 → b 5 → b 5 → c 5 → b 9 → d 7 → d 6 → e 3 → d 5 → f 2 → c 5 → d 4
5 5 7 3 2 6 6
→ d → d → e → f → g → h → g → e → h → f ^ ^ ^ ^
9 ^ 5 ^
图6.28 无
6 → g 5 → h 4^
（3）已知图的邻接矩阵如6.29所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
图6.29 邻接矩
（4）有向网如图6.30所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短
路径，完成表6.9。
图6.30 有向网
D 终点 b c d e f 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} 15 (a,b) 2 (a,c) 12 (a,d) ∞ ∞ ∞ 15 (a,b) 12 (a,d) 10 (a,c,e) 6 (a,c,f) ∞ 15 (a,b) 11 (a,c,f,d) 10 (a,c,e) 16 (a,c,f,g) 15 (a,b) 11 (a,c,f,d) 16 (a,c,f,g) 15 (a,b) 14 (a,c,f,d,g) 15 (a,b) i=1 i=2 i=3 i=4 i=5 i=6
（5）试对图6.31所示的AOE-网： ① 求这个工程最早可能在什么时间结束；
② 求每个活动的最早开始时间和最迟开始时间；
③ 确定哪些活动是关键活动
图6.31 AOE-网
【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l - e = 0? 来确定关键活动，从而确定关键路径。
Ve Vl 0 19 e l l-e 17 17 0 0 0 0 <1, 2> 0 15 8 <1, 3> 15 27 0 0 19 15 <3, 2> 19 19 12 1 15 37 <2, 4> 19 27 8 2 29 38 <2, 5> 15 37 0 3 38 43 <3, 5> 29 38 <4, 6> 38 <5, 6> 4 43 5 6 此工程最早完成时间为43。关键路径为<1, 3><3, 2><2, 5><5, 6>
3．算法设计题
（1）分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作： ① 增添一个新顶点v，InsertVex(G, v)；
② 删除顶点v及其相关的边，DeleteVex(G, v); ③ 增加一条边
//本题中的图G均为有向无权图,其余情况容易由此写出
Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v {
if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE; G.vexs[++G.vexnum]=v; return OK; }//Insert_Vex
Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上插入边(v,w) {
if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(i==j) return ERROR; if(!G.arcs[j].adj) {
G.arcs[j].adj=1; G.arcnum++; }