数据结构拓扑排序和关键路径的求解

数据结构课程设计大作业数据结构课程设计大作业 题 目拓扑排序和关键路径的求解拓扑排序和关键路径的求解 专 业 计算机科学与技术计算机科学与技术 学生姓名 学 号 指导教师 完成日期 2015 32015 3 哈尔滨理工大学哈尔滨理工大学 目 录 一 实验内容概述 2 二 实验目的概述 2 三 解题思路的描述 3 四 源程序清单 6 五 程序调试及测试结果 11 六 结论 13 七 参考文献 13 在此处键入 拓扑排序和关键路径的求解 内容摘要内容摘要 建立一个 AOV 网 把对象与对象之间的关系在 AOV 网中体现出来 要注意 AOV 网不可以建立成环的形式 否则工程将无法进行 之后对建立的网进行拓扑排序 对于一个工程 来说 不仅要关心各子工程的之间的先后关系 还要关系整个工程的最短时间 即有向带权图的 关键路径问题 在描述关键路径问题的有向图时 顶点表示事件 便表示活动 边上的权表示活 动所需的时间 即此有向图为 AOE 网 对 AOV 网构造其所有定点的线性序列 此序列保持网中各 顶点间原有的先后关系 且是原来没有先后关系的顶点也成为有先后关系 这样的线性序列称为 拓扑有序序列 构造 AOV 网的拓扑有序序列操作称为拓扑排序 在 AOE 网中有些活动可以并行地 进行 所以完成整个工程的最短时间是从源点到汇点的最长路径的长度 路径长度是路径各边的 权值之和 把从源点到汇点的最长路径称为关键路径 关键字关键字 AOE 网 拓扑排序 关键路径 The topological sort and critical path method Abstract Establish a AOV nets the relationship between the object and the object in AOV nets reflected in AOV nets should pay attention to the form of can t establish cyclization otherwise the project will not be able to do so After the nets to establish topological sort For a project it should not only about the relationship between the construction of the project the shortest time relationship which is the key to the weighted graph routing problem In the description of the critical path problem digraph vertices then said that events the right side of the time needed to denote activities namely this is to the net AOE For all its designated AOV network structure the sequence of linear sequence of each vertex keep the relationship between the original and is originally has no successively relationship has become a vertex such as linear topological orderly sequences AOV tectonic sequences of topological orderly sequences operation called topological sort In some activity can AOE net parallel to complete the whole project so the shortest time from point of origin to the length of the longest path sinks path length is the path to the sum of the weights from the point of origin to the longest path called zhonghua critical path Key words AOE net Topological sort The key path 在此处键入 一 实验内容概述一 实验内容概述 采用图的邻接表 出边表 表示方法 实现拓扑排序和关键路径的求解过程 使用实现的算 法对于图的 AOE 网 求出各活动的可能的最早开始时间和最晚开始时间 输出整个工程的最短完 成时间是多少 哪些活动是关键活动 说明哪项活动提高速度后能导致整个工程提前完成 二 实验目的概述二 实验目的概述 AOE 网是一个带权的有向无环图 其中 顶点表示事件 弧表示活动 权表示活动持续的时间 在 AOE 网络中 有些活动顺序进行 有些活动并行进行 由于整个工程只有一个开始点和一个完 成点 故在正常情况下 无环 网中只有一个入度为零的点 称作源点 和一个出度为零的点 叫做汇点 如图 1 图 1 AOE 网络在某些工程估算方面非常有用 为了进行人力 物力的调度和分配 以缩短工期 我们必须找出影响工程进度的关键活动 争取提高关键活动的功效 若网中有多条关键路径那么 只提高一条关键路径上的关键活动的速度还不能导致整个工程缩短工期 还必须提高同时在所有 关键路径上的活动的速度 因此必须求出所有关键路径 在此处键入 三 解题思路的描述三 解题思路的描述 从源点到各个顶点 以至从源点到汇点的有向路径可能不止一条 这些路径的长度也可能不 同 完成不同路径的活动所需的时间虽然不同 但只有各条路径上所有活动都完成了 整个工程 才算完成 因此 完成整个工程所需的时间取决于从源点到汇点的最长路径长度 即在这条路径 上所有活动的持续时间之和 这条路径长度最长的路径就叫做关键路径 Critical Path 要找出关键路径 必须找出关键活动 即不按期完成就会影响整个工程完成的活动 事件 Vi 的最早开始时间 Ve i 为源点 V1 到 Vi 的最长路径长度 活动 ai 的最早开始时间 e i 活 动 ai 的最迟开始时间 l i e i l i 的活动叫做关键活动 关键路径上的所有活动都是关键活动 因 此 只要找到了关键活动 就可以找到 例如 下图是一个有 11 项活动的AOE 网 其中有 9 个事件 V1 V2 V9 每个事 件表示在它之前的活动已经完成 在它之后的活动可以开始 如 V1表示整个工程开 始 V9表示整个工程结束 V5表示活动 a4和 a5已经完成 活动 a7和 a8可以开始 与每个活动相联系的数指的是执行该活动所需的时间 如 活动 a1需要 6 天 活动 a4需要 1 天等等 从源点到汇点的关键路径为 V1 V2 V5 V8 V9 路径长度为 18 即活动 V9 的最早发生时间是 18 活动 a6的最早开始时间是 5 最迟开始时间是 8 这意味着 活动 a6推迟 3 天开始或者延迟 3 天完成 都不会影响这个工程的完成 分析 关键路径上的所有活动都是关键活动 只有提高关键活动的效率 才能缩短 整个工期 提前完成非关键活动并不能加快工程进度 辨别关键活动就是找 l i e i 的活动 要得到活动的 l i 和 e i 必须先计算事件的最早和最迟发生时间 ve 在此处键入 和 vl 关键路径举例 找出图一中的关键路径 为了找出关键路径 需要找出关键活动 因此需要计算每个事件 每个 活动的最早开始时间和最晚开始时间 最早开始时间需要从源点开始正向的进行计算 而最晚开 始时间需要从汇点逆向的开始计算 a b c 图二 在此处键入 关键路径的算法 1 入 e 条弧 j k 建立 AOE 网的存储结构 2 从源点 V0 出发 令 ve 0 0 按拓扑有序求其余各顶点的最早发生时间 ve I 1 i n 1 如果得到的拓扑有序序列中顶点个数小于网中顶点数 n 则说明网中存在环 不能求关键路径 算法终止 否则执行步骤 3 3 从汇点 vn 出发 令 vl n 1 ve n 1 按逆拓扑有序求其余各顶点的最迟发生时间 vl I n 2 i 0 4 根据各顶点的 ve 和 vl 值 求每条弧 s 的最早开始时间 e s 和最迟开始时间 l s 若某条弧 满足条件 e s l s 则为关键活动 Status criticalpath algraph g G 为有向网 输出 G 的各项关键活 动 If topologicalorder G t return ERROR Vl 0 G vexnum 1 ve G vexnum 1 初始化顶点事件的最迟发生时间 While stackempty t 按拓扑逆序求各项点的 vl 值 For pop t j p g vextices j firstarc p p p nextarc K p adjvex dut p info dut j k If vl k dut vl j vl j vl k dut for j 0 jnextarc k p adjvex dut p info ee ve j el vl k dut tag ee el printf j k dut ee el tag 输出关键活动 criticalpath 在此处键入 四 源程序清单四 源程序清单 include include include include typedef struct node 边表结点类型 int adjvex 顶点的序号 int dut 边上的权值 struct node next 指向下一条边的指针 edgenode typedef struct 顶点表结点 int projectname 顶点域 int id 顶点入度 edgenode link 边表头指针 vexnode 建立图存储结构 void CreateGraphic vexnode Graphicmap int projectnumber int activenumber projectnumber 为工程的节点数 activenumber int begin end duttem edgenode p for int i 0 i projectnumber i Graphicmap i projectname i Graphicmap i id 0 Graphicmap i link NULL 在此处键入 printf 某项目的开始到结束在图中的工程输入 n printf 如 1 3 6 回车表示第一个工程到第三各工程之间的活动用了 6 个小时 n for int k 0 kadjvex end 1 将邻接点序号 j 赋给新结点的邻 接点域 p dut duttem Graphicmap end 1 id 将入度加 1 p next Graphicmap begin 1 link Graphicmap begin 1 link p 将新结点插入到顶点 vi 的边表头 部 求关键路径 int SearchMapPath vexnode Graphicmap int projectnumber int activenumber int 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 int e int malloc activenumber sizeof int 表示活动最早开始时间 edgenode p totaltime 0 for i 0 i projectnumber i ve i 0 for i 0 iadjvex 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 projectnumber printf n 本程序所建立的图有回路不可计算出关键路径 n printf 将退出本程序 n return 0 totaltime ve projectnumber 1 for i 0 i 0 i j topologystack i p Graphicmap j link while p k p adjvex if vl k p dut dut p p next i 0 printf 起点 终点 最早开始时间 最迟完成时间 差值 备注 n for j 0 jadjvex e i ve j l i vl k p dut printf 5d 5d 5d 5d 5d Graphicmap j projectname 1 Graphicmap k projectname 1 e i l i l i e i if l i e i printf 关键活动 printf n p p next return 1 寻找关键路径 void seekkeyroot int projectnumber activenumber totaltime 0 system cls printf 请输入这个工程个数 scanf d printf 请输入这个工程和工程之间的边数 scanf d 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 n printf 欢迎进入求关键路径算法程序 n printf s S tart 开始输入工程数据并求出关键路径 n printf s E xit 退出 n printf n printf s 请输入选择 S E scanf c ch toupper ch while ch S switch ch case S seekkeyroot break case E return 1 在此处键入 五 程序调试及测试结果五 程序调试及测试结果 图三图三 图四 在此处键入 图