| 查看: 342 | 回复: 3 | |||
| 当前主题已经存档。 | |||
yaojinling金虫 (正式写手)
|
[交流]
数据结构中关键路径算法的实现与应用
|
||
|
摘 要 介绍求关键路经的算法，对于给出的事件结点网络，要求求出从起点到终点的所有路径，经分析、比较后找出长读最大的路径，从而得出求关键路径的算法，并给出计算机上机实现的源程序。 关键词 关键路径 最少时间 1：引言 通常把计划、施工过程、生产流程、程序流程的都当成一个工程。除了很小的工程外、一般都把工程分为若干个叫做“活动”的子工程。完成了这些“活动”的子工程，这个工程就可以完成了。 通常我们用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边 AOE网络在某些工程估算方面非常有用。他可以使人们了解： （1）：研究某个工程至少需要多少时间？ （2）：那些活动是影响工程进度的关键？ 在AOE网络中，有些活动可以并行的进行。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度就叫做关键路径（critical path）。 2：设计步骤： 1: 以某一工程为蓝本，采用图的结构表示实际的工程计划的时间。 2: 调查以分析和预测这个工程计划个阶段的时间。 3: 用调查的结果建立ＡＯE网（Activity On Edge Network），即边表示活动的网络，并用图的形式表示。 4: 用图来存储这些信息。 5: 用CreateGraphic();函数建立AOE图。 6: 用SearchMapPath();函数求出最大路径，并打印出关键路径。 7:编写代码 8: 测试 3: 设计代码： #include #include #include #include //#define PROJECTNUMBER 9//10 //#define PLANNUMBER 11//13 typedef struct node { int adjvex; int dut; struct node *next; }edgenode; typedef struct { int projectname; int id; edgenode *link; }vexnode; //vexnode Graphicmap[PROJECTNUMBER]; void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber) { int begin,end,duttem; edgenode *p; for(int i=0;i Graphicmap.projectname=i; Graphicmap.id =0; Graphicmap.link =NULL; } printf("某项目的开始到结束在图中的节点输入  ;printf("如：3,4,9 回车表示第三节点到第四节点之间的活动用了9个单位时间\n" ;for(int k=0;k scanf("%d,%d,%d",&begin,&end,&duttem); p=(edgenode*)malloc(sizeof(edgenode)); p->adjvex =end-1; p->dut =duttem; Graphicmap[end-1].id ++; p->next =Graphicmap[begin-1].link ; Graphicmap[begin-1].link =p; } } int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int& totaltime) { int i,j,k,m=0; int front=-1,rear=-1; int* topologystack=(int*)malloc(projectnumber*sizeof(int));//用来保存拓扑排列 int* vl=(int*)malloc(projectnumber*sizeof(int));//用来表示在不推迟整个工程的前提下，VJ允许最迟发生的时间 int* ve=(int*)malloc(projectnumber*sizeof(int));//用来表示Vj最早发生时间 int* l=(int*)malloc(activenumber*sizeof(int));//用来表示活动Ai最迟完成开始时间 int* e=(int*)malloc(activenumber*sizeof(int));//表示活动最早开始时间 edgenode *p; totaltime=0; for(i=0;i for(i=0;i if(Graphicmap.id==0) { topologystack[++rear]=i; m++; } } while(front!=rear) { front++; j=topologystack[front]; m++; p=Graphicmap[j].link ; while(p) { k=p->adjvex ; Graphicmap[k].id --; if(ve[j]+p->dut >ve[k]) ve[k]=ve[j]+p->dut ; if(Graphicmap[k].id ==0) topologystack[++rear]=k; p=p->next ; } } if(m printf("\n本程序所建立的图有回路不可计算出关键路径\n" ;printf("将退出本程序\n" ;return 0; } totaltime=ve[projectnumber-1]; for(i=0;i for(i=projectnumber-2;i>=0;i--) { j=topologystack; p=Graphicmap[j].link ; while(p) { k=p->adjvex ; if((vl[k]-p->dut ) p=p->next ; } } i=0; printf("| 起点 | 终点 | 最早开始时间 | 最迟完成时间 | 差值 | 备注 |\n" ;for(j=0;j p=Graphicmap[j].link; while(p) { k=p->adjvex ; e[++i]=ve[j]; l=vl[k]-p->dut; printf("| %4d | %4d | %4d | %4d | %4d |",Graphicmap[j].projectname +1,Graphicmap[k].projectname +1,e,l,l-e); if(l==e) printf(" 关键活动 |" ;printf("\n" ;p=p->next ; } } return 1; } void seekkeyroot() { int projectnumber,activenumber,totaltime=0; system("cls" ;printf("请输入这个工程的化成图形的节点数:" ;scanf("%d",&projectnumber); printf("请输入这个工程的活动个数:" ;scanf("%d",&activenumber); vexnode* Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode)); CreateGraphic(Graphicmap,projectnumber,activenumber); SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime); printf("整个工程所用的最短时间为：%d个单位时间\n",totaltime); system("pause" ;} int main() { char ch; for(; { do { system("cls" ;printf("| 欢迎进入求关键路径算法程序 |" ;for(int i=0;i<80;i++)printf("*" ;printf("%s","(S)tart开始输入工程的节点数据并求出关键路径\n" ;printf("%s","(E)xit退出\n" ;printf("%s","请输入选择:" ;scanf("%c",&ch); ch=toupper(ch); , ;}while(ch!='S'&&ch!='E'); switch(ch) { case'S': seekkeyroot(); break; case'E': return 1; } } } 4: 总结： 至此，全部的设计过程完毕，上面所有代码已经在VC6.0+Win2000平台下调试成功。从上面的分析可以看出 ,设计结果与预测的相符合. 关键路径在具体的工程中有着重要的作用，当一个AOE网络中的关键路径只有一条时，加速关键路径上的任一关键活动，能够加速整个工程的完成。但当一个AOE网络中的关键路径不止一条时，加速任一关键活动不一定能够加速整个工程的完成。 如方案1与方案2在改变关键路径时整个工程的进度没有改变。 参 考 资 料 [1]谭浩强编著. C程序设计（第二版）.北京：清华大学出版社，2000 [2]严蔚敏，吴伟民编著.数据结构.北京：清华大学出版社，2001 [3]刘正林编著.面向对象程序设计.武汉：华东科技大学出版社，2002 [4]宜 晨编著.Visual C++5.0实用培训教程.北京：电子工业出版社，1998 [ Last edited by sdlwwxb on 2005-12-16 at 17:58 ] |
回复此楼» 猜你喜欢
二次调剂求老师收留
已经有3人回复
-
349学科化学045106求调剂，化学类都可以
已经有5人回复
-
一志愿0807 数一英一 313 有没有二轮调剂
已经有6人回复
-
求调剂，262机械专硕
已经有5人回复
-
286求调剂
已经有15人回复
-
0860004 求调剂 309分
已经有3人回复
-
材料类284调剂
已经有20人回复
-
调剂
已经有11人回复
-
考研调剂-材料类-284
已经有13人回复
-
复试调剂，一志愿郑州大学材料与化工289分
已经有13人回复
yaojinling
金虫 (正式写手)
- 应助: 0 (幼儿园)
- 金币: 896.4
- 散金: 4
- 帖子: 718
- 在线: 10.6小时
- 虫号: 99546
- 注册: 2005-11-11
- 性别: GG
- 专业: 计算机软件
2楼2005-11-18 18:24:25
3楼2005-11-18 18:25:24
imrking
荣誉版主 (著名写手)
- 应助: 17 (小学生)
- 贵宾: 9.05
- 金币: 4827.8
- 散金: 15
- 红花: 1
- 帖子: 2468
- 在线: 125.8小时
- 虫号: 56287
- 注册: 2005-01-06
- 性别: GG
- 专业: 计算机软件
- 管辖: 无机非金属
4楼2005-11-18 19:48:41
