关键路径算法课程设计

1、沈阳航空工业学院 课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计 课程设计题目：实现求关键路径的算法实现求关键路径的算法 院（系）：计算机学院 专 业：计算机科学与技术 班 级： 学 号： 姓 名：李恰 指导教师：郑智勇 完成日期：2009年7月8日 目目 录录 第一章第一章 需求分析需求分析.1 1.1题目内容与要求.1 1.2 题目理解与功能分析 .1 第二章第二章 概要设计概要设计.2 2.1 设计思路 .2 2.2系统模块图.2 第三章第三章 详细设计详细设计.3 3.1 图存储结构的建立 .3 3.2 求取关键路径 .4 3.3 主程序建立 .4 第四章第四章 实

2、验结果实验结果.5 参考文献参考文献.6 附附 录（程序清单）录（程序清单）.7 第一章 需求分析 1.1题目内容与要求题目内容与要求 内容： 自拟定合适的方式 ，从键盘上输入一个 AOE 网，并用合适的存储结构存储 该 AOE 网，然后求出该 AOE 网的关键路径。 基本要求： 1输入 AOE 网的方式要尽量的简单方便； 2要能够较形象地观察 AOE 网和它的关键路径； 3课程设计报告必须符合课程设计报告规范； 4提交合格的课程设计报告，经指导教师测试课设完成（验收）程序，课 设完成； 1.2 题目理解与功能分析题目理解与功能分析 该题实质要求用数据结构中的图形知识编写一个求无循环有向帯权图

3、中从起 点到终点所有路径，经分析、比较求出长度最大路径，从而求出关键路径。 通常我们用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有 向边表示活动 Vi 必须先于活动 Vj 进行。如果在这种图中用有向边表示一 个工程中的各项活动（ACTIVITY） ，用有向边上的权值表示活动的持续时间 （DURATION） ，用顶点表示事件（EVENT） ，则这种的有向图叫做用边表示活 动的网络，简称 AOE 网络。在 AOE 网络中，从源点到各个顶点，可能不止一条。 这些路径的长度也可能不同。不同路径所需的时间虽然不同，但只有各条路径上 所有活动都完成了，这个工程才算完成。因此，完成整个工程所需的

4、时间取决于 从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条 路径长度就叫做关键路径（critical path） 。 程序所要达到的功能：输入并建立 AOE 网；输出关键活动并求出这个工程的关键路径；求出完成这个关键路径的最 少时间并输出，该程序结束。 第二章 概要设计 2.1 设计思路设计思路 基本设计思路： (1) 以某一个求无循环有向帯权图蓝本。 (2) 观察并记录这个图中每个弧的起始点及权值。 (3) 用记录的结果建立E 网，即边表示活动的网络，并用图的形式表示。 (4) 用领接表来存储图这些信息。 (5) 用 CreateGraph( )函数建立 AOE 图。

5、 (6) 用 SearchMapPath ( )函数求出最大路径，并打印出关键路径。 (7) 编写代码并测试。 2.2系统模块图系统模块图 图图 2-1 系统模块图系统模块图 第三章 详细设计 3.1 图存储结构的建立图存储结构的建立 1. 先建立邻接表的存储单元，为建立邻接表做准备。为图中每个顶点建立一 个单链表，第 i 个单链表中的结点表示依附于顶点 vi 的边（对于有向图是以 vi 为 尾的弧） 。每个结点由 3 个域组成，其中邻接域（adjvex）指示与顶点 vi 邻接的 点在图中的位置，链域(nextedge)指示下一条边或弧的结点，权值域（W）存储边 或弧的权值大小。在表头结点除了

6、设有链域（firstedge）指向链表中第一个结点 之外，还设有存储顶点 v 或其他有关的数据域（data）和存储顶点入度的域（id） （代码如下） 。 typedef struct node int adjvex; int w; struct node *nextedge; edgenode; typedef struct char data; int id; edgenode *firstedge; vexnode; 2. 然后构造有向图。第一，输入顶点信息存储在顶点表中，并初始化该顶点 的便表。第二，首先输入边所依附的两个顶点的序号 i 和 j 然后生成新的邻接点 序号为 j 的边表结点

