若是从一二叉树树考虑，DFS就是先一路搜索到最左侧，然后逐渐返回上一节点，再搜索上一节点的子节点。有栈的思想。所以一般都会用递归的方式解决问题。
不同于BFS每次只找一层 ，先进先出的对列。而是对当前点cur进行递归，如果cur的临界点有效，就继续深搜递归，一直搜索到底为止。
一、DFS的一般步骤：
1、定义一个递归函数，在递归函数中，判断该点是否有效，（有时若是判定有效比较复杂，就单独写出一个isvalid函数判定该点是否有效。）如果有效，就对该点的相邻节点继续进行递归，一直进行到底为止。
2、对图中需要用递归函数的点，进行递归调用就行。
二、目前遇到的DFS的两种问题
2.1、有效路线问题
对于一些路线问题，相对比较难，要用栈记住路线，在搜索完一个点以后，需要逐级的弹出该点。所以在递归完以后，一定要pop出该点。
2.2.1、骑士周游问题
理解动态规划、BFS和DFS中的骑士周游问题：
nodeSet = set()
def knightTour(n,path,u,limit):
nodeSet.add(u)
path.append(u)
if n < limit:
nbrList = list(u.getConnections())
i = 0
done = False
while i < len(nbrList) and not done:
#先判断这个点是不是已经存在于nodeSet中
if nbrList[i] not in nodeSet:
#不在，则对这个点继续进行递归调用函数
done = knightTour(n+1,path,nbrList[i],limit)
i += 1
#如果遍历完这个节点，发现还是没有正确的路径，那么就把这个点从path中弹出
#并把点从nodeSet中弹出，对当前点的父节点的其余的子节点进行递归调用
if not done:
path.pop()
nodeSet.remove(u)
else:
done = True
return done
在搜索完该点的邻接点以后，需要返回上一节点去找上一节点的邻接节点，因此pop出当前节点，把上一节点留在栈顶，在递归的时候再弹出进行搜索。
2.2.2、经典的八皇后问题
解决这个问题，有四点需要注意：
-
1、如何表示皇后的位置。
这里参考中，是用一个长度为n初始化元素全为-1的列表pos来表示的。其中pos[i]表示第i行皇后的列数col。
比如搜索两次以后，pos=[3,6,-1,-1,-1,-1,-1,-1]就表示此时第1行皇后位置在第4列，第二行皇后位置在第7列。 -
2、如何找到新皇后的有效位置。
继续上面pos=[3,6,-1,-1,-1,-1,-1,-1]，在搜索到第三行时，此时就会对每一列col进行判定，如果此时col不与前面两行的皇后列数重复，并且不在一条斜线上，就是有效的。比如pos[2] = 2就是有效的，这时再对第四行进行递归调用。 -
3、搜索完一个点以后，如何返回上一个点
根据前面的pos的定义，在搜索到第3行第3个点时，就进行赋值pos[2]=2，此时pos=[3,6,2,-1,-1,-1,-1,-1]，然后对第四行调用递归函数。
当递归函数调用结束时，说明第3行第3个点已经搜索完了，此时应该搜索第3行的其余点，判断是否有效并且赋值。那么此时就应该令pos[2]=-1。
具体代码如下
if isvalid(pos,row,col):
#若有效，就把这一行皇后位置赋值为col
pos[row] = col
dfs(pos,row+1,res)
pos[row] = -1
- 4、输出结果如何表示
在搜索到底以后，就要按照题意输出一个有效的结果。然后把这个有效的结果，append到res列表中。在函数最后return res。
代码实现：
class Solution:
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
#定义输出结果列表
res = []
#定义一个判断皇后位置是否有效的函数，这个在递归函数中会用到
def isvalid(pos,row,col):
#若新皇后的列数col与前面任何一行的一个皇后的列数重复，或者斜着，都是无效的
for i in range(row):
if col == pos[i] or abs(row - i) == abs(col - pos[i]):
return False
return True
#先定义pos，长度为n，pos[i]代表第i行中皇后所处的列，其中每个元素初始化为-1
pos = []
for i in range(n):
pos.append(-1)
#定义递归函数，传入参数pos，n，res，返回一个有效结果out
#传入pos列表用来追踪已有的每行皇后的位置，传入n用来判断是否结束递归，
# 传入res用来存储有效结果out
def dfs(pos,row,res):
if row == n:
out = []
for i in range(n):
out.append(pos[i] * '.' + 'Q' + (n-1-pos[i]) * '.')
res.append(out)
return res
else:
for col in range(n):
if isvalid(pos,row,col):
#若有效，就把这一行皇后位置赋值为col
pos[row] = col
dfs(pos,row+1,res)
#对于row，col位置的搜索全部结束以后，就舍弃掉col，去找col+1是否有效，
#是否需要继续递归
pos[row] = -1
#调用递归函数，传入row为0
dfs(pos,0,res)
return res
2.2、二维数组中的一些问题
比如numIslands这道题，对于一些1相邻的点，递归搜索到底并且把1变成0以后，不需要逐级在返回时，把访问完的点再次进行弹出。那么就不用考虑这个pop的问题。
求节目标是有几个解时，用DFS。
题目见200. Number of Islands
代码实现：
class Solution:
def numIslands(self, grid):
if len(grid) == 0:
return 0
# 获取行列数
m = len(grid)
n = len(grid[0])
# 定义一个递归函数，传入一个有效点，visitred，
# 不返回值，但会把相邻的有效点坐标都添加进visited中去
def recur(location):
i = location[0]
j = location[1]
if i >= 0 and i <= m - 1 and j >= 0 and j <= n - 1 and grid[i][j] == '1':
grid[i][j] = '0'
for loc in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
recur(loc)
# 主函数，如果发现以后新的1，并且1的坐标不在visited中，num加1，并且对该点调用递归函数
num = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1' :
num += 1
recur((i, j))
return num
网友评论