关键路径算法课程设计

1、沈阳航空工业学院课程设计报告课程设计名称：数据结构课程设计课程设计题目：实现求关键路径的算法院（系）：计算机学院专 业：计算机科学与技术班 级：7401102学 号：指导教师：完成日期：2009年7月8日目 录 TOC o 1-5 h z HYPERLINK l bookmark6 o Current Document 第一章 需求分析1 HYPERLINK l bookmark9 o Current Document 1.1题目内容与要求1 HYPERLINK l bookmark16 o Current Document 1.2题目理解与功能分析1 HYPERLINK l bookmark

2、19 o Current Document 第二章概要设计2 HYPERLINK l bookmark22 o Current Document 2.1设计思路2 HYPERLINK l bookmark32 o Current Document 2.2系统模块图2 HYPERLINK l bookmark35 o Current Document 第三章详细设计33.1图存储结构的建立3 HYPERLINK l bookmark40 o Current Document 求取关键路径4 HYPERLINK l bookmark47 o Current Document 主程序建立5 HYPE

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

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

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

6、关键路径。编写代码并测试。2.2系统模块图图2-1系统模块图第三章详细设计3.1图存储结构的建立先建立邻接表的存储单元，为建立邻接表做准备。为图中每个顶点建立一 个单链表，第i个单链表中的结点表示依附于顶点vi的边(对于有向图是以vi 为尾的弧)。每个结点由3个域组成，其中邻接域(adjvex)指示与顶点vi邻接的 点在图中的位置，链域(nextedge)指示下一条边或弧的结点，权值域(W)存储边 或弧的权值大小。在表头结点除了设有链域(firstedge)指向链表中第一个结点之 外，还设有存储顶点v或其他有关的数据域(data)和存储顶点入度的域(id)(代 码如下)。typedef str

7、uct node intadjvex;intw;struct node *nextedge;edgenode;typedef struct chardata;intid;edgenode *firstedge;vexnode;然后构造有向图。第一，输入顶点信息存储在顶点表中，并初始化该顶点 的便表。第二，首先输入边所依附的两个顶点的序号i和j然后生成新的邻接点 序号为j的边表结点，最后将该结点插入到第i个表头部。(代码如下)for(int k=0;kadjvex =end-1;p-w =duttem;Graphend-1.id +;p-nextedge =Graphbegin-1.firste

8、dge ;Graphbegin-1.firstedge =p;3.2求取关键路径利用AOE网进行工程管理时，需解决的两个主要问题：其一，计算完成整 个工程的最短工期；其二，确定关键路径，以找出哪些活动时影响工程进度的关 键。因此须计算以下几点：（1）事件的最早发生时间vek；（2）事件最迟发生时间vlk；（3）活动最早开始时间eei；（4）活动的最迟开始时间eli；计算其过程必须分别在拓扑有序和逆拓扑有序的前提下进行。也就说，vek 必须在事件vk所有前驱的最早发生的时间求得之后才能确定。因此，可以在拓扑 排序的基础上计算vek和vlk。由此得到求解关键路径的方法：首先输入e条有向边，建立AO

9、E网的邻接表存储结构;然后从始点出发， 令事件的最早发生时间为0，按拓扑有序求其余各顶点时间的最早发生时间vek； （代码如下）while（p） k=p-adjvex ;Graphk.id -;if（vej+p-w vek）vek=vej+p-w ;接着从终点出发，令事件最迟发生时间等于其最早发生时间，按你你逆拓扑 排序求其余各顶点事件最迟发生时间vlk；最后根据各顶点事件的ve和vl值， 求所有活动最早开始时间ee和最迟开始时间el。如果某活动满足条件ee=el，则 为关键活动。(代码如下)if(eli=eei) printf(此弧为关键活动)；同时，为计算各顶点事件的ve值是在拓扑排序的过

10、程中进行的，因此需一个 队列来记录拓扑排序，如果顶点的入度为0，则该顶点从队尾进入队列，拓扑排 序时，从队头出队列。if(Graphk.id =0)topology_queue+rear=k;p=p-nextedge ;3.3主程序建立该部分主要是对所建立的函数的调用。包括：建立图的函数CreateGraph()；计算关键路径的函数SearchMapPath ()；最后程序结束。这样安排可以增强程序的可读性，是程序便于理解，也便于日后的对程序的 维护和修改等操作。第四章实验结果按照要求输入一组关于无循环有向带权图所有信息。依次执行程序每一步，最后结束该程序。程序运行如下图：,E:数据给构课设美

11、健路径新-se请瑜入这个图口的节点数法 请喻入这个图口的驰数：8 请输入这个图山的蓉个顶点的值:请输入图中弧的起始点及权值:其格式为起点，终点，权值,1,2,31,3,2253X43,6,34,6,25,6,1!起点；终点!最早开始时间!最迟开始时间!差值! 0 !0 !3 :6 !1 !4 !4 !是否为关键路径此弧为关键活动446为为节长it5路路&=，一&一二#键;HT./.TTX13468个单位时间i !1 :1 !3 !此弧为关键清夙J此弧为关键活动Press any key to continue图4-1运行结果参考文献1严蔚敏编.数据结构（C语言版）.北京：清华大学出版社，199

12、7.2谭浩强著C语言程序设计（第二版）.北京：清华大出版社，2001.3夏克俭编著.数据结构.北京：国防工业出版社，2000.7彭勃.数据结构.北京：电子工业出版社，2007.6宜晨编著Visual C+5.0实用培训教程.北京：电子工业出版社，1998.5崔武子C语言程序设计实践教程.北京:清华大出版社,2006.1庞振平.计算机程序设计基础.广州：华南理工出版社，2002.9附录(程序清单)#include#includetypedef struct node int adjvex;int w;struct node *nextedge;edgenode;typedef struct ch

13、ardata;intid;edgenode *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”,&ch);printf(-请输入图中弧的起始点及权值:其格式为 n);f

14、or(int k=0;kvarcnumber;k+) scanf(%d,%d,%d,&begin,&end,&duttem);p=(edgenode*)malloc(sizeof(edgenode);p-adjvex =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,

15、k,t;char sv100;int front,rear;int *topology_queue,*vl,*ve,*el,*ee;front=rear=-1; 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;f

16、or(i=0;ivexnumber;i+) vei=0;for(i=0;iadjvex ;Graphk.id -;if(vej+p-w vek)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-ad

17、jvex ;if(vlk-p-w )w;p=p-nextedge;printf(|起点|终点|最早开始时间|最迟开始时间|差值|是否为关键 路径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.

18、data;for(i=0;i);printf(n);printf(关键路径长度为：%d个单位时间n”,totaltime);return 1;void main( ) int vexnumber,arcnumber,totaltime=0;printf(-请输入这个图中的节点数:，scanf(%d”,&vexnumber);printf(-请输入这个图中的弧数:)；scanf(%d”,&arcnumber);vexnode* Graph=(vexnode*)malloc(vexnumber*sizeof(vexnode);CreateGraph(Graph,vexnumber,arcnumber);SearchMapPath(Graph,vexnumbe