关键路径算法课程设计

1、数据结构课程设计说明书 题目： 求网中的关键路径 班 级 计科 1203 组 别： 指导老师： 彭代文 完成时间： 2014.6.6 组 长： 王勋峰 学 号： 19 组 员 1： 蒋磊 学 号： 18 组 员 2： 刘源 学 号： 17 组 员 3： 陈乙生 学 号： 16 成 绩： 目目 录录 一一 需求分析需求分析.1 1.1 题目内容与要求.1 1.2 题目理解与功能分析 .1 二二 概要设计概要设计.2 2.1 设计思路 .2 2.2 系统模块图.2 2.2 系统模块图.3 三三 详细设计详细设计.4 3.1 图存储结构的建立.4 3.2 求取关键路径.8 3.3 主程序建立10 四

2、四 实验结果实验结果.11 五五 课程设计心得课程设计心得.12 六六 参考文献参考文献.13 七七 附录（程序清单）附录（程序清单）14 一 需求分析 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) 用记录的结果建立 AOE 网，即边表示活动的网络，并用图的形式表示。 (4) 用领接表来存储图这些信息。 (5)

5、用 CreateGraph( )函数建立 AOE 图。 (6) 用 CriticalPath ( )函数求出最大路径，并打印出关键路径。 (7) 编写代码并测试。 2.2系统模块图系统模块图 图图 2-1 系统模块图系统模块图 三 详细设计 3.1 图存储结构的建立图存储结构的建立 全局变量及用途全局变量及用途： #define MAX_VERTEX_NUM 50 / 最大顶点数 int indegreeMAX_VERTEX_NUM; / 存放节点入度数组 int veMAX_VERTEX_NUM,vlMAX_VERTEX_NUM; / 顶点事件 最早发 生时间 和最迟发生时间数组，全局变量

6、初始为 0 int eeMAX_VERTEX_NUM,elMAX_VERTEX_NUM; / 弧活动 最早发 生时间 和最迟发生时间数组 stack S; / 存放 入度为 0 的结点 stack T; / 存放 顶点的拓扑序列 1 先建立邻接表的存储单元，为建立邻接表做准备。为图中每个顶点建立一个 单链表，第 i 个单链表中的结点表示依附于顶点 vi 的边（对于有向图是以 vi 为尾 的弧） 。每个结点由 3 个域组成，其中邻接域（adjvex）指示与顶点 vi 邻接的点 在图中的位置，链域(nextedge)指示下一条边或弧的结点，权值域（W）存储边或 弧的权值大小。在表头结点除了设有链域

7、（firstedge）指向链表中第一个结点之 外，还设有存储顶点 v 或其他有关的数据域（data）和存储顶点入度的域（id） （代码如下） 。 数据存储结构：数据存储结构： typedef struct ArcNode / 结点 结构 int adjvex; / 该边所指的顶点的位置 struct ArcNode *nextarc; / 指向下一条边的指针 InforType info; / 弧的长度(关键路径中的活动) ArcNode; / 表的结点 typedef struct VNode / 顶点 VertexType data; / 顶点信息 【如数据等】 ArcNode *firs

