数据结构课程设计-拓扑排序和关键路径

.专业整理.ABSTRACT1.1图和栈的结构定义structSqStack////栈部分{SElemType*base;//栈底指针SElemType*top;//栈顶指针intstacksize;//栈的大小intelement_count;//栈中元素个素};/////////AOE网的存储结构structArcNode//表结点{intlastcompletetime;//活动最晚开始时间intadjvex;//点结点位置intinfo;//所对应的弧的权值structArcNode*next;//指向下一个表结点指针};structVNode//点结点{VertexTypedata;//结点标志intindegree;//该结点入度数intve;//记录结点的最早开始时间intvl;//记录结点的最晚开始时间structArcNode*first_out_arc;//存储下一个出度的表结点structArcNode*first_in_arc;//存储下一个入度的表结点.学习帮手..专业整理.};structALGraph{VNode*vertices;//结点数组intvexnum;//结点数intarcnum;//弧数intkind;//该图的类型};系统总分析2.1关键路径概念分析2.1.1什么是关键路径关键路径法(CriticalPathMethod,CPM)最早出现于20世纪50年代，它是通过分析项目过程中哪个活动序列进度安排的总时差最少来预测项目工期的网络分析。这种方法产生的背景是，在当时出现了许多庞大而复杂的科研和工程项目，这些项目常常需要运用大量的人力、物力和财力，因此如何合理而有效地对这些项目进行组织，在有限资源下以最短的时间和最低的成本费用下完成整个项目就成为一个突出的问题，这样CPM就应运而生了。对于一个项目而言，只有项目网络中最长的或耗时最多的活动完成之后，项目才能结束，这条最长的活动路线就叫关键路径（CriticalPath），组成关键路径的活动称为关键活动。.学习帮手..专业整理.2.1.2关键路径特点关键路径上的活动持续时间决定了项目的工期，关键路径上所有活动的持续时间总和就是项目的工期。关键路径上的任何一个活动都是关键活动，其中任何一个活动的延迟都会导致整个项目完工时间的延迟。关键路径上的耗时是可以完工的最短时间量，若缩短关键路径的总耗时，会缩短项目工期；反之，则会延长整个项目的总工期。但是如果缩短非关键路径上的各个活动所需要的时间，也不至于影响工程的完工时间。关键路径上活动是总时差最小的活动，改变其中某个活动的耗时，可能使关键路径发生变化。可以存在多条关键路径，它们各自的时间总量肯定相等，即可完工的总工期。关键路径是相对的，也可以是变化的。在采取一定的技术组织措施之后，关键路径有可能变为非关键路径，而非关键路径也有可能变为关键路径。2.2关键路径实现过程2.2.1结构选取首先要选取建图的一种算法建立图，有邻接矩阵，邻接表，十字链表，邻接多重表等多种方法，要选取一种适当的方法建立图，才能提高算法效率，降低时间复杂度和空间复杂度。两个相邻顶点与它们之间的边表示活动，边上的数字表示活动延续的时间。对于给出的事件AOE网络，要求求出从起点到终点的所有路径，经分析、比较后找出长读最大的路径，从而得出求关键路径的算法，并给出计算机上机实现的源程序。完成不同路径的活动所需的时间虽然不.学习帮手..专业整理.同，但只有各条路径上所有活动都完成了，这个工程才算完成。2.2.2具体要解决的问题（1）将项目中的各项活动视为有一个时间属性的结点，从项目起点到终点进行排列；（2）用有方向的线段标出各结点的紧前活动和紧后活动的关系，使之成为一个有方向的网络图；3）用正推法和逆推法计算出各个活动的最早开始时间，最晚开始时间，最早完工时间和最迟完工时间，并计算出各个活动的时差；（4）找出所有时差为零的活动所组成的路线，即为关键路径；（5）识别出准关键路径，为网络优化提供约束条件；2.3算法分析（1）求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；（2）只有缩短关键活动的工期才有可能缩短工；期（3）若一个关键活动不在所有的关键路径上，减少它并不能减少工期；（4）只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。（5）关键路径：从源点到汇点的路径长度最长的路径叫关键路。径（6）活动的最早开始时间e(i)；（7）活动的最晚开始时间l(i)；（8）定义e(i)=l(i)的活动叫关键活动；（9）事件的最早开始时间ve(i)；（10）事件的最晚开始时间vl(i)。设活动ai由弧<j,k>(即从顶点j到k)表示，其持续时间记为dut(<j,k>),则：e(i)=ve(j)l(i)=vl(k)-dut(<j,k>).学习帮手..专业整理.ve(i)和vl(j)分两步：1.从ve(1)=0开始向前递推ve(j)=Max{ve(i)+dut(<i,j>)}<i,j>T,2<=j<=n其中，T是所有以j为弧头的弧的集合。2.从vl(n)=ve(n)开始向后递推vl(i)=Min{vl(j)-dut(<i,j>)}<i,j>S,1<=i<=n-1其中，S是所有以i为弧尾的弧的集合。两个公式是在拓扑有序和逆拓扑有序的前提下进行。2.2.4算法步骤（1）输入e条弧<j,k>，建立AOE网的存储结构。（2）从源点v1出发，令ve(1)=0,求个点的最早开始时间ve(j)。（3）从汇点vn出发，令vl(n)=最大值，求个点的最晚开始时间vl(j)。（4）由于各结点的最早开始时间已求出来，所以各活动的最早开始时间即（每条弧s（活动）的最早开始时间）就等于该结点的最早开始时间，并由上可同时求出该活动的最晚开始时间l(j)。（5）具体表达式为：e(i)=ve(j)l(i)=vl(k)-dut(<j,k>)（6）当结点的最早开始时间ve(j)=最晚开始时间时vl(j)，则该结点为关键结点。（7）当活动的最早开始时间e(j)=最晚开始时间时l(j)，则该结点为关键活动。.学习帮手..专业整理.主要功能模块设计3.1程序模块栈部分模块StatusInitStack(SqStack&S)//初始化栈StatusDestroyStack(SqStack&S)//销毁栈StatusClearStack(SqStack&S)//清空栈StatusStackEmpty(SqStackS)//判断是否为空StatusStackEmpty(SqStackS)//判断是否为空StatusPop(SqStack&S,SElemType&e)//弹出元素StatusGetElement(SqStack&S,intposition,SElemType&e)//取元素，非弹出,i为要去元素位置无向图（AOE网）部分模块voidCreateALGraph(ALGraph&graph)//初始化AOE网StatusTopologicalSort(ALGraph&graph,SqStack&ToPoReverseSort)//求拓扑排序StatusPutInfoToPoSort(SqStacktemp,ALGraphgraph)//输出拓扑顺序排序(当拓扑序列存在时）StatusGetVeAndVl(ALGraph&graph,SqStackOrderSort,SqStackRevSort)//求出结点和活动的最晚开始时间和最早开始时间StatusCriticalPath(ALGraph&graph,SqStackRevSort)//求出关键活动和关键事件并输出.学习帮手..专业整理.系统详细设计4.1主函数模块main函数首先调用SqStackToPoSort;SqStackToPoReverseSort;函数来定义栈，调用InitStack(ToPoSort);来初始化存拓扑排序的栈和InitStack(ToPoReverseSort);来初始化逆拓扑排序的栈。其次调用CreateALGraph(ALGraph&graph)函数定义和初始化AOE网，调TopologicalSort(ALGraph&graph,SqStack&ToPoReverseSort)函数求拓扑序列和调用PutInfoToPoSort(ToPoSort,graph);函数来输出输出拓扑顺序排序。然后调用GetVeAndVl(graph,ToPoSort,ToPoReverseSort)函数求结点和活动的最晚开始时间、最早开始时间并输出。最后调用StatusCriticalPath(ALGraph&graph,SqStackRevSort)函数来求关键活动、关键事件并输出。求关键活动、关键事件模块调用5输出模块调用6

