关键路径算法课程设计

关键路径算法课程设计内容摘要：

报告 三 详细设计 9 点出发，令事件的最早发生时间为 0，按拓扑有序求其余各顶点时间的最早发生时间 ve[k]； (代码如下 ) If (ve[t] + pinfo ve[k]) ve[k] = ve[t] + pinfo。 // ve[k] k(终点 ) 顶点事件 最早 能发生的时间 ve[] 初始为 0 接着从终点出发，令事件最迟发生时间等于其最早发生时间，按你你逆拓扑排序求其余各顶 点事件最迟发生时间 vl[k]；最后根据各顶点事件的 ve 和 vl 值，求所有活动最早开始时间 ee 和最迟开始时间 el。 如果某活动满足条件 ee＝ el，则为关键活动。 (代码如下 ) if( vl[k] dut vl[t] ) { vl[t] = vl[k] dut。 } // vl[t] t(始点 ) 顶点事件 最迟发生时间 for(int j=1。 j=Gvexnum。 j++) { p=Gvertices[j].firstarc。 while(p) { i++。 int k = padjvex。 ee[i] = ve[j]。 el[i] = vl[k]pinfo。 printf(| %3c | %3c | %6d | %6d | %3d |,Gvertices[j].data, Gvertices[k].data, ee[i], el[i], el[i]ee[i])。 if(el[i]==ee[i]) { printf( 此弧为关键活动 )。 } p=pnextarc。 } } 湖南工学院课程设计报告 三 详细设计 10 同时，为计算各顶点事件的 ve 值是在拓扑排序的过程中进行的，因此需一个 栈 来记录拓扑排序，如果顶点的入度为 0，则该顶点 入栈。 int t = ()； ()。 (t)。 count++。 // 度为 0 的结点出栈 S 入栈 T 栈 T 保存 拓扑序列 cout关键路径所需时间为： ve[Gvexnum]。 主程序建立 该部分主要是对 所建立的函数的调用。 包括 ： 建立图的函数 CreateGraph( )； 计算关键路径的函数 CriticalPath ( )； 最后程序结束。 这样安排可以增强程序的可读性，是程序便于理解，也便于日后的对程序的维护和修改等操作。 四 实 验结果 按照要求输入一组关于 无循环有向帯权图所有信息。 如： 6 1 2 3 4 5 6 8 1 2 30 1 3 20 2 4 20 2 5 30 3 4 40 3 6 30 4 6 20 5 6 10 湖南工学院课程设计报告 三 详细设计 11 依次执行程序每一步，最后结束该程序。 程序运行如下图 ： 湖南工学院课程设计报告 五 程序设计心得 12 五 程序设计心得 通过这次求关键路径，我对图的邻接表有了深刻的了解。 以前都是用邻接矩阵的，感觉邻接矩阵直观 简便，而这次关键路径的有关算法，书上都是使用邻接表的，我试着熟悉它，发现也挺好用的，许多操作用邻接表更方便。 书上没有邻接表的构图代码，拓扑排序，关键路径的都是伪代码，我不得不去查资料，思索，自己编写完整可执行的代码，这个过程很艰辛，也很愉快。 拓扑排序时我想办法弄出了不同拓扑排序的总数，却怎么也无法打印出所有的拓扑序列。 在关键路径求顶点事件最迟的发生时间时，错把各个顶点的最早发生时间赋给了它，所以输出的结果怎么都不对， 我在这个地方纠结的好久。 知识只有在使用的时候才会远远感觉不够用，我深深体会到了这句话。 这次的程序设计对我的帮助很大，虽然真正自己写的代码并不多，许多都是书上的代码经过补充改写的，但毕竟我都把这整个过程走了一遍，熟悉了图的各种操作，各种算法我都认真看懂了，思考了。 我能感觉到自己的进步，每次编写出一个程序，在电脑上运行出来时，都会有一种莫名的成就感，很享受这种感觉，我会继续努力的。 计科 1203 王勋峰 湖南工学院课程设计报告 五 程序设计心得 13 六 参考文献 [1] 严蔚敏 编。 数据结构（ C 语言版）。 北京 : 清华 大学出版社， [2] 谭浩强著。 C 语言程序设计（第二版）。 北京 : 清华大出版社， [3] 武爱平编。 C 语言程序设计。 长春：吉林大学出版社出版， 湖南工学院课程设计报告 附 录 14 七 附录（程序清单） 程序可运行 include iostream using namespace std。 include stack typedef char VertexType。 typedef int VRType。 typedef int InforType。 define MAX_VERTEX_NUM 50 // 最大顶点数 int indegree[MAX_VERTEX_NUM]。 // 存放节点入度数组 int ve[MAX_VERTEX_NUM],vl[MAX_VERTEX_NUM]。 // 顶点事件 最早发生时间 和最迟发生时间数组，全局变量 初始为 0 int ee[MAX_VERTEX_NUM],el[MAX_VERTEX_NUM]。 // 弧活动 最早发生时间 和最迟发生时间数组 stackint S。 // 存放 入度为 0 的结点 stackint T。 // 存放 顶点的拓扑序列 /***********************************************************/ typedef struct ArcNode // 结点 结。