bfs dfs

引用https://leetcode-cn.com/problems/flood-fill/solution/python3-dfs-yu-bfs-liang-chong-fang-fa-san-chong-s/

图像渲染题目:
BFS:
首先找到初始节点，给它染色，这个初始节点当作第一层。
找到初始节点周围四个节点，给它们染色（符合条件的才能染），这四个节点当作第二层。
再找到这四个节点周围八个节点，给它们染色，这八个节点当作第三层。
重复以往，层层递进，直到找不到符合要求的节点。
就是一个从中间向外扩散的过程。

队列实现:
我们可以这样利用 *队列 *实现 广度优先搜索。

我们设置一个队列，先把初始点添加进去
规定每次从队列取出一个坐标
对这个坐标染色，并且把这个坐标的邻居（符合要求且不重复的好邻居），放到队列中。
当这个队列为空的时候，说明染色完成

因为队列每次取出的是最后的，而每次添加的是放在最前面，所以可以想象到，每次先处理的都是层级最少的，最接近初始点的，然后慢慢扩大，这样就实现了 广度优先搜索。

在这道题目里，层级是 不重要 的，这也是为什么后来还有个深度优先搜索，也可以解决这道题目。但是广度优先搜索的特点就在于这个层级，在很多题目当中它是很重要的。有时候，对队列取出元素的时候，要设置循环，固定住当前的队列项，对当前的队列项操作——因为当前的队列项一定是相同层级的。例如，在我们寻找到达某个节点的最小步数的时候，层级也就是步数就显得尤为重要了。

DFS:

先定个四个方向的顺序，例如上下左右，先上后下后左最后右
首先找到初始节点，给它染色。
按照方向的顺序，这里是上，就先把这个点的上方点先染色。
一直往上一直往上，直到不符合要求，便退一步，再找这个点的下方向
重复这个步骤。
换句话说，先把这个点上方的都弄完，再把这个点下边的都弄完，再左边的，最后下边的。

就是一个从中间向一个方向深入的过程。

堆栈实现:
我们可以这样利用堆栈实现深度优先搜索。
我们可以这样利用堆栈实现深度优先搜索。

我们设置一个栈，先把初始点添加进去
规定每次从栈中取出一个坐标
对这个坐标染色，并且把这个坐标的一个方向上的邻居（符合要求且不重复的好邻居），放到栈中。
当这个方向没有复合要求的邻居的时候，进入下一个方向
当这个栈为空的时候，说明染色完成
因为栈每次取出的是最后的，而每次添加的也在最后，所以可以想象到，每次先处理的都是最深的，然后慢慢扩大，这样就实现了深度优先搜索。

作者：qsctech-sange
链接：https://leetcode-cn.com/problems/flood-fill/solution/python3-dfs-yu-bfs-liang-chong-fang-fa-san-chong-s/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

DFS 能找最短路径，但是时间复杂度相对高很多。要把二叉树中所有树杈都探索完才能对比出最短的路径有多长。而 BFS 借助队列做到一次一步「齐头并进」，是可以在不遍历完整棵树的条件下找到最短距离的。

形象点说，DFS 是线，BFS 是面；DFS 是单打独斗，BFS 是集体行动。

BFS 可以找到最短距离，但是空间复杂度高，而 DFS 的空间复杂度较低。

还是拿刚才我们处理二叉树问题的例子，假设给你的这个二叉树是满二叉树，节点数为 N，对于 DFS 算法来说，空间复杂度无非就是递归堆栈，最坏情况下顶多就是树的高度，也就是 O(logN)。

但是你想想 BFS 算法，队列中每次都会储存着二叉树一层的节点，这样的话最坏情况下空间复杂度应该是树的最底层节点的数量，也就是 N/2，用 Big O 表示的话也就是 O(N)。

由此观之，BFS 还是有代价的，一般来说在找最短路径的时候使用 BFS，其他时候还是 DFS 使用得多一些（主要是递归代码好写）。

作者：labuladong
链接：https://leetcode-cn.com/problems/open-the-lock/solution/wo-xie-liao-yi-tao-bfs-suan-fa-kuang-jia-jian-dao-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。