---

深度优先搜索（Depth First Search, DFS）是图论中一种常用的遍历或搜索算法，适用于树、图以及其他结构化数据。它以“深”为核心思想，尝试沿着一个方向一直走到底，然后回溯寻找其他路径。本文将以详细的步骤与示例，帮助初学者掌握DFS的原理与实现。

---

一、什么是DFS？

DFS 是一种系统地探索图中所有节点的算法。它的特点是“优先深入”，即尽可能走到某条路径的尽头才会回溯寻找其他可能的路径。

核心特点：

1. 递归特性：DFS可以用递归（函数自调用）实现。
2. 栈的使用：在递归中，函数调用栈自动管理节点状态；非递归版本中，我们需要显式使用栈来模拟递归过程。
3. 路径回溯：当某条路径探索完成后，回退到上一个节点继续探索未访问的邻居。

---

二、DFS 的应用场景

1. 图的遍历：如找到所有节点，或判断图是否连通。
2. 路径搜索：如找到从起点到终点的所有路径。
3. 问题求解：如迷宫求解、组合问题（全排列、子集）、拓扑排序等。
4. 连通性判断：如判断一个图中有多少个连通分量。

---

三、DFS 的实现步骤

1. 准备工作：

• 输入：通常是一张图，用邻接表或邻接矩阵表示。
• 记录访问状态：用一个布尔数组 visited 标记每个节点是否访问过，避免重复遍历。

2. 递归实现：

递归版本最为直观，步骤如下：

1. 从起始节点出发，标记为已访问。
2. 依次递归访问当前节点的所有未访问邻居。
3. 所有邻居访问完成后，递归自动回溯。

def dfs_recursive(graph, node, visited):
    # 标记当前节点为已访问
    visited[node] = True
    print(f"访问节点: {node}")

    # 递归访问所有未访问的邻居
    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs_recursive(graph, neighbor, visited)

3. 非递归实现（用栈模拟）：

非递归实现需要显式使用栈管理节点访问状态。

1. 初始化一个栈，将起始节点压入栈。
2. 取出栈顶节点并标记为已访问。
3. 将所有未访问邻居压入栈。
4. 重复步骤2和3直到栈为空。

def dfs_iterative(graph, start):
    visited = [False] * len(graph)
    stack = [start]

    while stack:
        node = stack.pop()
        if not visited[node]:
            visited[node] = True
            print(f"访问节点: {node}")

            # 将未访问的邻居压入栈
            for neighbor in reversed(graph[node]):  # reversed 确保顺序一致
                if not visited[neighbor]:
                    stack.append(neighbor)

---

四、完整示例：图的遍历

假设有一张图，使用邻接表表示如下：

graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [1],
    4: [1],
    5: [2]
}

递归实现：

# 初始化访问数组
visited = [False] * len(graph)

# 从节点 0 开始遍历
dfs_recursive(graph, 0, visited)

输出：

访问节点: 0
访问节点: 1
访问节点: 3
访问节点: 4
访问节点: 2
访问节点: 5

非递归实现：

dfs_iterative(graph, 0)

输出（访问顺序可能不同）：

访问节点: 0
访问节点: 2
访问节点: 5
访问节点: 1
访问节点: 4
访问节点: 3

---

五、DFS 的复杂度分析

1. 时间复杂度：

   • 图的每个节点被访问一次，每条边被检查一次。
   • 时间复杂度为 O(V + E)，其中 V 是节点数，E 是边数。

2. 空间复杂度：

   • 递归版本需要 O(V) 的递归栈空间。
   • 非递归版本需要 O(V) 的栈存储节点。

---

六、DFS 中的关键问题

1. 如何避免死循环？

在环形结构或无向图中，DFS 可能会陷入死循环。因此，使用 visited 标记非常重要。

2. 如何找路径？

通过记录当前节点的父节点或路径，可以在回溯时重构完整路径。

---

七、延伸：DFS 与 BFS 的区别

特点	DFS	BFS
搜索策略	深度优先，沿路径走到底回溯	广度优先，按层级展开
实现方式	栈（递归或显式栈）	队列
适用场景	解决深度问题、路径枚举	找最短路径、层次遍历

---

八、总结

深度优先搜索是一种简单但功能强大的算法，广泛应用于图论和组合问题。通过理解其递归和非递归实现，以及学会在不同场景中应用，您将发现它在算法设计中的不可或缺性。

练习是掌握算法的关键。建议从简单的图遍历入手，逐步挑战复杂问题，例如迷宫求解或全排列生成。希望这篇文章能让您轻松上手 DFS！