深度优先搜索（DFS）算法详解 - 图解与Python实现

【免费下载链接】LeetCode-Py ⛽️「算法通关手册」：超详细的「算法与数据结构」基础讲解教程，从零基础开始学习算法知识，800+ 道「LeetCode 题目」详细解析，200 道「大厂面试热门题目」。 项目地址: https://gitcode.com/gh_mirrors/le/LeetCode-Py

深度优先搜索（Depth First Search，简称DFS）是图论中最基础也是最重要的算法之一。本文将从算法原理、实现方式到实际应用，全面讲解DFS算法，帮助读者彻底掌握这一核心算法。

一、DFS算法原理

深度优先搜索是一种用于遍历或搜索树或图结构的算法。它的核心思想是"一条路走到黑"：从起始节点开始，沿着一条路径尽可能深入地访问节点，直到无法继续前进时，再回溯到上一个未访问的节点，继续深入搜索。

DFS算法具有以下特点：

1. 采用回溯思想，优先深入探索路径
2. 访问顺序符合"后进先出"原则
3. 可以通过递归或栈结构实现
4. 时间复杂度通常为O(V+E)，其中V是顶点数，E是边数

二、DFS算法实现方式

2.1 递归实现

递归是DFS最自然的实现方式，它直接利用了计算机的函数调用栈来保存访问路径。

class Solution:
    def dfs_recursive(self, graph, u, visited):
        print(u)                        # 访问节点
        visited.add(u)                  # 标记已访问

        for v in graph[u]:              # 遍历邻接节点
            if v not in visited:       # 如果未访问过
                self.dfs_recursive(graph, v, visited)  # 递归访问

递归实现的优点：

• 代码简洁直观
• 直接利用系统栈，无需额外数据结构
• 适合树形结构的深度遍历

2.2 栈实现（非递归）

我们也可以显式地使用栈结构来实现DFS，避免递归可能带来的栈溢出问题。

class Solution:
    def dfs_stack(self, graph, u):
        print(u)                            # 访问节点
        visited, stack = set(), []          # 使用集合记录访问，栈保存节点
        
        stack.append([u, 0])                # 存入节点和邻接节点索引
        visited.add(u)                      # 标记已访问
    
        while stack:
            u, i = stack.pop()              # 取出节点和邻接索引
            
            if i < len(graph[u]):
                v = graph[u][i]             # 获取邻接节点
                stack.append([u, i + 1])    # 更新索引重新入栈
                if v not in visited:       # 如果未访问
                    print(v)                # 访问节点
                    stack.append([v, 0])    # 新节点入栈
                    visited.add(v)         # 标记已访问

栈实现的优势：

• 避免递归深度过大导致的栈溢出
• 可以精确控制遍历过程
• 适合大规模图遍历

三、DFS算法应用实例

3.1 岛屿数量问题

问题描述：给定一个由'1'(陆地)和'0'(水)组成的二维网格，计算岛屿的数量。岛屿被水包围，且通过水平或垂直相邻的陆地连接形成。

DFS解法思路：

1. 遍历网格中的每个点
2. 当遇到'1'时，启动DFS
3. 在DFS中将访问过的'1'标记为'0'
4. 每次完整的DFS计数为一个岛屿

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(i, j):
            if i<0 or i>=len(grid) or j<0 or j>=len(grid[0]) or grid[i][j] == '0':
                return
            grid[i][j] = '0'  # 标记为已访问
            # 四个方向DFS
            dfs(i+1, j)
            dfs(i-1, j)
            dfs(i, j+1)
            dfs(i, j-1)
        
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    dfs(i, j)
                    count += 1
        return count

3.2 图的克隆问题

问题描述：深度复制一个无向连通图，新图中的节点不应是原节点的引用。

DFS解法思路：

1. 使用哈希表记录原节点和克隆节点的映射
2. DFS遍历原图，为每个节点创建克隆
3. 递归处理邻接节点

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return node
        visited = {}

        def dfs(node):
            if node in visited:
                return visited[node]
            
            clone = Node(node.val, [])
            visited[node] = clone
            for neighbor in node.neighbors:
                clone.neighbors.append(dfs(neighbor))
            return clone

        return dfs(node)

四、DFS算法复杂度分析

DFS算法的时间复杂度主要取决于图的结构：

• 邻接表表示：O(V+E)
• 邻接矩阵表示：O(V²)

空间复杂度：

• 递归实现：O(h)，h为递归深度
• 栈实现：O(V)

五、DFS与BFS的比较

特性	DFS	BFS
数据结构	栈/递归	队列
空间复杂度	O(h)	O(w)
适用场景	路径查找、拓扑排序	最短路径、层级遍历
实现方式	递归或显式栈	队列

六、DFS的优化技巧

1. 记忆化搜索：存储已计算的结果避免重复计算
2. 剪枝：提前终止不可能产生最优解的分支
3. 迭代加深：结合BFS思想，限制搜索深度
4. 双向DFS：从起点和终点同时搜索

通过本文的系统讲解，相信读者已经对DFS算法有了全面的理解。DFS作为基础算法，在树/图遍历、路径查找、连通性分析等问题中都有广泛应用，是每个程序员必须掌握的算法之一。

【免费下载链接】LeetCode-Py ⛽️「算法通关手册」：超详细的「算法与数据结构」基础讲解教程，从零基础开始学习算法知识，800+ 道「LeetCode 题目」详细解析，200 道「大厂面试热门题目」。 项目地址: https://gitcode.com/gh_mirrors/le/LeetCode-Py