图之--AOV/AOE网及关键路径

有向图的两个广泛应用的网络，AOV和AOE网
AOV网：图中的顶点表示活动，边表示依赖关系
AOE网：图中的顶点表示事件，边表示事件持续的时间，20世纪40年代美国军方研发

1. AOV网
   举个例子就很容易解释：比如大学里的选课系统，大学物理要在完成高等数学之后才能学习
   这里有个死循环的问题，如果两个科目互相依赖就是死循环。存在死循环的网络是AOV网但不是拓扑序列。
   拓扑排序算法：
   1）从N中选出一个入度为0的顶点作为序列的下一个顶点
   2）从N网中删除所选顶点及所有的出边
   3）循环1）-2）直到再也没有入度为0的顶点时算法结束
   涉及关键技术：零度表的建立
   连通图时间复杂度：O(E+V)，空间复杂度：O(v)
   链接矩阵的时间复杂度：O（V2）
2. AOE网和关键路径
   AOE网是无环的带权有向图。关键路径是找出图中从起点到终点的最慢的时间路径。完成整个工程所需要的最少的时间取决于这条路径，所以称之为关键路径。