① ③
?? ?
?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
for(i=0;i G.arcs[m]=G.arcs[n]; G.arcs[m]=G.arcs[n]; //将边的关系随之交换 } G.arcs[m][m].adj=0; G.vexnum--; return OK; }//Delete_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++; } return OK; }//Insert_Arc ④ 删除一条边 Status Delete_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(G.arcs[j].adj) { G.arcs[j].adj=0; G.arcnum--; } return OK; }//Delete_Arc XLIX 以邻接表作为存储结构，本题只给出Insert_Arc算法.其余算法类似。 Status Insert_Arc(ALGraph &G,char v,char w)//在邻接表表示的图G上插入边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; p=new ArcNode; p->adjvex=j;p->nextarc=NULL; if(!G.vertices.firstarc) G.vertices.firstarc=p; else { for(q=G.vertices.firstarc;q->q->nextarc;q=q->nextarc) if(q->adjvex==j) return ERROR; //边已经存在 q->nextarc=p; } G.arcnum++; return OK; }//Insert_Arc （2）一个连通图采用邻接表作为存储结构，设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。 [算法描述] Void DFSn(Graph G,int v) { //从第v个顶点出发非递归实现深度优先遍历图G Stack s; SetEmpty(s); Push(s,v); While(!StackEmpty(s)) { //栈空时第v个顶点所在的连通分量已遍历完 Pop(s,k); If(!visited[k]) { { } L visited[k]=TRUE; VisitFunc(k); //访问第k个顶点 //将第k个顶点的所有邻接点进栈 if(!visited[w]&&w!=GetTop(s)) Push(s,w); //图中有环时w==GetTop(s) for(w=FirstAdjVex(G,k);w;w=NextAdjVex(G,k,w))