7-10-有向网关键路径-图-第7章-《数据结构》课本源码-严蔚敏吴伟民版
课本源码部分
第7章 图 - 有向网关键路径
——《数据结构》-严蔚敏.吴伟民版
源码使用说明 链接☛☛☛ 《数据结构-C语言版》(严蔚敏,吴伟民版)课本源码+习题集解析使用说明
课本源码合辑 链接☛☛☛ 《数据结构》课本源码合辑
习题集全解析 链接☛☛☛ 《数据结构题集》习题解析合辑
本源码引入的文件 链接☛ Status.h、SequenceStack.c、ALGraph.c
文档中源码及测试数据存放目录:数据结构\▲课本算法实现\▲07 图\10 CriticalPath
概述
关键路径通常(但并非总是)是决定项目工期的进度活动序列,它是项目中最长的路径,即使很小浮动也可能直接影响整个项目的最早完成时间。
解析
用顶点表示事件,弧表示活动,弧上的权值表示活动持续的时间的有向图叫AOE(Activity On Edge Network)网,在建筑学中也称为关键路线。AOE网常用于估算工程完成时间。
关键路径的算法建立在拓扑排序的基础之上,其计算方法简述为:
1.输入e条弧<j,k>,建立AOE-网的存储结构。
2.拓扑排序,并求得ve[]。从源点V0出发,令ve[0]=0,按拓扑有序求其余各顶点的最早发生时间ve[i]。如果得到的拓扑有序序列中顶点个数小于网中顶点数n,则说明网中存在环,不能求关键路径,算法终止;否则执行步骤3。
3.拓扑逆序,求得vl[]。从汇点Vn出发,令vl[n-1] = ve[n-1],按逆拓扑有序求其余各顶点的最迟发生时间vl[i]。
4.求得关键路径。根据各顶点的ve和vl值,求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s) = l(s),则为关键活动。
注:此有向网使用了图的邻接表存储结构是为了方便进行拓扑排序。由于此处的邻接表存储结构中无结点的权值信息,故将有向网的权值信息放到了"弧的附加信息"中,也算是变通吧。当然,也可以通过修改原来的邻接表存储结构来应对此处的算法。
源码
文件一 ☛ CriticalPath.h
文件二 ☛ CriticalPath.c
文件三 ☛ CriticalPath-main.c (测试文档)
文件四 ☛ TestData_DG_AL.txt(有向网关键路径测试数据)
测试结果展示
更多章节持续更新中...![微笑](http://static.blog.csdn.net/xheditor/xheditor_emot/default/smile.gif)
相关文章
- Java 集合框架03---ArrayList的源码分析
- Redis Sentinel 源码:Redis的高可用模型分析
- 超简单的pyTorch训练->onnx模型->C++ OpenCV DNN推理(附源码地址)
- Hive源码编译及阅读修改调试
- postgresql 11.6 源码安装
- 数据结构算法 - ConcurrentHashMap 源码解析
- 数据结构算法 - ConcurrentHashMap 源码解析
- Java 集合系列之 Vector详细介绍(源码解析)和使用示例
- Android 源码编译
- wubi安装ubuntu后,增加swap大小,优化swap的使用参数-----------让ubuntu健步如飞,为编译android源码准备
- 11-2-置换-选择排序-外部排序-第11章-《数据结构》课本源码-严蔚敏吴伟民版
- 10-8-简单选择排序-内部排序-第10章-《数据结构》课本源码-严蔚敏吴伟民版
- 10-7-快速排序-内部排序-第10章-《数据结构》课本源码-严蔚敏吴伟民版
- 10-3-二路插入排序-内部排序-第10章-《数据结构》课本源码-严蔚敏吴伟民版
- 9-2-折半查找/二分查找-查找-第9章-《数据结构》课本源码-严蔚敏吴伟民版
- 8-3-无用单元收集-动态存储管理-第8章-《数据结构》课本源码-严蔚敏吴伟民版
- 7-2-图的邻接表存储-图-第7章-《数据结构》课本源码-严蔚敏吴伟民版
- 6-4-线索二叉树-树和二叉树-第6章-《数据结构》课本源码-严蔚敏吴伟民版
- 6-1-二叉树顺序存储结构-树和二叉树-第6章-《数据结构》课本源码-严蔚敏吴伟民版
- 5-6-广义表(扩展线性链表存储表示)-数组和广义表-第5章-《数据结构》课本源码-严蔚敏吴伟民版
- 3-5-表达式求值-栈和队列-第3章-《数据结构》课本源码-严蔚敏吴伟民版
- 3-4-迷宫寻路-栈和队列-第3章-《数据结构》课本源码-严蔚敏吴伟民版
- 2-11-一元多项式运算-线性表-第2章-《数据结构》课本源码-严蔚敏吴伟民版
- 2-3-归并单链表(顺序表)-线性表-第2章-《数据结构》课本源码-严蔚敏吴伟民版
- 大数据Spark “蘑菇云”行动前传第8课:零基础实战Scala最常用数据结构Map和Tuple及Spark源码解析
- 36.QT-解决无边框界面拖动卡屏问题(附带源码)
- keystone系列五:keystone源码分析
- 【Android 安装包优化】p7zip 源码交叉编译 Android 平台可执行程序 ( 下载 p7zip 源码 | 交叉编译 Android 中使用 7z 可执行程序 )
- HBase源码分析之KeyValue