关键路径问题

《数据结构》课程设计题目关键路径问题院系计算机系年级班级2016计科（嵌入）学生姓名陈银学号20162375004学期2017-2018（二）任课教师黄群1引言2需求分析2.1问题描述2.2基本要求2.3目的3概要设计3.1数据类型3.2程序流程图4详细设计4.1创建图的函数4.2求关键路径5关键路径测试6课程设计总结与体会7参考文献1引言当一项工程分为多个子工程时，需要确定这么子过程的次序问题，还需要计算整个工程的时间，确定哪些活动是影响工程进度的关键，为按时或者提前完成整个工程提供保证，这就是关键路径的问题。关键路径问题相应的网称为AOE网，其中：顶点表示事件，边表示活动，边得权表示活动持续时间，AOE网可以用来估算工程完成的时间。2需求分析2.1问题描述（1）选择建图方法有:涉及邻接矩阵，邻接表，十字链表，邻接多重等多种方法，要选择一种适当的方法建立图，提高算法效率，降低时间复杂度和空间复杂度。（2）两个相邻顶点与它们之间的边表示活动，边上的数据表示活动延续的时间。对于给出的事件AOE网络。要求求出从起点到终点的所有路径，经分析，比较后找出长读最大的路径，从而得出关键路径的算法，并给出计算机上机实现的源程序。完成不同路径的活动所需时间不同，但路径各条上所有活动都完成，这个工程才算完成。2.2基本要求1选择一种算法建立图：选择邻接表算法，是一种顺序＋链式存储结构。用顺序表存放顶点，为每个顶点建立一个单链表，单链表中的结点表示该顶点的边或以该顶点为尾的弧。2两个相邻顶点与它们之间边表示活动，边上的数字表示活动时间，求出从起点到终点的所有路径，然后通过拓扑排序和逆拓扑排序求出最早与最晚发生时间，找出长度最大的路径，从而求得关键路径。2.3目的通过输入所要构造的图顶点数，弧数，创建图，并打印出来，对图进行拓扑排序，求得此图最早发生时间和最迟发生时间，并求得关键活动和关键路径。3概要设计求关键路径必须在拓扑排序的前提下，有环图不能求关键路径，只能减少关键活动工期，只有在不改变关键路径的前提下，减少关键活动才能减少整个工期。活动最早时间ve(i);最晚时间vi（i）。3.1数据类型structGraphNode{intstart;//弧尾的顶点的下标intend;//弧头的顶点的下标，有箭头的一方intweight;//弧的权重GraphNode*next;//下一条弧};//头结点structPnode{GraphNode*firstarc;//第一条依附在该顶点的弧stringdata;};3.2程序流程图开始开始主函数：求关键主函数：求关键文件输入文件输入求最大路径，打印关键路径结束求最大路径，打印关键路径结束4详细设计4.1创建图的函数classGraph_DG{private:intapex;//顶点个数intedge;//边的条数Pnode*arc;//邻接表int*indegree;//各个顶点的入度情况stack<int>List;//拓扑序列中各个边的情况int*ve;//记录每个顶点的最早发生时间int*vl;//记录每个顶点最迟发生时间public:Graph_DG(intapex,intedge);~Graph_DG();//析构函数boolcheck_edge_value(int,int,int);//检查边的信息是否合法voidcreateGraph();//创建一个新的图voidprint();//打印图的邻接表booltopological_sort();boolCriticalPath();};4.2求关键路径#include"关键路径.h"Graph_DG::Graph_DG(intapex,intedge){/*初始化一些基本的信息，包括边和顶点个数，各个顶点入度数组，邻接表的等*/this->apex=apex;this->edge=edge;this->arc=newPnode[this->apex];this->indegree=newint[this->apex];this->ve=newint[this->apex];this->vl=newint[this->apex];for(inti=0;i<this->apex;i++){this->indegree[i]=0;this->ve[i]=0;this->arc[i].firstarc=NULL;this->arc[i].data="v"+to_string(i+1);}}//释放内存空间Graph_DG::~Graph_DG(){GraphNode*p,*q;for(inti=0;i<this->apex;i++){if(this->arc[i].firstarc){p=this->arc[i].firstarc;while(p){q=p->next;deletep;p=q;}}}delete[]this->arc;delete[]this->indegree;}//判断我们每次输入的的边的信息是否合法//顶点从1开始编号boolGraph_DG::check_edge_value(intstart,intend,intweight){if(start<1||end<1||start>apex||end>apex||weight<0){returnfalse;}returntrue;}voidGraph_DG::createGraph(){cout<<"请输入每条边的起点和终点的编号（顶点从1开始编号）以及每条边的权重"<<endl;intcount=0;//记录初始化边的条数intstart,end,weight;while(count!=this->edge){cin>>start>>end>>weight;while(!check_edge_value(start,end,weight)){cout<<"输入的信息不合法，请重新输入："<<endl;cin>>start>>end>>weight;}GraphNode*temp=newGraphNode;temp->start=start-1;temp->end=end-1;temp->weight=weight;temp->next=NULL;//如果当前顶点的还没有边依附时，++indegree[temp->end];//对应的弧头的顶点的入度加1if(this->arc[start-1].firstarc==NULL){this->arc[start-1].firstarc=temp;}else{GraphNode*now=this->arc[start-1].firstarc;while(now->next){now=now->next;}//找到该链表的最后一个结点now->next=temp;}++count;}}voidGraph_DG::print(){cout<<"图的邻接表为："<<endl;intcount=0;while(count!=this->apex){cout<<this->arc[count].data<<"";GraphNode*temp=this->arc[count].firstarc;while(temp){cout<<"<"<<this->arc[temp->start].data<<","<<this->arc[temp->end].data<<">="<<temp->weight<<"";temp=temp->next;}cout<<"^"<<endl;++count;}}boolGraph_DG::topological_sort(){cout<<"图的拓扑序列为："<<endl;stack<int>s;//保存入度为0的顶点下标GraphNode*temp;inti;for(i=0;i<this->apex;i++){if(!indegree[i])s.push(i);//入度为0，则入栈}//count用于计算输出的顶点个数intcount=0;while(!s.empty()){//如果栈为空，退出循环i=s.top();//i等于栈顶的元素s.pop();cout<<this->arc[i].data<<"";//输出拓扑序列temp=this->arc[i].firstarc;this->List.push(i);while(temp){if(!(--indegree[temp->end])){//如果入度减少到为0，则入栈s.push(temp->end);}//同时更新ve的值if((ve[i]+temp->weight)>ve[temp->end]){ve[temp->end]=ve[i]+temp->weight;}temp=temp->next;}++count;}if(count==this->apex){cout<<endl;returntrue;}cout<<"此图有环，无拓扑序列"<<endl;returnfalse;//说明这个图有环}boolGraph_DG::CriticalPath(){if(!this->topological_sort()){cout<<"此图有环，无关键路径"<<endl;returnfalse;}cout<<"图的关键路径为："<<endl;//初始化vl的值都为ve[this->vexnum-1]intk;for(k=0;k<this->apex;k++){vl[k]=ve[this->apex-1];}GraphNode*temp;while(!this->List.empty()){k=List.top();//从逆拓扑排序开始，求vlList.pop();temp=this->arc[k].firstarc;while(temp){//dut<k,temp->end>，从以第k个顶点为弧尾集合中选择一个最小的值//来作为第i个顶点的最迟发生时间if(vl[k]>(vl[temp->end]-temp->weight)){vl[k]=vl[temp->end]-temp->weight;}temp=temp->next;}}intee;intel;for(k=0;k<this->apex;k++){temp=temp=this->arc[k].firstarc;while(temp