深度优先搜索广度优先搜索

1. 什么是 “搜索” 算法

我们知道，算法都是作用于某种具体的数据结构上的，而深度优先搜索算法和广度优先搜索算法就是作用于图这种数据结构的。

图上的搜索算法，就是从图中的一个顶点出发，到另一个顶点的路径。图有两种存储方法，邻接矩阵和邻接表，在这里我们用邻接表来存储图，并以无向图作为例子，但这两种算法也同样都可以应用在有向图中。

V 为顶点个数，E 为边的条数。

 

深度优先搜索

深度优先搜索（Depth-First-Search），简称 DFS，最直观的例子就是走迷宫。

假设你站在迷宫的某个分岔路口，你想找到出口。你随意选择一个岔路口来走，走着走着发现走不通的时候就原路返回到上一个分岔路口，再选择另一条路继续走，直到找到出口，这种走法就是深度优先搜索的策略。

上图中，我们希望找到一条从 s 到 t 的路径，其中实线表示向前遍历，虚线表示回退。可以看到，深度优先搜索到的并不是从 s 到 t 的最短路径。

 

实际上，深度优先搜索用的是一种比较著名的思想——回溯思想，这种思想非常适合用递归来实现。深度优先搜索的代码里面有几个和广度优先搜索一样的部分 visited、prev 和 Print() 函数，它们的作用也都是一样的。此外，还有一个特殊的 found 变量，标记是否找到终止顶点，找到之后我们就可以停止递归不用再继续查找了。

 

在深度优先搜索算法中，每条边最多会被访问两次，一次是遍历，一次是回退。所以，深度优先搜索的时间复杂度为 O(E)。

visited、prev 数组的大小为顶点个数，而递归函数调用栈的最大深度不会超过顶点的个数，所以深度优先搜索的空间复杂度为 O(V)。

广度优先搜索

广度优先搜索（Breadth-First-Search），一般简称为 BFS。直观地讲，它其实就是一种地毯式层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。

下面我们来看一下广度优先搜索的时间复杂度和空间复杂度。

最坏情况下，终止顶点 t 距离起始顶点 s 很远，需要遍历完整个图才能找到。这时候，每个顶点都要进出一遍队列，每条边也都会被访问一次。所以，广度优先搜索的时间复杂度为 O(V+E)，V 为顶点个数，E 为边的条数。针对一个所有顶点都是联通的图，E 肯定要大于 V-1，所以时间复杂度可以简写为 O(V)。

 

空间复杂度主要是三个变量所占用的额外空间，和顶点个数成正相关，为 O(V)。

 

其中，有三个非常重要的辅助变量需要特别注意。

  • visited，布尔数组，记录顶点是否已经被访问过，访问过则为真，没有访问过则为假，这里用 0 和 1 表示。
  • vertex，记录上一层的顶点，也即已经被访问但其相连的顶点还没有被访问的顶点。当一层的顶点搜索完成后，我们还需要通过这一层的顶点来遍历与其相连的下一层顶点，这里我们用队列来记录上一层的顶点。
  • prev，记录搜索路径，保存的是当前顶点是从哪个顶点遍历过来的，比如 prev[4] = 1，说明顶点 4 是通过顶点 1 而被访问到的。

参考文献

https://zhuanlan.zhihu.com/p/95081559

 

https://blog.csdn.net/curry___/article/details/81742727