精心整理
②求每个活动的最早开始时间和最迟开始时间； ③确定哪些活动是关键活动
图6.31AOE-网 【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个
活动的最早可能开始时间e和最迟允许开始时间l，根据l-e=0?来确定关键活动，从而确定关键路径。 Ve Vl <1,2> e l 7 l-e 7 0 11<1,3> 0 5 0 5 0 0 17 8 <3,2> 19 29 0 2 <2,4> 19 17 1<2,5> 15 27 8 <3,5> 19 38 0 <4,6> 28 3<5,6> 30 19 15 37 38 43 1? 0 2? 19 3? 15 4? 29 5? 38 6? 43 此工程最早完成时间为43。关键路径为<1,3><3,2><2,5><5,6> 3．算法设计题 （1）分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作： ①增添一个新顶点v，InsertVex(G,v)； ②删除顶点v及其相关的边，DeleteVex(G,v); ③增加一条边
G.arcs[j].adj=1; G.arcnum++; }
returnOK; }//Insert_Arc
StatusDelete_Vex(MGraph&G,charv)//在邻接矩阵表示的图G上删除顶点v {
n=G.vexnum; 精心整理
精心整理
if((m=LocateVex(G,v))<0)returnERROR;
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--; returnOK; }//Delete_Vex 分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加. StatusDelete_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上删除边(v,w) { if((i=LocateVex(G,v))<0)returnERROR; if((j=LocateVex(G,w))<0)returnERROR; if(G.arcs[j].adj) { G.arcs[j].adj=0; G.arcnum--; } returnOK; }//Delete_Arc //为节省篇幅,本题只给出Insert_Arc算法.其余算法请自行写出. StatusInsert_Arc(ALGraph&G,charv,charw)//在邻接表表示的图G上插入边(v,w) { if((i=LocateVex(G,v))<0)returnERROR; if((j=LocateVex(G,w))<0)returnERROR; p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j;p->nextarc=NULL; else { if(q->adjvex==j)returnERROR;//边已经存在 q->nextarc=p; } G.arcnum++; returnOK; }//Insert_Arc （2）一个连通图采用邻接表作为存储结构，设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。 数据结构考研指导232页7.3.7 （3）设计一个算法，求图G中距离顶点v的最短路径长度最大的一个顶点，设v可达其余各个顶点。 数据结构考研指导232页7.3.8 精心整理 精心整理 （4）试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。 解1： intvisited[MAXSIZE];//指示顶点是否在当前路径上 intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j 是否有路径,是则返回1,否则返回0 { if(i==j)return1;//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))return1;//i下游的顶点到j有路径 }//for }//else }//exist_path_DFS 解2：（以上算法似乎有问题：如果不存在路径，则原程序不能返回0。我的解决方式是在原程序的中引入一变量level来控制递归进行的层数。具体的方法我在程序中用红色标记出来了。） intvisited[MAXSIZE];//指示顶点是否在当前路径上 intlevel＝1;//递归进行的层数 intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j 是否有路径,是则返回1,否则返回0 { if(i==j)return1;//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))return1;//i下游的顶点到j有路径 }//for }//else if(level==1)return0; }//exist_path_DFS （5）采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为为k的简单路径。 （注1：一条路径为简单路径指的是其顶点序列中不含有重现的顶点。 注2：此题可参见严题集P207-208中有关按“路径”遍历的算法基本框架。） intvisited[MAXSIZE]; intexist_path_len(ALGraphG,inti,intj,intk)//判断邻接表方式存储的有向图G 的顶点i到j是否存在长度为k的简单路径 精心整理 精心整理 { { if(i==j&&k==0)return1;//找到了一条路径,且长度符合要求 elseif(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))return1;//剩余路径长度减一 }//for visited[i]=0;//本题允许曾经被访问过的结点出现在另一条路径中 }//else return0;//没找到 }//exist_path_len 精心整理