第三章：基础搜索算法回顾：BFS、DFS与Dijkstra
各位同学，欢迎来到第三章。在正式进入A*和RRT这些高级算法之前，我觉得有必要先回头看看那些最基础的东西。说白了，A*就是Dijkstra加了个启发式，RRT本质上也是DFS的变种。你想想看，地基不牢，后面盖什么楼？
这一章，我们就来聊聊三个老朋友：BFS、DFS和Dijkstra。我会结合我实际项目中的踩坑经历，帮你把这些算法的「脾气秉性」摸透。
3.1 广度优先搜索（BFS）
BFS，全称Breadth-First Search。它的核心思想很简单：一层一层地往外扩。就像往平静的湖面扔一颗石子，波纹一圈一圈地荡开。
我个人习惯用队列（Queue）来实现BFS。为什么？因为队列先进先出，正好符合「先探索近的，再探索远的」这个逻辑。
3.1.1 算法流程
- 把起点放入队列。
- 从队列取出一个节点，标记为已访问。
- 检查该节点是不是终点。如果是，结束。
- 如果不是，把它的所有未访问邻居加入队列。
- 重复步骤2-4，直到队列为空。
嗯，这里要注意：BFS只适用于无权图。如果每条边的代价不一样，BFS找到的「最短路径」可能不是真正的「最便宜路径」。我在一个仓储机器人项目里就吃过这个亏——明明BFS找到了路径，但机器人走起来就是比别人慢，后来才发现是忽略了不同路段的通行代价。
3.1.2 代码实现
from collections import deque
def bfs(graph, start, goal):
queue = deque([start])
visited = set([start])
parent = {start: None} # 记录路径
while queue:
current = queue.popleft()
if current == goal:
# 回溯路径
path = []
while current is not None:
path.append(current)
current = parent[current]
return path[::-1]
for neighbor in graph[current]:
if neighbor not in visited:
visited.add(neighbor)
parent[neighbor] = current
queue.append(neighbor)
return None # 没找到路径3.2 深度优先搜索（DFS）
DFS和BFS正好相反。它是一条道走到黑，撞了南墙再回头。用栈（Stack）来实现最顺手。
你可能会问：「DFS能找到最短路径吗？」答案是：不能保证。DFS找到的第一条路径，很可能不是最短的。但它有个好处——内存占用小。你想想看，BFS要存一整层，DFS只需要存一条路径。
3.2.1 算法流程
- 把起点压入栈。
- 从栈顶弹出一个节点，标记为已访问。
- 如果是终点，结束。
- 否则，把它的未访问邻居压入栈。
- 重复步骤2-4，直到栈为空。
3.2.2 代码实现
def dfs(graph, start, goal):
stack = [start]
visited = set([start])
parent = {start: None}
while stack:
current = stack.pop()
if current == goal:
path = []
while current is not None:
path.append(current)
current = parent[current]
return path[::-1]
for neighbor in graph[current]:
if neighbor not in visited:
visited.add(neighbor)
parent[neighbor] = current
stack.append(neighbor)
return None你看，代码和BFS几乎一样，只是把deque换成了list，popleft换成了pop。这就是数据结构的魅力——同样的逻辑，不同的容器，行为天差地别。
3.3 Dijkstra算法
终于到了Dijkstra。说实话，这是我个人最喜欢的算法之一。它解决了BFS和DFS的痛点——带权图的最短路径。
Dijkstra的核心思想是「贪心」：每次都选当前代价最小的节点去扩展。它需要一个优先队列（Priority Queue）来维护待探索的节点。
3.3.1 算法流程
- 初始化所有节点的代价为无穷大，起点代价为0。
- 把起点加入优先队列（按代价排序）。
- 从队列取出代价最小的节点。
- 如果该节点是终点，结束。
- 否则，更新它所有邻居的代价（如果新路径更短）。
- 重复步骤3-5，直到队列为空。
3.3.2 代码实现
import heapq
def dijkstra(graph, start, goal):
# graph: {node: [(neighbor, cost), ...]}
pq = [(0, start)] # (累计代价, 节点)
visited = set()
parent = {start: None}
cost_so_far = {start: 0}
while pq:
current_cost, current = heapq.heappop(pq)
if current in visited:
continue
visited.add(current)
if current == goal:
path = []
while current is not None:
path.append(current)
current = parent[current]
return path[::-1], current_cost
for neighbor, edge_cost in graph[current]:
new_cost = current_cost + edge_cost
if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:
cost_so_far[neighbor] = new_cost
parent[neighbor] = current
heapq.heappush(pq, (new_cost, neighbor))
return None, float('inf')3.4 三种算法对比
| 特性 | BFS | DFS | Dijkstra |
|---|---|---|---|
| 数据结构 | 队列 | 栈 | 优先队列 |
| 适用图 | 无权图 | 任意图 | 非负权图 |
| 最短路径 | 是（无权） | 否 | 是 |
| 内存消耗 | 高（存整层） | 低（存单路径） | 中（存优先队列） |
| 时间复杂度 | O(V+E) | O(V+E) | O((V+E)logV) |
看到这个表格，你应该能明白为什么实际项目中Dijkstra用得最多。它虽然比BFS慢一点，但能处理带权图，这才是真实世界的常态。
3.5 我的建议
如果你刚开始学路径规划，我建议你先把这三个算法手写三遍。别用IDE，就在纸上写伪代码。为什么？因为只有当你真正理解每个变量在什么时候变化，你才算真的懂了。
我记得有一次面试，面试官让我在白板上写Dijkstra。我刷刷刷写完了，他问了一句：「如果图里有100万个节点，你的代码会有什么问题？」我当时一愣，后来才意识到——visited集合用list还是set，性能差了一个数量级。这些细节，只有在实战中才会暴露。
好了，这一章就到这里。下一章我们进入A*算法——Dijkstra的「开挂版」。到时候你会发现，理解了Dijkstra，A*就是一层窗户纸。
公众号:蓝海资料掘金营，微信deep3321