算法原理
深度优先搜索是一种图的遍历算法,遍历每个节点一次,一般叫做DFS(Depth First Search)。
算法步骤如下:
1.访问节点v
2.再访问节点v的下一个未被访问的邻接点,并且置为当前节点,继续重复第1、2步骤;如果v的所有邻接点均访问过,则退回前一个含有未被访问过的邻接点的节点,重复第1、2步骤,直到所有节点都已访问过
大致思想是这样,用到的数据结构是栈,把访问过的节点压入栈中,并且标记节点已被访问,再遍历栈顶的未访问的邻接点,如果栈顶的邻接点都被访问过,就弹出栈,直到栈空,则遍历了一个联通的图。下面是用树结构画的动图来展现深搜的思想。
Python实现深搜算法
DFS实现有两种方式,一种是利用栈的数据结构,直接循环实现(非递归);另一种是使用递归。
以二叉树的中序遍历为例,分别用两种方法实现。
递归方式容易理解,比较好实现:
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = [] # 存储遍历结果
def dfs(node): # 中序遍历以node为根节点的树
if not node: # node节点为空则结束
return
dfs(node.left)
ans.append(node.val)
dfs(node.right)
dfs(root)
return ans
中序遍历的函数 dfs
,只要node节点非空,则递归遍历其左子树,然后访问根节点,最后递归遍历右子树。
非递归方式:
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = [] # 存储遍历结果
stk = [] # 栈,用于存储遍历的路径
node = root # 遍历的根节点
while stk or node: # 只要stk非空或node节点非空则说明还没遍历完
while node: # node节点非空
stk.append(node) # 则把node节点入栈,
node = node.left # 并且继续遍历其左子树
node = stk.pop() # node为空则说明遍历完了左子树,要返回上一个父节点,从stk弹出节点
ans.append(node.val) # 访问根节点
node = node.right # 接着遍历右子树
return ans
在树的深搜当中,递归方式容易理解容易实现,但效率没有循环好。栈迭代虽然提高了效率,但里面嵌套了一层循环,不容易理解,所以结合一些其他人的实现方式和栈的特点,有另一种写法:
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = [] # 存储遍历结果
stk = [root] # 栈,用于存储遍历的路径
while stk: # 栈非空
node = stk.pop() # 弹出一个节点
if node is None:
continue
if isinstance(node, TreeNode): # 如果node是一个树的节点
stk.extend([node.right, node.val, node.left]) # 中序遍历的顺序是(左根右),压入栈中,则访问顺序就要反过来,根节点是值,而不是树节点
else:
ans.append(node) # 访问根节点
return ans
这种写法理解后是很好写的,而且效率相对来说更高。对于前序、后序遍历也都可以类似的实现,只需改一下节点访问的顺序。
应用
很多地方都能使用DFS深搜解决问题,下面是一些例子,可以去尝试做一做。
有的时候用深搜也容易超时,这个时候要考虑下优化,比如记忆化深搜,就是把一些计算的结果保存下来,下次还会用到时就可以直接调用,节省时间。
Leetcode题目:矩阵中的最长递增路径
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
if not matrix:
return 0
m, n = len(matrix), len(matrix[0]) # 矩阵数组的行列形状
max_len = 1 # 记录最大长度
dfs_dict = {} # 没有使用LRU缓存装饰器时,可以用一个字典来保存函数的结果
# @lru_cache(None) # LRU缓存机制,目的是记忆之前已经调用过的函数结果,再次使用时可以直接使用
def dfs(i, j): # 在位置i,j进行深搜,返回这个位置的最长长度
L = 1 # 本身的长度为1
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 四个方向
for dx, dy in dirs:
ii, jj = i + dx, j + dy # 新的坐标
if 0 <= ii < m and 0 <= jj < n and matrix[ii][jj] > matrix[i][j]: # 新的坐标ii,jj合法并且值大于当前i,j
if (ii, jj) not in dfs_dict:
dfs_dict[(ii, jj)] = dfs(ii, jj) + 1 # 判断ii,jj的最长长度是否已经在记忆字典中
L = max(L, dfs_dict[(ii, jj)]) # 去最长的长度
return L
for i in range(m):
for j in range(n):
l = dfs(i, j) # 循环每个位置的最长长度
if l > max_len:
max_len = l
return max_len
评论区