拓扑排序

拓扑排序

0x00 什么是拓扑排序

QQ截图20200210141126

QQ截图20200210141235

QQ截图20200210141245

0x01 算法实现

QQ截图20200210141304

由于我们只需要每次找到入度为0的顶点,因此不必要进行排序,每次吧入度为0的顶点保存起来就行了

QQ截图20200210141323

0x02 关键路径

​ 关键路径有点像小学题目 最优化方案

QQ截图20200210141333

QQ截图20200210141342

先正向推最后总的最早完成时间,再反推,看每个活动是不是有 能够调整的时间(机动时间)(也就是活动完成的最晚时间和活动开始的最早时间之间的差不为0),如果没有机动时间,就说明该活动(路径,边)是关键路径,该活动的完成时间直接影响最后总的完成时间