数据结构笔记(图->拓扑排序)

拓扑排序:
拓扑序:如果一个图里,从V到W有一条有向路径,则V一定排在W之前,满足这个条件的顶点序列就是一个拓扑序
拓扑排序:获得一个拓扑序的过程
AOV如果有合理的拓扑序,则必定是有向无环图(Directed Acyclic Graph,DAG)

方法:
每次取出入度为0的顶点,将它指向的下一个顶点入度减1

关键路径问题:
AOE(Activity On Edge)网络:
一般用来安排项目的工序:
最快完成时间:
Earlest[j] = max(Earlest[i] + C<i,j>)(取所有到J的点的最长时间的)
可以最晚完成的时间:
Latest[I] = min(Lastest[j] - C<i,j>)(取倒推回来的最小时间)
机动时间:
D<I,j> = Latest[j] - Earlest[i] - C<i,j>
关键路径:
由绝对不允许延误的活动组成的路径

练习题:旅游规划(dijkstra算法)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

友情链接更多精彩内容