3. 图搜索基础：图论基本概念与DFS/BFS

各位同学好，我是你们这节《路径规划与决策算法入门》的讲师。今天我们来聊聊图搜索。说实话，图搜索是整个路径规划算法的地基。你后面学的A*、Dijkstra、RRT，本质上都是在图搜索这个框架上做文章。所以这一节，咱们把地基打牢。

3.1 图论基本概念：节点、边、权重

先问个问题：什么是图？

说白了，图就是一堆「点」和连接这些点的「线」。在路径规划里，点就是机器人可能到达的位置，线就是位置之间的可行路径。

节点（Node/Vertex）：代表状态或位置。比如一个房间的角落、一个路口、一个栅格的中心点。

边（Edge）：代表两个节点之间的连接关系。如果两个节点之间有边，说明机器人可以直接从A走到B。

权重（Weight）：边的代价。可以是距离、时间、能耗，甚至风险值。我做过一个仓储机器人项目，权重就是「路径长度 + 障碍物密度惩罚项」。嗯，这个惩罚项帮我们避开了很多拥堵区域。

核心概念速查表

术语	含义	路径规划中的例子
节点	状态/位置	栅格地图中的每个格子
边	连接关系	相邻格子之间的可通行路径
权重	代价	移动距离、时间、能耗
有向图	边有方向	单行道、下坡路
无向图	边无方向	双向通行的走廊

我个人习惯把图分为两种：有向图和无向图。无向图就是A能到B，B也能到A。有向图则像单行道，只能一个方向走。你想想看，在真实机器人场景里，斜坡、电梯、单向门，这些都得用有向图来表示。

3.2 深度优先搜索（DFS）

DFS，说白了就是「一条路走到黑，撞了南墙再回头」。它的核心思想是：从起点出发，沿着一条分支一直往下探索，直到走不动了，再回溯到上一个分叉点，换条路继续走。

DFS的算法流程：

把起点压入栈（Stack）
从栈顶弹出一个节点，标记为已访问
检查该节点是否为目标节点。如果是，结束
否则，把所有未访问的邻居节点压入栈
重复步骤2-4，直到栈为空

这里的关键数据结构是栈。后进先出（LIFO）的特性，决定了DFS会优先深入探索，而不是横向扩展。

避坑指南：我曾经在一个迷宫导航项目里用DFS，结果机器人绕了远路。为什么？因为DFS不保证找到最短路径。它只保证「能找到一条路径」。如果你需要最短路径，请用BFS或Dijkstra。

# DFS 伪代码
def dfs(graph, start, goal):
    stack = [start]
    visited = set()
    
    while stack:
        node = stack.pop()  # 从栈顶取
        if node == goal:
            return True
        if node not in visited:
            visited.add(node)
            # 把未访问的邻居压入栈
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)
    return False

DFS的时间复杂度是O(V+E)，V是节点数，E是边数。空间复杂度最坏情况O(V)。嗯，这里要注意，如果图特别深，递归实现的DFS可能会栈溢出。我建议用迭代版本，更可控。

3.3 广度优先搜索（BFS）

BFS和DFS正好相反。它是「层层推进，地毯式搜索」。从起点开始，先探索所有距离为1的节点，再探索距离为2的节点，以此类推。

BFS的算法流程：

把起点放入队列（Queue）
从队列头部取出一个节点，标记为已访问
检查是否为目标节点
把所有未访问的邻居节点加入队列尾部
重复步骤2-4，直到队列为空

关键数据结构是队列。先进先出（FIFO）保证了「先发现的节点先被扩展」，这就是BFS能找到最短路径的根本原因。

注意：BFS能找到最短路径，前提是所有边的权重相同。如果边的权重不同（比如有的路长、有的路短），BFS就不灵了。这时候得用Dijkstra算法。我在做AGV调度时吃过这个亏，后来老老实实换了Dijkstra。

# BFS 伪代码
def bfs(graph, start, goal):
    queue = [start]
    visited = set()
    
    while queue:
        node = queue.pop(0)  # 从队列头部取
        if node == goal:
            return True
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)  # 加入队列尾部
    return False

BFS的时间复杂度也是O(V+E)。但空间复杂度比DFS高，因为队列里可能同时存很多节点。尤其是当图的分支因子很大时，BFS的内存消耗会暴涨。

3.4 DFS vs BFS：怎么选？

我经常被问到：「到底用DFS还是BFS？」

我的回答是：看需求。

场景	推荐算法	原因
需要最短路径（等权图）	BFS	BFS保证找到最短路径
内存有限	DFS	DFS空间复杂度通常更低
解可能很深	DFS	DFS能快速深入，BFS可能爆炸
解可能很浅	BFS	BFS在浅层就能找到解
需要遍历所有节点	两者均可	都能遍历，但DFS实现更简洁

举个例子。我在做扫地机器人全覆盖路径规划时，用的是DFS。因为需要遍历所有房间，DFS的递归回溯特性天然适合「走遍每个角落」。但如果是送餐机器人找最短路径，我肯定用BFS。

3.5 知识体系总览

下面这张图是我手绘的本章知识结构，帮你理清脉络。

3.6 实战小贴士

最后分享几个我在项目中积累的经验：

别用递归DFS处理大图。Python默认递归深度只有1000左右，超过就报错。用栈实现迭代版本更安全。
BFS的队列别用list.pop(0)。这个操作是O(n)的，数据量大时巨慢。用collections.deque，popleft是O(1)。
记得标记已访问节点。不然DFS/BFS都会陷入死循环。我见过有人忘了这步，程序跑了半小时没停。
权重不同时，BFS不保证最优。这是新手最容易犯的错误。等权图用BFS，不等权用Dijkstra。

好了，图搜索基础就讲到这里。记住，DFS和BFS是路径规划的两把入门钥匙。后面学A*、Dijkstra时，你会发现它们都是在BFS的基础上加了「启发式」或「权重」的改进。地基打牢了，后面盖楼才稳。

📚 课程目录

3. 图搜索基础：图论基本概念与DFS/BFS

3.1 图论基本概念：节点、边、权重

3.2 深度优先搜索（DFS）

3.3 广度优先搜索（BFS）

3.4 DFS vs BFS：怎么选？

3.5 知识体系总览

3.6 实战小贴士