（9）用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。 A．栈 B. 队列 C. 树 D．图 答案：A
解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。 （10）深度优先遍历类似于二叉树的（ ）。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 答案：A
（11）广度优先遍历类似于二叉树的（ ）。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 答案：D
（12）图的BFS生成树的树高比DFS生成树的树高（ ）。
A．小 B．相等 C．小或相等 D．大或相等 答案：C
解释：对于一些特殊的图，比如只有一个顶点的图，其BFS生成树的树高和DFS生
成树的树高相等。一般的图，根据图的BFS生成树和DFS树的算法思想，BFS生成树的树高比DFS生成树的树高小。
（13）已知图的邻接矩阵如图6.30所示，则从顶点v0出发按深度优先遍历的结果是（ ）。
图6.30 邻接矩阵
（14）已知图的邻接表如图6.31所示，则从顶点v0出发按广度优先遍历的结果是（ ），按深度优先遍历的结果是（ ）。
图6.31 邻接表
A．0 1 3 2 答案：D、D
B．0 2 3 1 C．0 3 2 1 D．0 1 2 3
44
（15）下面（ ）方法可以判断出一个有向图是否有环。
A．深度优先遍历 B．拓扑排序 C．求最短路径 D．求关键路径 答案：B 2．应用题
（1）已知图6.32所示的有向图，请给出： ① 每个顶点的入度和出度； ② 邻接矩阵； ③ 邻接表；
④ 逆邻接表。
图6.32 有向图 图6.33 无向网
答案：
（2）已知如图6.33所示的无向网，请给出： ① 邻接矩阵； ② 邻接表； ③ 最小生成树 答案：
45
① ③
?? ?
?4 ? 3 ??? ??? ??? ?????43? ?55 5 ? 5 55?9?7??6??5?54?9 ? 7?3???? ? 63?2??? ? 5?2?6????? 5 ? ?4??????6????? ②
a b c d e f g
→ → → → → → → b a a b b d d 4 4 3 5 9 6 5 → → → → → → → c c b c d e f 3 5 5 5 7 3 2 → → → → → → d d e f g h 5 → e 9 5 → h 5 7 → f 6 → 3 2 6
g 5 →
h 4
（3）已知图的邻接矩阵如图6.34所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
（4）有向网如图6.35所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表6.9。
图6.28 邻接矩阵
46
图6.35 有向网 图6.34 邻接矩阵
表6.9 D 终点 b c d e f g i=1 15 (a,b) 2 (a,c) 12 (a,d) ∞ ∞ ∞ S 终点集 {a,c} {a,c,f} {a,c,f,e} i=2 15 (a,b) 12 (a,d) 10 (a,c,e) 6 (a,c,f) ∞ i=3 15 (a,b) 11 (a,c,f,d) 10 (a,c,e) 16 (a,c,f,g) i=4 15 (a,b) 11 (a,c,f,d) 16 (a,c,f,g) {a,c,f,e,d} i=5 15 (a,b) 14 (a,c,f,d,g) {a,c,f,e,d,g} {a,c,f,e,d,g,b} i=6 15 (a,b)
（5）试对图6.36所示的AOE-网： ① 求这个工程最早可能在什么时
间结束；
② 求每个活动的最早开始时间和
最迟开始时间；
③ 确定哪些活动是关键活动
47
图6.36 AOE-网
答案：按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l - e = 0? 来确定关键活动，从而确定关键路径。
1 ? Ve 0 Vl 0 2 ? 19 19 3 ? 15 15 4 ? 29 37 5 ? 38 38 6 ? 43 43 <5, 6> 38 38 0 <1, 2> <1, 3> <3, 2> <2, 4> <2, 5> <3, 5> <4, 6> e 0 0 15 19 19 15 29 l 17 0 15 27 19 27 37 -e 17 0 0 8 0 12 8 此工程最早完成时间为43。关键路径为<1, 3><3, 2><2, 5><5, 6>
3．算法设计题
（1）分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作： ① 增加一个新顶点v，InsertVex(G, v)； ② 删除顶点v及其相关的边，DeleteVex(G, v); ③ 增加一条边
假设图G为有向无权图，以邻接矩阵作为存储结构四个算法分别如下： ① 增加一个新顶点v
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
② 删除顶点v及其相关的边，
Status Delete_Vex(MGraph &G,char v)//在邻接矩阵表示的图G上删除顶点v {
n=G.vexnum;
if((m=LocateVex(G,v))<0) return ERROR;
G.vexs[m]<->G.vexs[n]; //将待删除顶点交换到最后一个顶点
48