求结点和活动的最晚最早开始时间模块调用4求拓扑序列模块调用3Main模块调用2初始化模块调用1（初始化AOE网）栈模块（存储顺序拓扑序列和逆序拓扑序列）4.2初始化模块.学习帮手..专业整理.初始化模块用来初始化图，要求用户自己输入数据，并程序构造AOE网。本程序是用自己改进的邻接表来构造AOE网。见图2-4-2提示输入结点数和图类型并生成邻接表graph.vertices=(VNode*)malloc((graph.vexnum+1)*sizeof(VNode));初始化所以结点的信息for(i=0;i<=graph.vexnum;i++)输出提示用户按一定格式输入是否符合格 N式Y构造出度的表结构并初始化构造入度的表结构并初始化退出图2-4-2

保留入度度数初始化栈 S并压入度数为零的结点判断栈S是 Y否为空N弹出栈S中元素并用栈ToPoReverseSort存放拓扑逆序序列检查当删除结点时，其入度是否唯一for(p=((graph.vertices+i)->first_out_arc);p;p=p->next N)销毁栈S还原入度数并退出图2-4-3.学习帮手..专业整理.4.3求拓扑序列模块利用栈来存储入度为零的结点，然后逐个弹出，来进行与该结点的出度结点来比较，是否符合拓扑排序的规则，最后用ToPoReverseSort存放拓扑逆序序列来完成整个拓扑排序。见图2-4-34.4求最晚开始时间和最早开始时间模块（包括结点和活动的最早和最晚开始时间）见图2-4-4.学习帮手..专业整理.用拓扑排序顺序栈OrderSort和逆序利用顺序栈栈OrderSort逐渐将元素弹出进入双循环判断ve（当 N前)+权值>对应Y将ve+权值赋进入下值给对应的次循环出度点的最早开始时间退出双循环

