拓扑排序
#图
目录
1. 定义
- 把图拉平,如果
拉平的图
的箭头方向都是一致的(比如上图所有箭头都是==朝右==的),那么这张图是可拓扑排序的- 有向有向图,无法拓扑排序,因为肯定做不到所有箭头方向一致
- 有向无环图,一定可以进行拓扑排序
- 如何进行拓扑排序
- 把图的后序遍历的结果进行反转,就是拓扑排序的结果,为什么?
2. 为什么图的后序遍历的结果进行反转,就是拓扑排序的结果
- 二叉树的后序遍历是什么时候?
- 遍历完左右子树之后才会执行后序遍历位置的代码
- 换句话说,当左右子树的节点都被装到结果列表里面了,根节点才会被装进去
- 之所以拓扑排序的基础是后序遍历,是因为==一个任务必须等到它依赖的所有任务都完成之后才能开始开始执行==