关键路径问题.docx
- 文档编号:18463690
- 上传时间:2023-08-18
- 格式:DOCX
- 页数:13
- 大小:77.48KB
关键路径问题.docx
《关键路径问题.docx》由会员分享,可在线阅读,更多相关《关键路径问题.docx(13页珍藏版)》请在冰点文库上搜索。
关键路径问题
《数据结构》课程设计
题目关键路径问题
院系计算机系
年级班级2016计科(嵌入)
学生姓名陈银
学号*********04
学期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*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->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
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开始编号)以及每条边的权重"< intcount=0;//记录初始化边的条数 intstart,end,weight; while(count! =this->edge){ cin>>start>>end>>weight; while(! check_edge_value(start,end,weight)){ cout<<"输入的信息不合法,请重新输入: "< cin>>start>>end>>weight; } GraphNode*temp=newGraphNode; temp->start=start-1; temp->end=end-1; temp->weight=weight; temp->next=NULL; //如果当前顶点的还没有边依附时, ++indegree[temp->end];//对应的弧头的顶点的入度加1 if(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<<"图的邻接表为: "< intcount=0; while(count! =this->apex){ cout< GraphNode*temp=this->arc[count].firstarc; while(temp){ cout<<"<" < <<"," < <<">=" < <<""; temp=temp->next; } cout<<"^"< ++count; } } boolGraph_DG: : topological_sort(){ cout<<"图的拓扑序列为: "< stack GraphNode*temp; inti; for(i=0;i if(! indegree[i])s.push(i);//入度为0,则入栈 } //count用于计算输出的顶点个数 intcount=0; while(! s.empty()){//如果栈为空,退出循环 i=s.top();//i等于栈顶的元素 s.pop(); cout< 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< returntrue; } cout<<"此图有环,无拓扑序列"< returnfalse;//说明这个图有环 } boolGraph_DG: : CriticalPath(){ if(! this->topological_sort()){ cout<<"此图有环,无关键路径"< returnfalse; } cout<<"图的关键路径为: "< //初始化vl的值都为ve[this->vexnum-1] intk; for(k=0;k vl[k]=ve[this->apex-1]; } GraphNode*temp; while(! this->List.empty()){ k=List.top();//从逆拓扑排序开始,求vl List.pop(); temp=this->arc[k].firstarc; while(temp){ //dut //来作为第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 temp=temp=this->arc[k].firstarc; while(temp){ ee=ve[k]; el=vl[temp->end]-temp->weight; if(ee==el){//这两个值相等,说明它为关键活动: cout< <<"----" < <<"=" < < } temp=temp->next; } } } 5关键路径测试 6课程设计总结与体会 课程设计的课题是关键路径问题: 人们不仅需要确定这些活动的先后次序,确定哪些活动是影响工程进度的关键活动,以便合理安排人力,物力,财力,加快这些活动的进程。 7参考文献 [1]《C程序设计(第三版)》,谭浩强,清华大学出版社,2005。 [2]《数据结构》(C语言版),严蔚敏,吴伟民清华大学出版社,2007。 [3]《数据结构题集》,严蔚敏,清华大学出版社,2007。 [4]《c++语言程序设计》郑莉董渊何江舟清华大学出版社2010。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 关键 路径 问题