算法-DFS

前言

深度优先搜索(Depth-First Search, DFS)是一种用于遍历或搜索树或图的算法。与广度优先搜索不同，DFS 会尽可能深地搜索树的分支，直到不能再深入为止，然后回溯到前一个节点，继续搜索其他分支。

DFS算法基本原理

DFS 的基本思想非常简单：

从起始节点开始，标记该节点为已访问
对该节点的每个未访问的相邻节点，递归地应用DFS
如果没有未访问的相邻节点，则回溯

DFS 可以用递归或栈来实现。递归实现更为简洁，而栈实现则能更好地控制内存使用。

递归实现

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    
    # 标记当前节点为已访问
    visited.add(node)
    print(node)  # 处理当前节点
    
    # 访问所有未访问的邻居节点
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

栈实现

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node)  # 处理当前节点
            
            # 将所有未访问的邻居节点加入栈中
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

DFS的应用场景

DFS 在许多问题中都有应用，包括：

寻找图中的连通分量
拓扑排序
检测环
路径查找
解决迷宫、数独等问题
排列组合问题

DFS在LeetCode中的应用

在 LeetCode 上，有很多问题可以用 DFS 解决。下面介绍几个经典例题：

例题1：岛屿数量（LeetCode 200）

问题描述：给定一个由 ‘1’（陆地）和 ‘0’（水）组成的二维网格，计算岛屿的数量。岛屿由相邻的陆地连接而成，相邻指上下左右四个方向。

解法：使用 DFS 遍历网格，每当遇到一个陆地，就用 DFS 标记与其相连的所有陆地为已访问，计数加1。

def numIslands(grid):
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    def dfs(i, j):
        # 超出边界或已访问或是水域，则返回
        if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] != '1':
            return
        
        # 标记为已访问
        grid[i][j] = '#'
        
        # 搜索四个方向
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)
    
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)
    
    return count

例题2：路径总和（LeetCode 112）

问题描述：给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，使得路径上所有节点值相加等于目标和。

解法：使用 DFS 遍历二叉树的所有路径，判断是否存在满足条件的路径。

def hasPathSum(root, targetSum):
    if not root:
        return False
    
    # 如果是叶子节点，检查当前值是否等于剩余的和
    if not root.left and not root.right:
        return root.val == targetSum
    
    # 递归检查左右子树
    return (hasPathSum(root.left, targetSum - root.val) or 
            hasPathSum(root.right, targetSum - root.val))

例题3：全排列（LeetCode 46）

问题描述：给定一个不含重复数字的数组，返回其所有可能的全排列。

解法：使用 DFS 来生成所有可能的排列。

def permute(nums):
    result = []
    
    def dfs(nums, path):
        if not nums:
            result.append(path)
            return
        
        for i in range(len(nums)):
            dfs(nums[:i] + nums[i+1:], path + [nums[i]])
    
    dfs(nums, [])
    return result

例题4：单词搜索（LeetCode 79）

问题描述：给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中”相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

解法：使用 DFS 探索网格中的所有可能路径。

def exist(board, word):
    if not board or not board[0]:
        return False
    
    rows, cols = len(board), len(board[0])
    
    def dfs(i, j, k):
        # 超出边界或字符不匹配，则返回False
        if i < 0 or i >= rows or j < 0 or j >= cols or board[i][j] != word[k]:
            return False
        
        # 如果已经匹配完所有字符，返回True
        if k == len(word) - 1:
            return True
        
        # 记录当前字符，并标记为已访问
        temp, board[i][j] = board[i][j], '#'
        
        # 搜索四个方向
        found = (dfs(i+1, j, k+1) or dfs(i-1, j, k+1) or 
                 dfs(i, j+1, k+1) or dfs(i, j-1, k+1))
        
        # 回溯，恢复字符
        board[i][j] = temp
        return found
    
    for i in range(rows):
        for j in range(cols):
            if dfs(i, j, 0):
                return True
    
    return False

DFS的优缺点

优点

实现简单，代码简洁
空间复杂度较低（但在最坏情况下可能是 $O(n)$ ）
适合找到所有可能的解决方案
在某些场景下比 BFS 更高效

缺点

容易陷入深度较大的分支而导致效率问题
可能无法找到最短路径（这是 BFS 的强项）
在处理环形结构时需要额外的处理

后记

深度优先搜索是一种强大而灵活的算法，在解决许多复杂问题时非常有效。通过在 LeetCode 上实践 DFS 算法，可以更好地理解其工作原理和应用场景。掌握 DFS 对于提高算法解题能力和理解图论问题至关重要。