8、tarc; / 指向第一条依附该顶点的边的弧指针 VNode; typedef struct ALGraph VNode verticesMAX_VERTEX_NUM; / 顶点 线性表 【数组】 int vexnum, arcnum; / 图的当前 顶点数 和 弧数 ALGraph; 2构造有向图。构图函数由增加结点和增加边构成。第一，增加结点：输入 顶点数级定点信息，并初始化该顶点的边表。第二，首先输入边所依附的 两个顶点及权重，最后将该结点接到第 i 个表尾部。(代码如下) 定位函数： /=返回顶点 v 在顶点向量中的位置= int LocateVex (ALGraph *G, char

9、 v) for(int i = 1; v != G-verticesi.data i+) if(i G-vexnum) return 0; return i; /=构造邻接链表 图= void CreateGraph(ALGraph *G) add_vex(G); / 增加节点 add_arc(G); / 增加边 /=增加边= void add_arc(ALGraph *G) ArcNode *s; ArcNode *p; coutG-arcnum; char v1, v2; int length; coutnn 输入边信息(始点 终点 权值): endl; for(int k = 1; k

10、arcnum; k+) cinv1v2length; int i = LocateVex(G, v1); int j = LocateVex(G, v2); / 确定 v1 , v2 在 G 中的位置 indegreej+; / 点 j 的入度增加 1 s = (ArcNode *) malloc (sizeof(ArcNode); s-adjvex = j; / 该边所指向的顶点的位置为 j s-info = length; s-nextarc = NULL; if(G-verticesi.firstarc=NULL) G-verticesi.firstarc=s; else for(p =

11、 G-verticesi.firstarc; p-nextarc!=NULL; p = p-nextarc) / 尾插法 构建顶点 链表; p-nextarc=s; 3.2 求取关键路径求取关键路径 利用 AOE 网进行工程管理时，需解决的两个主要问题：其一，计算完成整 个工程的最短工期；其二，确定关键路径，以找出哪些活动时影响工程进度的关 键。因此须计算以下几点： （1）事件的最早发生时间 ve k； （2）事件最迟发生时间 vl k； （3）活动最早开始时间 ee i； （4）活动的最迟开始时间 el i； 计算其过程必须分别在拓扑有序和逆拓扑有序的前提下进行。也就说，vek 必须在事件

12、vk 所有前驱的最早发生的时间求得之后才能确定。因此，可以在拓 扑排序的基础上计算 vek和 vlk。由此得到求解关键路径的方法： 首先输入 arcnum 条有向边，建立 AOE 网的邻接表存储结构；然后从始 点出发，令事件的最早发生时间为 0，按拓扑有序求其余各顶点时间的最早发生 时间 vek； (代码如下) If (vet + p-info vek) vek = vet + p-info; / vek k(终点) 顶点事件 最早 能发生的时间 ve 初始为 0 接着从终点出发，令事件最迟发生时间等于其最早发生时间，按你你逆拓扑 排序求其余各顶点事件最迟发生时间 vlk；最后根据各顶点事件的

13、 ve 和 vl 值， 求所有活动最早开始时间 ee 和最迟开始时间 el。如果某活动满足条件 eeel，则 为关键活动。(代码如下) if( vlk - dut vlt ) vlt = vlk - dut; / vlt t(始点) 顶点事件 最迟发生时间 for(int j=1; jvexnum; j+) p=G-verticesj.firstarc; while(p) i+; int k = p-adjvex; eei = vej; eli = vlk-p-info; printf(| %3c | %3c | %6d | %6d | %3d |,G- verticesj.data, G-v

14、erticesk.data, eei, eli, eli-eei); if(eli=eei) printf( 此弧为关键活动 ); p=p-nextarc; 同时，为计算各顶点事件的 ve 值是在拓扑排序的过程中进行的，因此需一个栈 来记录拓扑排序，如果顶点的入度为 0，则该顶点入栈。 int t = S.top()； S.pop(); T.push(t); count+; / 度为 0 的结点出栈 S 入栈 T 栈 T 保存 拓扑序列 cout关键路径所需时间为： vexnum; 3.3主程序建立主程序建立 该部分主要是对所建立的函数的调用。 包括： 建立图的函数 CreateGraph(

15、)； 计算关键路径的函数 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 依次执行程序每一步，最后结束该程序。 程序运行如下图： 五五 程序设计心得程序设计心得 通过这次求关键路径，我对图的邻接表有了深刻的了解。以前 都是用邻接矩阵的，感觉邻接矩阵直观 简便，而这次关键路径的有 关算法，书上都是

16、使用邻接表的，我试着熟悉它，发现也挺好用的， 许多操作用邻接表更方便。 书上没有邻接表的构图代码，拓扑排序，关键路径的都是伪代 码，我不得不去查资料，思索，自己编写完整可执行的代码，这个过 程很艰辛，也很愉快。拓扑排序时我想办法弄出了不同拓扑排序的总 数，却怎么也无法打印出所有的拓扑序列。在关键路径求顶点事件最 迟的发生时间时，错把各个顶点的最早发生时间赋给了它，所以输出 的结果怎么都不对，我在这个地方纠结的好久。 知识只有在使用的时候才会远远感觉不够用，我深深体会到了 这句话。这次的程序设计对我的帮助很大，虽然真正自己写的代码并 不多，许多都是书上的代码经过补充改写的，但毕竟我都把这整个过

17、程走了一遍，熟悉了图的各种操作，各种算法我都认真看懂了，思考 了。我能感觉到自己的进步，每次编写出一个程序，在电脑上运行出 来时，都会有一种莫名的成就感，很享受这种感觉，我会继续努力的。 - 计科 1203 王勋峰 六 参考文献 1 严蔚敏编。数据结构（C 语言版） 。北京: 清华大学出版社，1997.2 2 谭浩强著。C 语言程序设计（第二版） 。北京: 清华大出版社，2001.3 3 武爱平编。C 语言程序设计。长春：吉林大学出版社出版，2010.1 七 附录（程序清单） 程序可运行 #include using namespace std; #include typedef char V

18、ertexType; typedef int VRType; typedef int InforType; #define MAX_VERTEX_NUM 50 / 最大顶点数 int indegreeMAX_VERTEX_NUM; / 存放节点入度数组 int veMAX_VERTEX_NUM,vlMAX_VERTEX_NUM; / 顶点事件 最 早发生时间 和最迟发生时间数组，全局变量 初始为 0 int eeMAX_VERTEX_NUM,elMAX_VERTEX_NUM; / 弧活动 最早 发生时间 和最迟发生时间数组 stack S; / 存放 入度为 0 的结点 stack T; /

19、存放 顶点的拓扑序列 /*/ typedef struct ArcNode / 结点 结构 int adjvex; / 该边所指的顶点的位置 struct ArcNode *nextarc; / 指向下一条边的指针 InforType info; / 弧的长度(关键路径中的活动) ArcNode; / 表的结点 typedef struct VNode / 顶点 VertexType data; / 顶点信息 【如数据等】 ArcNode *firstarc; / 指向第一条依附该顶点的边的弧指 针 VNode; typedef struct ALGraph VNode vertices50;

20、 / 顶点 线性表 【数组】 int vexnum, arcnum; / 图的当前 顶点数 和 弧数 ALGraph; /*/ /=返回顶点 v 在顶点向量中的位置= int LocateVex (ALGraph *G, char v) for(int i = 1; v != G-verticesi.data i+) ; if(i G-vexnum) return 0; return i; /=增加节点= void add_vex(ALGraph *G) coutG-vexnum; coutn 输入顶点信息: endl; for(int i = 1; i vexnum; i+) cinG-ve

21、rticesi.data; / 构造顶点向量 G-verticesi.firstarc = NULL; / 初始 链指针 /=增加边= void add_arc(ALGraph *G) ArcNode *s; ArcNode *p; coutG-arcnum; char v1, v2; int length; coutnn 输入边信息(始点 终点 权值): endl; for(int k = 1; k arcnum; k+) cinv1v2length; int i = LocateVex(G, v1); int j = LocateVex(G, v2); / 确定 v1 , v2 在 G 中

22、的位置 indegreej+; / 点 j 的入度增加 1 s = (ArcNode *) malloc (sizeof(ArcNode); s-adjvex = j; / 该边所指向的顶点的位置为 j s-info = length; s-nextarc = NULL; if(G-verticesi.firstarc=NULL) G-verticesi.firstarc=s; else for(p = G-verticesi.firstarc; p-nextarc!=NULL; p = p-nextarc) / 尾插法 构建顶点 链表 ; p-nextarc=s; /=构造邻接链表 图= v

23、oid CreateGraph(ALGraph *G) add_vex(G); / 增加节点 add_arc(G); / 增加边 /=拓扑排序= int TopologicalSort (ALGraph *G) int a10; int count = 0; / count 为入栈【访问】 顶点的计数 ArcNode *p; for(int i=1; ivexnum; i+) if(indegreei=0) S.push (i); printf(n 拓扑排序: n ); i=1; while( !S.empty() ) int t = S.top(); a0=1; ai=ai-1 * S.si

24、ze(); printf(n 第 %d 步有 (%d) 种方式, i, S.size() ); / 栈 内为度 为 0 结点的【下标】 i+; printf( -%c (%d) ,G-verticest.data,t); S.pop(); T.push(t); count+; / 度为 0 的结点出栈 S 入栈 T 栈 T 保存 拓扑序列 for( p=G-verticest.firstarc; p; p=p-nextarc ) / 与度为 0 结点 相邻的结点 的入度减 1 int k = p-adjvex; indegreek-; if(indegreek=0) S.push(k); if

25、(vet + p-info vek) vek = vet + p-info; / vek k(终点) 顶点事件 最早 能发生的时间 ve 初始为 0 printf(nn 共有 %d 种拓扑排序方式n, aG-vexnum); if(count vexnum) return 0; / 若 小于顶点数 说明 图中有环 else return 1; /=求关键路径= void CriticalPath(ALGraph *G) / G 为有向网，输出 G 的各项关键活 动 ArcNode *p; if(TopologicalSort (G)=0) coutn 该图有环!; for(int i=1; i

26、vexnum; i+) / 初始化 顶点事件最初发生的事件 为工程总时间 (为一较大值) vli=veG-vexnum; printf(n 逆拓扑序列为： ); while( !T.empty() ) int t = T.top(); printf(-%c,G-verticest.data); T.pop(); for(p=G-verticest.firstarc; p!=NULL; p=p-nextarc) int k = p-adjvex; int dut = p-info; if( vlk - dut vlt ) vlt = vlk - dut; / vlt t(始 点) 顶点事件 最迟发生时间 printf(nnn| 起点 | 终点 | 最早开始时间 | 最迟开始时间 | 差值 | 是否为关键路径 nn); i=0; for(int j=1; jvexnum; j+) p=G-vertices