DFS 算法解析

https://www.datacyber.com数新网络让每个人享受数据的价值

01 概念解析

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点。事实上，深度优先搜索属于图算法的一种，其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。沿着树的深度遍历树的节点，尽可能更深的搜索树的分支，当节点的所在边都已经被搜寻过或者在搜索时节点不满足条件，搜索将回溯到发现到节点的那条边的起始节点，整个进程都会反复进行直到所有节点都被访问到为止。

02 案例分析

例子：

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题

研究的是如何将 n 个皇后放置在 n*n 的棋盘上，并且使皇后彼此之间不能相互攻击。

例如:如果在一个 4x4 的棋盘中

那么只存在以上两种不同的放置方式来使棋子之间不互相攻击。

应该怎么找出任意大小的棋盘中所有的解？

可以使用 dfs 来对所有的可能方案进行一一尝试，将可达的情况加入到一个结果数组中找出所有的解。

dfs 的实现思路可以通过一个树结构体现：

1）每一行，选一个格子置为"Q"，一行一行往下选，第一行有四种选择。

2）再选下一行的皇后时，为了避免和之前所选的列冲突，有三种选择。

3）继续选下去，可能会遇到对角线冲突，得不出合法的解，需要撤销当前放置的棋子重新选择下一个位置放置。 

dfs 函数的出口：当前所遍历的行是棋盘的最后一行时结束。

而这个例子中需要考虑的最重要的是如何剪枝，其中同一行或同一列比较好解决，同一斜线该怎么解决？

首先可以通过创建一个二维数组来模拟一个棋盘：

这个时候我们可以知道通过二维数组不仅构造了一个棋盘，同时也构建一个直角坐标系。获取棋盘上 game[x][y]的值是"."还是"Q" 相当于在直角坐标系中(x,y)的取值在直角坐标系中我们可以通过 y=kx+b 来判断两个点是否在同一条直线上, b=1 , k=-1 或者 1，即直线：y=x+1 或者 y=-x+1。那么在这个棋盘上我们可以通过 col-row 以及 col+row 是否存在来判断对角线能不能放置棋子。

vertical、backwardSlash、forwardSlash 均为 Set 集合,backwardSlash 代表之前所放置的所有皇后的反对角线"\"上的坐标,forwardSlash 代表正对角线"/"上的坐标。例如：一个皇后棋子的反对角线上(y=-x+1)总满足一个条件即: x+y=1 => row+col=定值。同理，正对角线上(y=x+1)总满足一个条件即: x-y=-1 => row-col==定值。只要满足 backwardSlash.has(row + col)或 forwardSlash.has(row - col) 就说明当前所要放置的位置在之前已放置的皇后的对角线上此时就不能放置。之所以使用 Set 集合是因为只要 Set 中存在这个定值，不管是在哪一次遍历添加进去的，那么在之后的放置位置中这个位置所表示的直线都不能有棋子。

因此每一次需要执行的函数体：

因此这个问题就可以通过 dfs 将所有可能的放置方法遍历出来，并根据写好的函数体进行剪枝排除错误的放置方式，完整代码：