拓扑排序

#图

目录

1. 定义

图片&文件

  • 把图拉平,如果拉平的图的箭头方向都是一致的(比如上图所有箭头都是==朝右==的),那么这张图是可拓扑排序的
    • 有向有向图,无法拓扑排序,因为肯定做不到所有箭头方向一致
    • 有向无环图,一定可以进行拓扑排序
  • 如何进行拓扑排序
    • 图的后序遍历的结果进行反转,就是拓扑排序的结果,为什么?

2. 为什么图的后序遍历的结果进行反转,就是拓扑排序的结果

  • 二叉树的后序遍历是什么时候?
    • 遍历完左右子树之后才会执行后序遍历位置的代码
    • 换句话说,当左右子树的节点都被装到结果列表里面了,根节点才会被装进去
    • 之所以拓扑排序的基础是后序遍历,是因为==一个任务必须等到它依赖的所有任务都完成之后才能开始开始执行==

图片&文件

图片&文件

3. 相关题目