0x01.前序

有一位小伙伴问我，迷宫问题怎么解决，我说DFS或者BFS，然后，TA 说，哦哦，这我知道，就是图里面的算法嘛，但，这是个迷宫，难道我要把这个二维矩阵变成图嘛？

我：当场去世。。。

Test

于是我开启了我的长篇大论。。。

希望大家有所收获。

0x02.DFS和BFS简要介绍

首先，回答一下那位小伙伴的问题，这个算法确实属于图里面的算法，但并不是说是专门针对图的算法，它在算法领域应用非常广泛，可以说是一种不可缺少的思想。

官方说明：

  • DFS：深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。
  • BFS：宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

简要理解：

说实话，我第一次看没看懂，确实比较官方，我们可以用我们的思维去简单的理解一下：

  • DFS：深度优先搜索，是一种搜索算法，讲究搜索的深度，所以叫深度优先算法。又叫回溯算法。这个算法的核心就是不断的往更深的地方搜索，如果更深的地方搜索失败了，就返回来搜，是一个回溯的过程。

  • BFS：广度优先搜素，也是一种搜索算法，讲究搜索的广度，所以叫广度优先算法。这个算法的核心就是，先把周围的找完，再去找更深的地方。- 通俗易懂的说法：DFS就是一条路走到底，发现没路了，返回来，走另一条路。BFS就是每条路都走一点，走一点点后就走另一条路了。

    不如看张图，看图吧：
    Test
    Test

如果你还对这两种方式不理解，你可以看一下。

0x03.DFS和BFS的实现方式

这两种算法的不同主要在于优先级的不同，所以实现方式是很相似的。

这两种算法都可以使用的递归的方式，其中DFS还可以用栈来实现，BFS还可以用队列实现。

具体的实现，可以参考 ：

DFS和BFS用递归实现的思路：
  • 根据各自传参的优先级的顺序，不断的调用自身。
  • 一般情况下，用递归实现BFS比较为难，所以常用队列实现。
    DFS用栈实现的思路：
  • 每遇到一个元素，就把这个元素的所有邻接元素入栈，当栈不为空的时候，不断的从栈顶拿出元素进行操作，直到栈为空。
    BFS用队列实现的思路：
  • 每遇到一个元素，就把这个元素的所有邻接元素放入队列，当队列不为空的时候，不断从队首拿出元素进行操作，直到队列为空。
    特别的：
  • 在非递归的实现中，你只需要把DFS的栈全部改为队列，它就变成BFS了哦~

0x04.DFS和BFS的应用区别

其实，大部分问题都是既可以用BFS，也可以用DFS的，但是这两种算法面对不同的问题，解决效率并不一样。

  • BFS类似于水波纹的扩散，在求解一些最短路径，最优值问题的时候效率很高。
  • BFS为了遍历，需要保存所有的状态，对空间来说是一个巨大的消耗。（因为通常是无法递归实现的）
  • DFS主要应用于回溯的搜索问题中，比如迷宫问题，岛屿问题。
  • DFS能够做到使用一个状态变量去搜索所有的状态空间，这对空间的消耗来说，是非常节约空间的（通常使用递归实现）。

0x05.如何根据问题选择实现方式

我的观点就是：无特殊情况，DFS就用递归实现，BFS就用队列实现。

我们看一下两种实现方式对处理问题带来的不同：

  • 使用递归的方式对于恢复状态非常方便，因为大部分问题在回溯后都需要恢复相应的状态
  • 使用非递归方式对于一些求值问题来说，比较容易理解的产生原理。
  • 递归可能消耗时间会多一些。
  • 使用栈和队列可能空间消耗会非常大。
  • 非递归实现的解决问题方式，一目了然，比较容易看懂。
  • 递归解决，如果你对递归的调用过程还不是非常清晰的时候，可能就比较难理解。
  • DFS无特殊情况就使用递归的原因是，递归更能体现这种回溯的思路。
  • BFS无特殊情况就使用对垒实现的原因是，一般递归实现会比较难。

0x06.如何使用这两种算法去解决相应的问题

第一步，确定什么问题可以用这两种算法解决：（可别说只针对图了啊）

  • 凡是在一个二维矩阵中，找路径，找方法数，搜索东西，想都不要想，一般都可以用上。- 去遍历图肯定是可以的
  • 看到有关找方法的问题，可以尝试使用。- 凡是包含搜索思想的，都可以使用。

第二步，确定使用的算法和实现形式，具体看上文。

第三步，根据题目的需求，确定搜索失败后是否需要还原状态，求值问题是否需要更新值。

第四步，设计针对性的算法。

注意事项：

  • 关于求种数问题，一定要明白，每一步递归返回值的含义。- 求最短路径问题，搜索失败后，一定要还原状态，比如某些标志遍历，或者矩阵里的坐标之类的。

调试小技巧：通过输出关键操作的值，来确定程序执行的顺序，确定出错原因。

0x07.常用的优化算法的思路

我们设计算法，不是为了单纯AC问题，而是，追求极致，比如，这个： 在这里插入图片描述

优化时间的思路：

  • 过滤没有必要的递归。
  • 合适的使用相应的数据结构。
  • 传参的时候传实参（指针或者引用），如果传形参会造成反复拷贝参数，如果参数过大的话，会超出时间限制。
    优化空间的思路：
  • 在需要恢复状态的时候，可以采用沉岛思想，不过需要题目适用。
  • 沉岛思想的关键是把已经访问过的值，变成一些完全不可能的值，避免重复访问，也可以根据是否需要恢复状态，考虑是否可以直接删去。

0x08.谈谈它们的鼻祖

这两种算法的鼻祖就是搜索算法，搜索算法的核心就是遍历到所有可能的情况，所以，常见的暴力枚举也是搜索算法的一种，所以我们在采用这两种算法的时候，思路就已经是在遍历所有可能的情况了，但是在这其中，可以借助贪心的思维去优化，做到不必要遍历每种情况。

0x09.如何快速提升使用它们的能力

算法，还是要使用，所有，多练习经典的题目吧！！！ 下面是一些比较经典的题目，你也可以尝试去做N皇后问题，迷宫问题。

最后，多练多收获！！！

最后修改：2022 年 03 月 28 日
© 转载自他站
如果觉得我的文章对你有用，请随意赞赏