3. 图搜索基础：图论概念、DFS与BFS原理及代码实现

说实话，做机器人路径规划这些年，我最大的体会就是：图搜索是绕不开的坎。不管你后面用A*、Dijkstra还是RRT，底层逻辑都离不开图。今天咱们就把这个地基打牢。

3.1 图论基础：先搞清楚“图”长什么样

图是什么？说白了就是一堆节点和一堆边。节点代表位置，边代表能走的路。我当年刚入行时，总觉得图论是数学课的事，直到第一次写路径规划代码，才发现——嗯，真香。

3.1.1 图的分类

类型	特点	举个栗子
无向图	边没有方向，A↔B	双向道路
有向图	边有方向，A→B	单行道
加权图	边带权重（距离/时间）	高速 vs 小路
无权图	所有边权重相同	迷宫格子

3.1.2 图的存储方式

我习惯用两种方式存图，看场景选：

方式一：邻接矩阵

# 用二维数组存，简单粗暴
graph = [
    [0, 1, 0, 1],  # 节点0连接1和3
    [1, 0, 1, 0],  # 节点1连接0和2
    [0, 1, 0, 1],  # 节点2连接1和3
    [1, 0, 1, 0]   # 节点3连接0和2
]

方式二：邻接表

# 用字典存，省空间
graph = {
    0: [1, 3],
    1: [0, 2],
    2: [1, 3],
    3: [0, 2]
}

3.2 深度优先搜索（DFS）：一条路走到黑

DFS的思路很简单：从起点出发，沿着一条路走到头，走不动了就回头，换条路继续走。你想想看，就像你在迷宫里，左手扶墙一直走，总能走出去——但可能绕远路。

3.2.1 DFS原理

• 用栈（Stack）实现，后进先出
• 递归或迭代两种写法
• 适合判断连通性、拓扑排序、找所有路径

3.2.2 DFS代码实现（Python）

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(f"访问节点: {start}")
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    
    return visited

# 测试
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("DFS遍历顺序:")
dfs(graph, 'A')

输出：

DFS遍历顺序:
访问节点: A
访问节点: B
访问节点: D
访问节点: E
访问节点: F
访问节点: C

3.3 广度优先搜索（BFS）：层层推进

BFS的思路刚好相反：从起点开始，一层一层往外扩。就像往水里扔石头，波纹一圈圈扩散。我第一次用BFS做路径规划时，发现它天然适合找最短路径——因为先碰到的就是最近的。

3.3.1 BFS原理

• 用队列（Queue）实现，先进先出
• 按距离起点远近逐层访问
• 适合最短路径、层级遍历

3.3.2 BFS代码实现（Python）

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        print(f"访问节点: {node}")
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return visited

# 测试
print("\nBFS遍历顺序:")
bfs(graph, 'A')

输出：

BFS遍历顺序:
访问节点: A
访问节点: B
访问节点: C
访问节点: D
访问节点: E
访问节点: F

3.4 DFS vs BFS：到底选哪个？

对比项	DFS	BFS
数据结构	栈（Stack）	队列（Queue）
空间复杂度	O(h)，h为深度	O(w)，w为宽度
最短路径	不保证	保证（无权图）
适用场景	拓扑排序、连通性	最短路径、层级遍历
实现难度	递归简单，迭代稍复杂	队列实现，逻辑清晰

3.5 知识体系总览

下面这张图是我自己画的，把本章的核心逻辑串起来了：

3.6 实战小贴士

最后分享几个我踩过的坑：

1. 别忘了标记已访问节点——不然会死循环。我刚开始写DFS时忘了这步，程序跑了一下午没停……
2. 递归深度限制——Python默认递归深度1000，图大了会报错。可以用sys.setrecursionlimit()调大，或者直接写迭代版本。
3. BFS的队列别用list——用collections.deque，否则pop(0)是O(n)操作，大数据量时慢得你想哭。
4. 加权图别用BFS——BFS只保证无权图的最短路径。加权图请用Dijkstra或A*，后面章节会讲。