拓扑序列最后结点：ve=vl利用逆序栈RevSort弹出拓扑序列最后一个元素利用逆序栈RevSort逐渐将元N素弹出进入双循环将ve-权值赋值给活动的最晚开始时间N判断ve（当前)-权值<对应入度点的veY将ve-权值赋值给对应的进入下入度点的最次循环晚开始时间退出双循环图2-4-4.学习帮手..专业整理.4.5关键活动和关键事件见图2-4-5用拓扑排序顺序栈OrderSort作为输入参数

判断活动的最早开始时间是否等于最晚开始时间判断结点ve=vl？

Y NN 为关键活动并输出该活动Y循环直到为关键事件结束并输出该结点程序结循环直到束结束图2-4-54.6输出模块输出相应结点的信息，拓扑序列，以及事件的最早开始时间和最晚开始时.学习帮手..专业整理.间，输出相应的活动的最早开始时间和最晚开始时间，关键活动以及关键事件。测试分析5.1测试内容求的关键路径为：.学习帮手..专业整理.程序输入部分：求拓扑序列部分.学习帮手..专业整理.求结点和活动的最早开始时间和最晚开始时间输出图中的关键事件和关键活动（关键路径）.学习帮手..专业整理.测试关键路径结果：.学习帮手..专业整理.5.2回路测试.学习帮手..专业整理.结果分析：结果完全符合所求，但是输出的方面不够完美，并且自我感觉程序所使用的空间比较大，算法复杂度较高，所以效率比较低下，当程序输入存在有环的时候，程序没有发生任何错误，直接输出“图存在有环”然后退出程序。由此可见本程序计划实施到完工比较顺利的完成了，并且在程序测试中能够得到预期的结果出来，不过唯一不满意的是程序过于复杂化，使用的太多的空间，致使程序成为一个缺陷。.学习帮手..专业整理.参考文献[1]严蔚敏，吴伟民.数据结构.北京：清华大学出版社，2006.[2]谭浩强.C程序设计（第二版）作者：清华大学出版社，2006.学习帮手..专业整理.心得体会经历几天的编程之后，课程设计终于结束了。一开始整个程序不知道怎么开始，而且算法是怎么样的都不知道，不过经过一番的查书、翻阅资料、上网查找之后终于了解到整个算法流程以及实现，首先，关键路径的实现是用邻接表来存储的，对于这个来说，本人觉得单纯按照书本的邻接表来做不太合适，于是就自己改进了一个邻接表，加上在结点里加上存储入度的变量，和加上指向所以入度的表的指针。并且在表结构上加上入度表结构。由于搜集了很多关于关键路径的资料，包括几种不同思路的程序代码，以及程序流程。然后看懂并整理这些代码，然后再其基础上增加自己需要的功能，按照自己的意愿来修改与完善。在程序输入部分采用结点，结点，弧（即结点和结点之间的权值），由于输入贯穿整个程序部分，所以输入部分十分重要。之后创建整个程序的结构，其中包括入度和出度的表结点，这两个都依附在结点结构之上。在程序求关键路径的时候，首先必须要求出整个图的拓扑排序，并用栈来保存起来，然后并在主函数里定义了两个栈，分别来存储顺序拓扑排序和逆序拓扑排序，其中在求拓扑排序的时候就遇到了一个问题就是结点存储的度数发生变化了，这个问题在后来的时候才发现的，因为之后还需要用到入度数，由.学习帮手..专业整理.此，在求拓扑序列的时候必须把入度数先用一个数组来存起来，然后求完拓扑序列之后必须把整个结点的入度数还原。/////////保留入度度数/////////////int*indegree_copy=(int*)malloc(sizeof(int)*graph.vexnum);for(i=0;i<graph.vexnum;i++){*(indegree_copy+i)=(graph.vertices+i+1)->indegree;}//////////////////////////////////////////还原入度度数/////////////for(i=0;i<graph.vexnum;i++){(graph.vertices+i+1)->indegree=*(indegree_copy+i);}/////////////////////////////////最后按照拓扑的顺序序列求出结点的最早开始时间，但是源结点的最早开始时间必须赋予一定的值，所以按照顺序的拓扑序列并且还可以求出活动的最早开始时间。再次，按照逆序拓扑序列来求出结点和活动的最晚开始时间。然后根据算法就可以轻易的求出关键路径和关键事件。其中在编译过程中出现了一个编译的异常，上网找了一下，说是指针越界了，于是，再设断点等手段经过长时间的摸索之后就发现了原来是程序中的栈的部分出问题了，由于之前都没有过栈出问题的情况，于是就改变了一下这个.学习帮手..专业整理.问题就没出现过了。教师评语.学习帮手..专业整理..学习帮手..专业整理.附录程序源代码：关键路径.cpp:定义控制台应用程序的入口点。#include"stdafx.h"#include<stdio.h>#include<stdlib.h>#defineVertexTypeint/////////栈部分#defineSTACK_ADDITIONsizeof(SElemType)#defineSElemTypeint#defineOKtrue#defineERRORfalse#defineStatusboolstructSqStack{.学习帮手..专业整理.SElemType*base;SElemType*top;intstacksize;intelement_count;//元素个素};StatusInitStack(SqStack&S)//初始化栈{S.base=(SElemType*)malloc(STACK_ADDITION);S.stacksize=STACK_ADDITION;S.element_count=0;if(S.base==NULL){printf("mallocerror\n");exit(0);}else{S.top=S.base;}returnOK;}StatusDestroyStack(SqStack&S)//销毁栈.学习帮手..专业整理.{if(S.base==NULL){printf("Stackisnotexistent\n");}else{delete(S.base);}returnOK;}StatusClearStack(SqStack&S)//清空栈{if(S.base==NULL){printf("Stackisnotexistent\n");}elseif(S.base==S.top){printf("SackisNULL\n");}else.学习帮手..专业整理.{S.top=S.base;S.element_count=0;}returnOK;}StatusStackEmpty(SqStackS)//判断是否为空{if(S.base==NULL){printf("Stackisnotexistent\n");returnfalse;}if(S.top==S.base){returntrue;}else{returnfalse;}}.学习帮手..专业整理.StatusPush(SqStack&S,SElemTypee)//增加元素{SElemType*temp1=S.base;SElemType*temp2=S.top;if(S.stacksize-(S.element_count*STACK_ADDITION)==STACK_ADDITION){S.base = (SElemType*)realloc(S.base,(S.stacksize+STACK_ADDITION));S.stacksize+=STACK_ADDITION;S.top=S.base+(temp2-temp1);*S.top=e;S.top=S.top+1;S.element_count++;}else{*S.top=e;S.top=S.top+1;S.element_count++;}returnOK;}.学习帮手..专业整理.StatusPop(SqStack&S,SElemType&e)//弹出元素{if(S.top==S.base){printf("Stackisnull!Poperror!\n");returnfalse;}else{e=*--S.top;S.element_count--;returnOK;}}intStackLength(SqStackS){returnS.element_count;}StatusGetElement(SqStack&S,intposition,SElemType&e)//取元素，非弹出,i为要去元素位置{SElemType*temp;.学习帮手..专业整理.temp=S.top;if(S.top==S.base){printf("Stackisnull!GetElementerror!\n");returnfalse;}elseif(position<=S.element_count){e=*(temp-position);returnOK;}else{printf("error!由于输入位置比栈元素数目大");returnfalse;}}//===================================================================structArcNode//表结点{intlastcompletetime;//活动最晚完成时间intadjvex;//点结点位置.学习帮手..专业整理.intinfo;//所对应的弧的权值structArcNode*next;//下一个表结点};structVNode//点结点{VertexTypedata;//标志intindegree;//该结点入度数intve;//记录最早开始时间intvl;//记录最晚开始时间structArcNode*first_out_arc;//存储下一个出度的表结点structArcNode*first_in_arc;//存储下一个入度的表结点};structALGraph{VNode*vertices;//结点数组intvexnum;//结点数intarcnum;//弧数intkind;//该图的类型};voidCreateALGraph(ALGraph&graph){inttemp1=1;.学习帮手..专业整理.inttemp2=0;inttemp3=0;//权inti=0;structArcNode*arc1=NULL;structArcNode*arc2=NULL;printf("请输入结点数(结点由1开始）和图的类型：\n");scanf("%d%d",&graph.vexnum,&graph.kind);graph.vertices=(VNode*)malloc((graph.vexnum+1)*sizeof(VNode));for(i=0;i<=graph.vexnum;i++){(graph.vertices+i)->data=i;(graph.vertices+i)->first_in_arc=NULL;(graph.vertices+i)->first_out_arc=NULL;(graph.vertices+i)->ve=0;(graph.vertices+i)->vl=0;(graph.vertices+i)->indegree=0;}printf("请输入(格式：点，点，两点之间的权值\n");graph.arcnum=-1;while(!(temp1==0&&temp2==0&&temp3==0)){graph.arcnum++;//图的弧数.学习帮手..专业整理.scanf("%d%d%d",&temp1,&temp2,&temp3);((graph.vertices+temp2)->indegree)++;if((graph.vertices+temp2)->first_in_arc==NULL){(graph.vertices+temp2)->first_in_arc=(ArcNode*)malloc(sizeof(ArcNode));(graph.vertices+temp2)->first_in_arc->adjvex=temp1;(graph.vertices+temp2)->first_in_arc->info=temp3;(graph.vertices+temp2)->first_in_arc->lastcompletetime=0;//活动最晚完成时间初始化(graph.vertices+temp2)->first_in_arc->next=NULL;}else{arc2=(graph.vertices+temp2)->first_in_arc;while(arc2->next!=NULL)//如果下一个不为空的话就存储下一个地址{arc2=arc2->next;}arc2->next=(ArcNode*)malloc(sizeof(ArcNode));.学习帮手..专业整理.arc2->next->adjvex=temp1;arc2->lastcompletetime=0;//活动最晚完成时间初始化arc2->next->info=temp3;arc2->next->next=NULL;}//========================================================if((graph.vertices+temp1)->first_out_arc==NULL){(graph.vertices+temp1)->first_out_arc=(ArcNode*)malloc(sizeof(ArcNode));(graph.vertices+temp1)->first_out_arc->adjvex=temp2;(graph.vertices+temp1)->first_out_arc->info=temp3;(graph.vertices+temp1)->first_out_arc->lastcompletetime=0;//活动最晚完成时间初始化(graph.vertices+temp1)->first_out_arc->next=NULL;}else{arc1=(graph.vertices+temp1)->first_out_arc;while(arc1->next!=NULL)//如果下一个不为空的话就存储下一个地址.学习帮手..专业整理.{arc1=arc1->next;}arc1->next=(ArcNode*)malloc(sizeof(ArcNode));arc1->next->adjvex=temp2;arc1->next->info=temp3;arc1->next->lastcompletetime=0;//活动最晚完成时间初始化arc1->next->next=NULL;}}}//求拓扑排序StatusTopologicalSort(ALGraph&graph,SqStack&ToPoReverseSort){SqStackS;structArcNode*p=NULL;intk=0;inti=0;intcounter;//计算拓扑序列的个数.学习帮手..专业整理./////////保留入度度数/////////////int*indegree_copy=(int*)malloc(sizeof(int)*graph.vexnum);for(i=0;i<graph.vexnum;i++){*(indegree_copy+i)=(graph.vertices+i+1)->indegree;}/////////////////////////////////if(!InitStack(S))printf("初始化栈失败");for(i=1;i<=graph.vexnum;i++){if(!((graph.vertices+i)->indegree))Push(S,i);}counter=0;i=0;while(!StackEmpty(S)){Pop(S,i);Push(ToPoReverseSort,i);//用栈ToPoReverseSort存放拓扑逆序序列.学习帮手..专业整理.counter++;for(p=((graph.vertices+i)->first_out_arc);p;p=p->next){k=p->adjvex;if(!(--((graph.vertices+k)->indegree)))Push(S,k);}}DestroyStack(S);/////////还原入度度数/////////////for(i=0;i<graph.vexnum;i++){(graph.vertices+i+1)->indegree=*(indegree_copy+i);}/////////////////////////////////if(counter<graph.vexnum)returnERROR;elsereturnOK;.学习帮手..专业整理.}//输出拓扑顺序排序(当拓扑序列存在时）StatusPutInfoToPoSort(SqStacktemp,ALGraphgraph){SElemTypee=0;intj=temp.element_count;for(inti=1;i<=j;i++){Pop(temp,e);printf("该结点为V%d：数组下标为：%d\n",(graph.vertices+e)->data,e);}returnOK;}//求出结点和活动的最晚开始时间和最早开始时间StatusGetVeAndVl(ALGraph&graph,SqStackOrderSort,SqStackRevSort){inti=0,j=0;intkk=0;structArcNode*p=NULL;.学习帮手..专业整理.SElemTypee1;SElemTypee2;//////////求出所有结点的最早开始时间//////////////Pop(OrderSort,e1);(graph.vertices+e1)->ve=1;kk=OrderSort.element_count;for(i=1;i<=kk;i++){Pop(OrderSort,e2);for(j=1,p=((graph.vertices+e2)->first_in_arc);j<=(graph.vertices+e2)->indegree;j++,p=p->next){if((graph.vertices+e2)->ve<(graph.vertices+p->adjvex)->ve+p->info){(graph.vertices+e2)->ve=(graph.vertices+p->adjvex)->ve+p->info;}}}.学习帮手..专业整理.//////////求出所有结点的最晚开始时间//////////////Pop(RevSort,e1);//弹出拓扑序列最后一个元素for(i=1;i<=graph.vexnum;i++)(graph.vertices+i)->vl=2147483647;(graph.vertices+e1)->vl=(graph.vertices+e1)->ve;//最晚开始时间=最早开始时间kk=RevSort.element_count;for(i=1;i<=kk;i++){Pop(RevSort,e2);for(p=((graph.vertices+e2)->first_out_arc);p;p=p->next){p->lastcompletetime=((graph.vertices+p->adjvex)->vl)-(p->info);if((graph.vertices+e2)->vl>((graph.vertices+p->adjvex)->vl)-(p->info)){(graph.vertices+e2)->vl=((graph.vertices+p->adjvex)->vl)-(p->info);}.学习帮手..专业整理.}}///////////////////////////////////////printf("\n\n☆☆☆☆☆☆☆☆☆结点信息☆☆☆☆☆☆☆☆☆\n");printf("结点\t最早开始时间\t最晚开始时间\t入度数\n");for(i=1;i<=graph.vexnum;i++){printf("V%d\t%2d\t\t%2d\t\t%2d\n",(graph.vertices+i)->data,(graph.vertices+i)->ve,(graph.vertices+i)->vl,(graph.vertices+i)->indegree);}printf("\n☆☆☆☆☆☆☆☆☆活动信息☆☆☆☆☆☆☆☆☆\n");printf("活动 最早开始时间 最晚开始时间为\n");for(i=1;i<=graph.vexnum;i++)for(p=((graph.vertices+i)->first_out_arc);p;p=p->next){printf("<V%d,V%d>\t\t%d\t\t%d\n",i,p->adjvex,(graph.ve