DFS、BFS与01BFS算法详解与对比

1. 引言

在图论和树形结构的遍历与搜索中，深度优先搜索（DFS）、广度优先搜索（BFS）以及01BFS是三种基础且至关重要的算法。它们不仅是解决许多经典问题（如路径查找、连通性判断、最短路径等）的核心工具，也是理解更复杂算法（如Dijkstra、A*）的基石。本文将深入剖析这三种算法的原理、实现、应用场景及性能差异，并通过代码示例帮助读者建立清晰的认识。

2. 深度优先搜索（DFS）

2.1 核心思想与实现

深度优先搜索遵循“一条路走到黑，碰壁再回头”的策略。它从起始节点出发，尽可能深地探索图的分支，直到当前路径上的所有节点都被访问过，然后回溯到上一个分叉点，选择另一条未探索的路径继续深入。

递归实现（隐式栈）：

def dfs_recursive(graph, node, visited):
    if node not in visited:
        visited.add(node)
        print(node)  # 处理节点
        for neighbor in graph[node]:
            dfs_recursive(graph, neighbor, visited)
示例图（邻接表）
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
visited = set()
dfs_recursive(graph, 'A', 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 reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

2.2 时间复杂度与空间复杂度

• 时间复杂度：O(V + E)，其中 V 为顶点数，E 为边数。每个顶点和每条边最多被访问一次。
• 空间复杂度：O(V)，主要消耗在递归调用栈（递归实现）或显式栈（迭代实现）以及访问标记集合上。

2.3 典型应用场景

• 拓扑排序：用于有向无环图（DAG）的任务调度。
• 连通分量检测：判断无向图的连通性，或寻找有向图的强连通分量（配合Kosaraju或Tarjan算法）。
• 路径查找与回溯：如迷宫求解、八皇后问题、数独等。
• 环检测：在遍历过程中判断图中是否存在环。

3. 广度优先搜索（BFS）

3.1 核心思想与实现

广度优先搜索采用“层层推进”的策略。它从起始节点开始，先访问所有直接相邻的节点（第一层），然后再访问这些相邻节点的相邻节点（第二层），以此类推，直到遍历完所有可达节点。

迭代实现（队列）：

from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
while queue:
node = queue.popleft()
print(node)  # 处理节点
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)

3.2 时间复杂度与空间复杂度

• 时间复杂度：O(V + E)，与DFS相同。
• 空间复杂度：O(V)，队列在最坏情况下可能需要存储所有顶点。

3.3 典型应用场景

• 无权图最短路径：BFS首次访问到目标节点时经过的路径就是最短路径（边权为1）。
• 层次遍历：如二叉树的层序遍历，社交网络中的“好友度”计算。
• 广播网络：模拟消息或病毒在网络中的传播过程。
• 迷宫最短路径：在网格迷宫中寻找从起点到终点的最短步数。

4. 01BFS（0-1广度优先搜索）

4.1 核心思想与实现

01BFS是BFS的一种变体，专门用于处理边权只有两种可能值（通常为0和1）的图。它使用一个双端队列（deque）来保证始终以距离起点的非递减顺序处理节点，从而在线性时间内求出最短路径。

算法步骤：

1. 初始化距离数组dist，起点距离为0，其他为无穷大。使用双端队列deque，将起点加入队列。
2. 当队列不为空时，弹出队首节点u。
3. 遍历u的所有邻接边(u, v, w)，其中w为边权（0或1）。
4. 如果dist[u] + w < dist[v]，则更新dist[v] = dist[u] + w。
   • 若w == 0，将v加入队首（保证优先处理距离更小的节点）。
   • 若w == 1，将v加入队尾。

Python实现：

from collections import deque
def zero_one_bfs(graph, start):
"""graph: 邻接表，graph[u] = [(v, weight), ...]，weight为0或1"""
n = len(graph)
dist = [float('inf')] * n
dist[start] = 0
dq = deque([start])
while dq:
    u = dq.popleft()
    for v, w in graph[u]:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            if w == 0:
                dq.appendleft(v)  # 权值为0，加入队首
            else:
                dq.append(v)      # 权值为1，加入队尾
return dist</code></pre>
4.2 时间复杂度与空间复杂度
时间复杂度：O(V + E)，每个节点和每条边最多被处理一次。
空间复杂度：O(V)，用于存储距离数组和双端队列。
4.3 典型应用场景
网格迷宫带成本移动：某些方向移动代价为0（如直行），某些方向代价为1（如转弯）。
电路布线：在网格上布线，穿过某些区域（如已有线路）代价为0，穿过空白区域代价为1。
双端队列优化的最短路径：任何边权仅为0或1的图的最短路径问题。
5. 三种算法对比
特性
DFS
BFS
01BFS
数据结构
栈（递归/迭代）
队列
双端队列（deque）
遍历顺序
深度优先
广度优先（层序）
按距离非递减（0权优先）
最短路径
不保证（无权图）
保证（无权图）
保证（0-1权图）
空间开销
O(树高) / O(V)
O(最宽层) / O(V)
O(V)
适用图类型
通用
通用
边权仅为0或1
经典问题
回溯、拓扑排序、连通分量
层序遍历、无权图最短路径
0-1权图最短路径、网格转弯问题
6. 总结与选择建议
DFS、BFS和01BFS各有其擅长的领域：
需要探索所有可能解或进行回溯（如排列组合、迷宫所有路径）：优先考虑DFS。
寻找最短步数或最近关系（如社交网络好友度、无权图最短路径）：使用BFS。
图中边权只有0和1，且需要求最短路径：01BFS是最优选择，其效率高于通用的Dijkstra算法。
理解这三种基础算法的内在联系与区别，是迈向更高级图论算法（如Dijkstra、Bellman-Ford、A*）的关键一步。在实际编码面试或项目开发中，根据问题特征快速准确地选择并实现合适的搜索算法，是程序员必备的核心能力。

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/QY8765/article/details/163017876