数据结构和算法-AOV与AOE网络和(逆)拓扑排序与关键路径
2023-12-17 17:30:55
文章目录
AOV网络
必须是DAG图(有向无环图)
拓扑排序
排序序列不唯一
当前网中不存在无前驱的顶点即存在回路
代码实现
此时时邻接表存储
首先入度为0的点入栈
然后开始出栈,知道栈为空,每出一个保存到print数组中,然后将出栈的点指向的顶点入度减1,并把入度为零的顺便压入栈中
时间复杂度
逆拓扑排序
实现
逆邻接表
DFS算法实现逆拓扑排序
小结
AOE网络
关键路径
下图关键路径标红
按关键路径从后往前推
求关键路径
所有事件的最早发生时间就是所有活动的最早发生时间
而所有事件的最迟发生事件并不等于所有活动的最迟发生时间
所有活动的最迟发生时间需要通过活动的执行时间和所有事件的最迟发生时间来求
求事件最早发生时间
求事件最迟发生时间
求活动最早发生时间
求活动最迟发生时间
求活动余量
关键活动 关键路径的特性
缩短到一定程度时,即再缩短也无法缩短整个工程的工期了
小结
文章来源:https://blog.csdn.net/llovewuzhengzi/article/details/135045109
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!