图6.29 邻接矩
（4）有向网如图6.30所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表6.9。
图6.30 有向网
D 终点 b c 15 (a,b) 2 (a,c) d e f g 12 (a,d) ∞ ∞ ∞ 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) 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 <<1, 3> 0 17 l 0 15 0 19 15 <3, 2> 15 27 1 ? 15 37 <2, 4> 19 19 2 ? 29 38 <2, 5> 19 27 3 ? 38 43 <3, 5> 15 37 0 <4, 6> 29 38 <5, 6> 38 4 ? 43 5 ? 6 1, 2> e l 0 -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均为有向无权图,其余情况容易由此写出 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++; }
return OK;
}//Insert_Arc
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]; //将待删除顶点交换到最后一个顶点 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 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 //为节省篇幅,本题只给出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=(ArcNode*)malloc(sizeof(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出发的深度优先遍历的非递归过程。 数据结构考研指导232页7.3.7 （3）设计一个算法，求图G中距离顶点v的最短路径长度最大的一个顶点，设v可达其余各个顶点。 数据结构考研指导232页7.3.8 （4）试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。 解1： int visited[MAXSIZE]; //指示顶点是否在当前路径上 int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j 是否有路径,是则返回1,否则返回0 { if(i==j) return 1; //i就是j else { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径 }//for }//else }//exist_path_DFS 解2：（以上算法似乎有问题：如果不存在路径，则原程序不能返回0。我的解决方式是在原程序的中引入一变量level来控制递归进行的层数。具体的方法我在程序中用红色标记出来了。） int visited[MAXSIZE]; //指示顶点是否在当前路径上 int level＝1;//递归进行的层数 int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j 是否有路径,是则返回1,否则返回0 { if(i==j) return 1; //i就是j else { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc，level--) { level++; k=p->adjvex; if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径 }//for }//else if (level==1) return 0; }//exist_path_DFS （5）采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为为k的简单路径。 （注1：一条路径为简单路径指的是其顶点序列中不含有重现的顶点。 注2：此题可参见严题集P207-208中有关按“路径”遍历的算法基本框架。） int visited[MAXSIZE]; int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G 的顶点i到j是否存在长度为k的简单路径 { { if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求 else if(k>0) { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { l=p->adjvex; if(!visited[l]) if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一 }//for visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else return 0; //没找到 }//exist_path_len