(资料图)

今天，发了最小生成树的两个算法，实在不想说话了，还剩最后一章《拓扑排序》，就用这篇文章结束吧！

一.AOV网

简单来说，就是一个有向无环图，无回路。

在原神中，你要完成某个任务，但会有一些前面的任务一直干扰着你，此时，你不得完成前面任务，才开始这个任务，用图表示出来，之后，你会想，我应该怎么设计一个路线，完成所有任务呢？

其实，任务表示出来的图，就是AOV网， 描述出来的的路线就是拓扑排序的结果序列。

二.拓扑排序

每次将入度为0的点加入序列中，并修改后面的入度与出度可有深搜或广搜来完成，（注：广搜时应用栈来实现）

代码如下：

简单，高效，使用的算法，复杂度为O(V+E)

三.AOE关键路径

AOE关键路径主要讨论的完成一个工程至少需要多少天，在AOV网上完成，用拓扑排序实现

1.最早发生与最早开始时间

活动k需要前面的事情完成，设前面的事情为earliest[j],现在的事情为earliest[k] 则earliest[k]=earliest[j]+完成earliest[j]的时间

2.最晚发生时间

考虑实际生活中，某些问题需要在最迟时间之前或现在完成，不然会影响工程的完成天数，

设前面的事情为lastest[j],现在的事情为lastest[k]

lastest[n]=earliest[n]  

lastest[j]=min(lastest[k]-完成lastest[j]的时间)由于前面的任务不是单一的，所以要取最小值

3.计算最早和最晚发生时间

actearliest[i]=earliest[j]

actlastest[i]=lastest[j]-完成j的时间

4.代码实现    有一点长，请分块理解

都看到了这，三连再走吧！求求了！

想要观看更多内容，关注数学哪里出来!