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