image.png

    树也是一种图：
    图的宽度优先在树上就是层次遍历，可以用队列实现。
    tips：

    • 通常宽度优先的题目都能用队列，比如二叉树层次化顺序的序列化和反序列化
    • 用魔法打败魔法。

    图的深度优先在树上就是前序遍历，可以用栈实现。

    图可能有环，所以第三步就是这样一种机制，不会死循环
    问题一： 宽度优先遍历
    set是保证这个点不重复进队列。
    image.png
    image.png
    深度优先遍历
    image.png
    tips： 栈保存的是回溯的路径，所以当出栈的时候，如果碰到没有加入去重集合的值，那么要将这个节点重新入栈。
    image.png
    image.png
    tips：最常用的用途是依赖文件、编译顺序。
    只有有向无环图才可以。
    image.png
    解法：
    step1: 准备一个队列， 和一张当前节点入度的字典，将入度为0的节点放进队列
    step2: 队列中弹出一个节点，并在字典中 将相邻节点入度减一，若该节点入度变成0，入队列
    重复弹出队列操作。
    image.png