1. 什么是深度优先搜索？
深度优先搜索（Depth-First Search, DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
2. 算法思想
DFS 的核心思想是 “一路走到黑，不撞南墙不回头”。想象你在一个迷宫里，你选择一条路一直走，直到遇到死胡同，然后返回到上一个路口，选择另一条你没走过的路继续探索。
为了实现这一点，我们需要一个机制来记录我们访问过的节点，以避免重复访问和无限循环。通常我们使用一个 visited 集合来存储已访问的节点。
DFS 主要有两种实现方式：
- 递归 (Recursion)：利用函数调用栈来隐式地管理节点的访问顺序。这是最直观和常见的实现方式。
- 迭代 (Iteration)：显式地使用一个栈 (Stack) 数据结构来模拟递归的过程。
3. Python 代码示例
我们先定义一个图。这里使用邻接表（Adjacency List）来表示图，它是一个字典，其中键是节点，值是与该节点相邻的节点列表。
# 定义一个图的邻接表表示
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print("图的邻接表表示:")
for node, neighbors in graph.items():
print(f"{node}: {neighbors}")
图的邻接表表示:
A: ['B', 'C']
B: ['A', 'D', 'E']
C: ['A', 'F']
D: ['B']
E: ['B', 'F']
F: ['C', 'E']
3.1 递归实现
visited_recursive = set() # 用于存储已访问过的节点
def dfs_recursive(graph, node):
"""递归实现的深度优先搜索"""
if node not in visited_recursive:
print(node, end=' ') # 访问节点
visited_recursive.add(node) # 标记为已访问
# 递归访问邻居节点
for neighbor in graph[node]:
dfs_recursive(graph, neighbor)
print("递归DFS遍历结果: ")
dfs_recursive(graph, 'A') # 从节点 'A' 开始遍历
递归DFS遍历结果:
A B D E F C
3.2 迭代实现
def dfs_iterative(graph, start_node):
"""迭代实现的深度优先搜索"""
visited_iterative = set() # 存储已访问的节点
stack = [start_node] # 用列表模拟栈，初始放入起始节点
while stack: # 当栈不为空时循环
node = stack.pop() # 弹出栈顶元素
if node not in visited_iterative:
print(node, end=' ') # 访问节点
visited_iterative.add(node) # 标记为已访问
# 将邻居节点逆序压入栈中，以保证访问顺序与递归版本一致
# (因为pop会弹出最后的元素，所以逆序放入后，第一个邻居会最后被pop)
for neighbor in reversed(graph[node]):
if neighbor not in visited_iterative:
stack.append(neighbor)
print("迭代DFS遍历结果: ")
dfs_iterative(graph, 'A') # 从节点 'A' 开始遍历
迭代DFS遍历结果:
A B D E F C
4. 复杂度分析
假设图有 V 个节点 (Vertices) 和 E 条边 (Edges)。
时间复杂度: O(V + E)。
- 每个节点最多被访问一次 (入栈/递归调用一次)，所以是 O(V)。
- 每条边最多被探索一次，所以是 O(E)。
- 总的时间复杂度是 O(V + E)。
空间复杂度: O(H)，其中 H 是图中的最大深度。
- 在递归实现中，空间复杂度取决于递归调用的最大深度。在最坏的情况下（例如一个链状的图），H 可能等于 V。
- 在迭代实现中，空间复杂度取决于栈中存储的节点数，同样在最坏情况下是 O(V)。
5. 应用场景
DFS 是一个非常基础且强大的算法，应用广泛，例如：
- 寻找路径：查找从一个节点到另一个节点是否存在路径。
- 检测环：判断图中是否存在环。在有向图和无向图中都可以使用。
- 拓扑排序 (Topological Sorting)：对于有向无环图 (DAG)，可以得到一个线性的节点排序。
- 寻找连通分量 (Connected Components)：在无向图中，可以用DFS找到所有的连通子图。
- 解决迷宫问题：从起点开始，使用DFS探索所有可能的路径直到找到出口。
代码链接：
https://github.com/zhouruiliangxian/Awesome-demo/tree/main/Data_Structures_and_Algorithms