图的应用：拓扑排序
拓扑排序Topological Sort
很多问题可以转化为图，利用图算法解决
例如早餐吃煎饼的过程
- 以动作为顶点，以先后次序为有向边
问题是对整个过程而言
- 一个人独自做时的先后次序
- 从加料开始？还是从加热烤盘开始?
从工作流程图得到工作次序排列的算法，称为拓扑排序
拓扑排序处理一个DAG,输出顶点的线性序列
- 使得两个顶点v,w,如果G中有(v,w)边，在线性序列中v就出现w之前
拓扑排序广泛应用在依赖事件的排期上，还可以用在项目管理、数据库查询优化和矩阵乘法的次序优化上
拓扑排序可以采用DFS很好的实现：
- 将工作流程建立为图，工作项是节点，依赖关系是有向边
- 工作流程图一定是一个DAG图，否则有循环依赖对DAG图调用DFS算法，以得到每个顶点的“结束时间”
- 按照每个顶点的“结束时间”从大到小排序输出这个次序的顶点列表
- DAG:有向无圈图，即无回路有向图
视频链接
中国大学
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！