图搜索算法入门：图论基础与三大经典算法

大家好，我是你们的老朋友。今天咱们正式进入图搜索算法的世界。

说实话，我刚入行那会儿，觉得图论这东西特别抽象。什么节点、边、权重，听着就像数学课本里的概念。直到我第一次做机器人路径规划，才真正体会到——没有图论，你连地图都描述不清楚。

这一章，我会带你打好基础。咱们从图论的基本概念讲起，然后手撸BFS、DFS，最后搞定Dijkstra。嗯，都是硬货，但我会尽量讲得接地气。

图论基础：节点、边、权重

先问个问题：什么是图？

说白了，图就是一堆点（节点）和连接这些点的线（边）。你想想看，地图上的路口就是节点，道路就是边。就这么简单。

我习惯把图分成三种：

  • 无向图：边没有方向。比如你和朋友的关系，是双向的。
  • 有向图：边有方向。比如单行道，只能从一个方向走。
  • 加权图：边上带数字（权重）。比如道路的长度、通行时间、油耗等。

权重这东西，我在项目中吃过亏。有一次做AGV调度，我默认所有路径的权重都是距离。结果发现，有些路段虽然短，但经常堵车。后来我改成用通行时间做权重，效果立竿见影。

核心概念速记

  • 节点（Vertex）：图中的基本单元，代表位置或状态
  • 边（Edge）：节点之间的连接，代表关系或路径
  • 权重（Weight）：边的代价，可以是距离、时间、成本等
  • 邻接（Adjacency）：两个节点之间有边直接相连
  • 路径（Path）：从一个节点到另一个节点经过的边序列

下面这张图，是我手绘的图结构示意。你可以看到节点、边和权重的关系。

A B C D 5 3 2 4 1 图例 节点 边（权重） 自环

图中A到B的权重是5，A到C是3，B到D是2，C到D是4。A还有一个自环，权重为1。这种结构，在路径规划中非常常见。

广度优先搜索（BFS）

BFS是什么？我打个比方：你往池塘里扔一块石头，水波一圈一圈往外扩散。BFS就是这种扩散式的搜索方式。

它的核心思想是：先访问离起点近的节点，再访问远的。用队列实现，先进先出。

我曾经用BFS解决过一个迷宫问题。机器人要从左上角走到右下角，障碍物随机分布。BFS保证能找到最短路径（步数最少），但不管权重。说白了，它只关心「几步能到」，不关心「这条路好不好走」。

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

# 示例图（邻接表）
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

bfs(graph, 'A')

运行结果：A → B → C → D。注意，B和C的顺序取决于邻接表的定义。如果你把C放在B前面，结果就是A → C → B → D。

避坑指南

我曾经在BFS里忘记标记已访问节点，结果死循环了。嗯，那是在一个环形图里，队列永远清不空。所以记住：入队即标记，不要出队再标记。

深度优先搜索（DFS）

DFS和BFS正好相反。它是一条路走到黑，撞了南墙再回头。用栈实现，后进先出。

我刚开始学DFS时，总觉得它不如BFS实用。后来做拓扑排序和连通性检测，才发现DFS的妙处。比如检测一个图有没有环，DFS比BFS方便得多。

DFS有两种写法：递归和迭代。我个人习惯用递归，代码更简洁。但要注意递归深度，Python默认递归深度是1000，图大了会栈溢出。

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

# 迭代版本
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(f"访问节点: {node}")
            # 注意：为了保持和递归相同的顺序，需要反向入栈
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    return visited

# 使用示例
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

print("递归DFS:")
dfs_recursive(graph, 'A')
print("\n迭代DFS:")
dfs_iterative(graph, 'A')

递归版本输出：A → B → D → C。迭代版本如果不用reversed，顺序会不同。你想想看，栈是后进先出，所以先压入的节点会后访问。

BFS vs DFS 对比

特性 BFS DFS
数据结构 队列（Queue） 栈（Stack）
空间复杂度 O(宽度)，可能很大 O(深度)，通常较小
最短路径 能找到（无权图） 不能保证
适用场景 最短路径、层级遍历 拓扑排序、连通性检测

Dijkstra算法原理与实现

终于到了重头戏。Dijkstra算法，说白了就是带权重的BFS。它解决了BFS的痛点：当边的权重不同时，步数最少不等于代价最小。

我记得第一次在项目中用Dijkstra，是在一个仓储机器人系统里。地图上有不同长度的走廊，还有电梯（权重特别大）。BFS给出的路径虽然步数少，但要走电梯，耗时反而更长。换成Dijkstra后，机器人自动绕开了电梯，走平路。

Dijkstra的核心思想：贪心 + 松弛。每次选择当前距离最小的节点，然后更新它的邻居。用优先队列（最小堆）实现。

import heapq

def dijkstra(graph, start):
    # 初始化距离字典，起点为0，其他为无穷大
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    # 优先队列：(距离, 节点)
    pq = [(0, start)]
    # 记录路径
    previous = {node: None for node in graph}
    
    while pq:
        current_dist, current_node = heapq.heappop(pq)
        
        # 如果当前距离大于已知距离，跳过（重要优化）
        if current_dist > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node].items():
            distance = current_dist + weight
            
            # 松弛操作
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous[neighbor] = current_node
                heapq.heappush(pq, (distance, neighbor))
    
    return distances, previous

def reconstruct_path(previous, start, end):
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = previous[current]
    path.reverse()
    return path if path[0] == start else []

# 示例图（带权重的邻接表）
graph = {
    'A': {'B': 5, 'C': 3},
    'B': {'A': 5, 'D': 2},
    'C': {'A': 3, 'D': 4},
    'D': {'B': 2, 'C': 4}
}

distances, previous = dijkstra(graph, 'A')
print(f"从A到各节点的最短距离: {distances}")
print(f"从A到D的最短路径: {reconstruct_path(previous, 'A', 'D')}")

输出结果：从A到D的最短距离是7（A→B→D，5+2），而不是A→C→D（3+4=7，一样）。如果权重不同，结果会变。

Dijkstra的局限性

  • 不能处理负权边。如果有负权，算法会陷入死循环或给出错误结果。
  • 需要知道所有节点信息。如果图是动态变化的，Dijkstra不适用。
  • 时间复杂度O((V+E)logV)，对于超大图可能不够快。

我曾经在项目中遇到负权边，Dijkstra跑出来的路径明显不对。后来换成Bellman-Ford才解决。所以，用之前一定要确认权重非负。

三种算法的选择建议

说了这么多，到底什么时候用哪个？我总结一下：

  • 无权图，找最短步数 → BFS
  • 需要遍历所有节点，或者检测连通性 → DFS
  • 有权图，找最小代价路径 → Dijkstra
  • 有权图，有负权边 → Bellman-Ford（下一章会讲）

你想想看，实际项目中90%的情况都是有权图。所以Dijkstra是重中之重。BFS和DFS虽然简单，但它们是理解更复杂算法的基础。

我的学习建议

别光看代码，动手画图。拿一张纸，画几个节点，手动模拟BFS、DFS、Dijkstra的执行过程。我当年就是这么学的，效果比看十遍视频都好。

好了，这一章的内容就到这儿。图论基础打牢了，后面学A*、RRT、PRM这些高级算法才会轻松。记住：算法是工具，理解原理才能用好它。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →