（15）下面（ ）方法可以判断出一个有向图是否有环。
A．深度优先遍历 B．拓扑排序 C．求最短路径 D．求关键路径 答案：B 2．应用题
（1）已知图6.32所示的有向图，请给出： ① 每个顶点的入度和出度； ② 邻接矩阵； ③ 邻接表；
④ 逆邻接表。
答案：
图6.32 有向图 图6.33 无向网
（2）已知如图6.33所示的无向网，请给出： ① 邻接矩阵； ② 邻接表； ③ 最小生成树
答案：
XLV
① ③
?? ?
?4 ? 3 ??? ??? ??? ?????43? ?5559???5???5?7654?97?3????63?2???5?2?6????? 5 ? ?4??????6????? 5 ? 5 ? ? ?
②
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 邻接矩阵
XLVI
表6.9 D 终点 b c d e f g i=1 15 (a,b) 2 (a,c) 12 (a,d) ∞ ∞ ∞ S 终点集 {a,c} 图6.34 邻接矩阵 图6.35 有向网
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} i=6 15 (a,b) {a,c,f} {a,c,f,e} {a,c,f,e,d,g,b}
（5）试对图6.36所示的AOE-网： ① 求这个工程最早可能在什么时
间结束；
② 求每个活动的最早开始时间和
最迟开始时间；
③ 确定哪些活动是关键活动
XLVII
图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]; //将待删除顶点交换到最后一个顶点
XLVIII