算法分析 | 一文理解搜索算法-彻底入门DFS

前言

搜索是一种适用性非常广泛的算法。很多我们实际遇到的问题，数据量可能不会太大，都可以暴力搜索一把来解决。

其实这个算法网上也很多但是都讲的比较复杂很多人也只能看一个前面的东西后面的其实看不懂。也有很多文章讲的不是太精炼，讲不出个所以然来。所以小编今天就利用这篇文章来带大家先入门搜索算法。最简单的 DFS 相当于一个暴力搜索算法。

如果不了解暴力的可以看看前面写的这篇文章：

算法分析 | 枚举+优化套路入门，万能的暴力法

基本上遇到的很多题目暴力都能解决，毕竟 CPU 处理的速度这么快。

搜索DFS正文

搜索算法是属于一种比较基础的算法，相当于万丈高楼的第一层，也是后期学习的一些高级算法的基础部分,搜索算法分为深度优先搜索（ Depth First Search , DFS）和广度优先搜索（Breadth First Search, BFS）这两种。DFS 相对简单一点那就从 DFS 开始入门吧。

说到这个搜索算法就要讲到图的问题，有学过离散数学或者数据结构的都知道，图是一个点集合加上一个边的集合一个边对应两个定点，属于一种二元关系。

如果你没学过的话上面那句话省略，直接看这里：举个例子讲，微信朋友圈可以看成一个很大的图，每个人都是一个顶点，彼此是好友彼此的朋友圈就能看到，相当于彼此的可达的。这个问题一抽象化就能算出只要你的朋友圈连接着多少人了。假如你发张你的自拍，你的每个好友都转发，你好友的好友也都转发.....然后全世界都知道你长什么样子了。 所以小编的文章能怎么样还是需要你们这些第一批种子用户的。

直接形象化的上图

了解什么是图了，那么我们从图的遍历开始讲，给定一个包含N个顶点的图，以及图上的M条边。让你遍历图中的每一个顶点恰好一次。图的遍历有很多用途，比如判断一个图是不是连通的。和判断你的微信能不能连接全世界是一样的。

我们说说到一个算法首先考虑的是他的实现，要实现的话就得要存储，看问题我们是有两个集合（点集和边集）集合一般的思想就是通过一个数组集合来存储，通过对点集的标号，找到与数组下标的关系，我们就能实现存储。

其实我们有两种方法来存储边集。一种叫做邻接矩阵表示法，另一种叫邻接表表示法。

邻接矩阵是说我们用一个二维矩阵A来表示边集。Aij=0表示顶点i和顶点j之间不存在边，Aij=1表示顶点i和顶点j之间存在边。如果我们用邻接矩阵表示上图，是这个样子：

在程序中，我们一般用一个二维数组来表示邻接矩阵: int a[N+1][N+1]。a[i][j]==1表示i和j之间有边相连，a[i][j]==0表示i和j之间没有边相连。

邻接表是图中的每一个顶点i都有一个线性表，保存与i相连的顶点编号。

如果我们用邻接矩阵表示上图，是这个样子：

在程序中，我们一般用一个数组嵌套vector的方法来表示邻接表：vector<int> g[N+1]，里面保存着每一个与i相邻的顶点编号。

上面讲了什么是搜索，如何存储一个图。那么重头戏来了我们不妨设从1号顶点起始。在搜索过程中，我们维护一个布尔数组bool visited[N+1]，这个数组用来表示每个顶点是不是已经遍历过了。visited[i]==true表示顶点i已经遍历过了，visited[i]==false表示i还没有遍历过。DFS一般我们可以用递归实现，如果采用邻接矩阵，伪代码如下：

当我们执行DFS(1)的时候，程序就会开始从1号节点开始遍历，每一次都对搜索过的书标记一直到全部被标记完为止。而每一次DFS执行中都要i循环从1到N遍历一遍。所以整个复杂度是O(N^2)的。

了解了大概，看官们是不跃跃欲试了呢。那就看看我下面的栗子，源码的获取方式在文章末尾。小编写了两种方法。

举个栗子

小提示：

这道题的基本思路就是从1号节点出发开始遍历。如果遍历结束时所有visited[]数组的值全都是true，那么就说明整个图是连通的，否则就不是。

C语言代码是这个样子：

C++代码使用STL：

最后一点，就是 DFS 运用的不同的场景限制会有些不同，有些时候需要去掉重复的路径，还有的是预防存在环路，代码死循环，或者没有找完的情况。如果有问题在后台留言。

代码获取

为了方便看官们的代码获取，小编在微信公众号后台放了获取方式。微信搜索：「挑战算法与程序设计」订阅此号，然后后台回复： 搜索01 即可获得两种方式的代码。

公众号出了这个还有更加精彩的哟~！、