7、，最后将该结点插入到第 i 个表头部。(代码如下) for(int k=0;kadjvex =end-1; p-w =duttem; Graphend-1.id +; p-nextedge =Graphbegin-1.firstedge ; Graphbegin-1.firstedge =p; 3.2 求取关键路径求取关键路径 利用 AOE 网进行工程管理时，需解决的两个主要问题：其一，计算完成整 个工程的最短工期；其二，确定关键路径，以找出哪些活动时影响工程进度的关 键。因此须计算以下几点： （1）事件的最早发生时间 vek； （2）事件最迟发生时间 vlk； （3）活动最早开始时间 eei

8、； （4）活动的最迟开始时间 eli； 计算其过程必须分别在拓扑有序和逆拓扑有序的前提下进行。也就说，vek 必须在事件 vk 所有前驱的最早发生的时间求得之后才能确定。因此，可以在拓 扑排序的基础上计算 vek和 vlk。由此得到求解关键路径的方法： 首先输入 e 条有向边，建立 AOE 网的邻接表存储结构；然后从始点出发， 令事件的最早发生时间为 0，按拓扑有序求其余各顶点时间的最早发生时间 vek； (代码如下) while(p) k=p-adjvex ; Graphk.id -; if(vej+p-w vek) vek=vej+p-w ; 接着从终点出发，令事件最迟发生时间等于其最早发

9、生时间，按你你逆拓扑 排序求其余各顶点事件最迟发生时间 vlk；最后根据各顶点事件的 ve 和 vl 值， 求所有活动最早开始时间 ee 和最迟开始时间 el。如果某活动满足条件 eeel，则 为关键活动。(代码如下) if(eli=eei) printf( 此弧为关键活动 ); 同时，为计算各顶点事件的 ve 值是在拓扑排序的过程中进行的，因此需一 个队列来记录拓扑排序，如果顶点的入度为 0，则该顶点从队尾进入队列，拓扑 排序时，从队头出队列。 if(Graphk.id =0) topology_queue+rear=k; p=p-nextedge ; 3.3 主程序建立主程序建立 该部分主

10、要是对所建立的函数的调用。 包括： 建立图的函数 CreateGraph( )； 计算关键路径的函数 SearchMapPath ( )； 最后程序结束。 这样安排可以增强程序的可读性，是程序便于理解，也便于日后的对程序的 维护和修改等操作。 第四章 实验结果 按照要求输入一组关于无循环有向帯权图所有信息。 依次执行程序每一步，最后结束该程序。 程序运行如下图： 图图 4-1 运行结果运行结果 参考文献 1 严蔚敏编.数据结构（C 语言版）.北京: 清华大学出版社，1997.2 2 谭浩强著.C 语言程序设计（第二版）.北京: 清华大出版社，2001.3 3 夏克俭编著.数据结构.北京: 国防

11、工业出版社，2000.7 4 彭勃.数据结构.北京: 电子工业出版社，2007.6 5 宜晨编著.Visual C+5.0 实用培训教程.北京：电子工业出版社，1998.5 6 崔武子.C 语言程序设计实践教程.北京:清华大出版社, 2006.1 7 庞振平.计算机程序设计基础.广州: 华南理工出版社，2002.9 附 录（程序清单） #include #include typedef struct node int adjvex; int w; struct node *nextedge; edgenode; typedef struct char data; int id; edgenod

12、e *firstedge; vexnode; void CreateGraph(vexnode* Graph,int vexnumber,int arcnumber) int begin,end,duttem; char ch; edgenode *p; for(int i=0;ivexnumber;i+) Graphi.id =0; Graphi.firstedge =NULL; printf(请输入这个图中的各个顶点的值:n); for(i=0;ivexnumber;i+) scanf(%s, Graphi.data=ch; printf(请输入图中弧的起始点及权值:其格式为n); for

13、(int k=0;kadjvex =end-1; p-w =duttem; Graphend-1.id +; p-nextedge =Graphbegin-1.firstedge ; Graphbegin-1.firstedge =p; int SearchMapPath(vexnode* Graph,int vexnumber,int arcnumber) int totaltime=0; int m=0; int i,j,k,t; char sv100; int front,rear; int *topology_queue,*vl,*ve,*el,*ee; front=rear=-1;

14、t=0; topology_queue=(int*)malloc(vexnumber*sizeof(int); vl=(int*)malloc(vexnumber*sizeof(int); ve=(int*)malloc(vexnumber*sizeof(int); el=(int*)malloc(arcnumber*sizeof(int); ee=(int*)malloc(arcnumber*sizeof(int); edgenode *p; for(i=0;ivexnumber;i+) vei=0; for(i=0;iadjvex ; Graphk.id -; if(vej+p-w vek

15、) vek=vej+p-w ; if(Graphk.id =0) topology_queue+rear=k; p=p-nextedge ; if(mvexnumber) printf(n 本程序所建立的图有回路不可计算出关键路径n); printf(将退出本程序n); return 0; totaltime=vevexnumber-1; for(i=0;i=0;i-) j=topology_queuei; p=Graphj.firstedge; while(p) k=p-adjvex ; if(vlk-p-w )w; p=p-nextedge; printf(| 起点 | 终点 | 最早开始

16、时间 | 最迟开始时间 | 差值 | 是否为关键 路径 n); i=0; for(j=0;jadjvex ; ee+i=vej; eli=vlk-p-w; printf(| %4c | %4c | %12d | %12d | %4d |,Graphj.data ,Graphk.data ,eei,eli,eli- eei); if(eli=eei) printf( 此弧为关键活动 ); svt=Graphj.data;t+; printf(n); p=p-nextedge; printf(关键路径节点为：); svt=Graphvexnumber-1.data; for(i=0;i); pri

17、ntf(n); printf(关键路径长度为：%d 个单位时间n,totaltime); return 1; void main( ) int vexnumber,arcnumber,totaltime=0; printf(请输入这个图中的节点数:); scanf(%d, printf(请输入这个图中的弧数:); scanf(%d, vexnode* Graph=(vexnode*)malloc(vexnumber*sizeof(vexnode); CreateGraph(Graph,vexnumber,arcnumber); SearchMapPath(Graph,vexnumber,arcnumber); 课程设计总结：课程设计总结： 从这次