loading
图6.34 邻接矩阵图6.35 有向网
表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.36AOE-网
答案：按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l-e = 0? 来确定关键活动，从而确定关键路径。
1 ? Ve Vl 0 0 <1, 2> e l
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;
48
2 ? 19 19 <1, 3> 0 0 0 3 ? 15 15 <3, 2> 15 15 0 4 ? 29 37 <2, 4> 19 27 8 5 ? 38 38 <2, 5> 19 19 0 <3, 5> 15 27 12 6 ? 43 43 <4, 6> 29 37 8 <5, 6> 38 38 0 0 17 -e 17 此工程最早完成时间为43。关键路径为<1, 3><3, 2><2, 5><5, 6>