图算法实战：遍历、最短路、最小生成树与拓扑排序

引言

图是描述「关系」的语言——社交网络、地图导航、任务依赖、网络路由，全是一张图。本文把图算法的核心盘成一张技能树：先遍历（BFS/DFS），再最短路（Dijkstra/Bellman-Ford），再最小生成树（Prim/Kruskal），最后拓扑排序（有向无环图的关卡）。每类给出「解决什么问题、为什么这个算法、代码骨架、最坏复杂度」四件套，末尾给选型表。

前置：/others-big-o-complexity-guide/（复杂度）、/others-sorting-algorithms/（堆与排序）、/others-hashing-guide/（哈希与结构选型）。

目录

• 1. 图是什么：表示方法决定算法效率
• 2. BFS：无权图的最短路径
• 3. DFS：连通性与回溯
• 4. Dijkstra：加权最短路与堆优化
• 5. Bellman-Ford：负权与检测负环
• 6. 最小生成树：Prim 与 Kruskal
• 7. 并查集：连通性的快速判定
• 8. 拓扑排序：有向无环图的顺序
• 9. 选型表与常见陷阱
• 10. 速查表与一句话记忆
• 延伸阅读

1. 图是什么：表示方法决定算法效率

1.1 图的基本元素

顶点 V、边 E
有向/无向、加权/无权、稠密/稀疏

1.2 两种表示

# 现实图（社交/路网/依赖）几乎都是稀疏的 → 邻接表是默认
# 判断稀疏：E 远小于 V²

记忆：图 = 顶点+边；邻接表查边 O(度) 适合稀疏现实图（默认）、邻接矩阵 O(1) 只适合稠密图——表示选错，同样算法差一个数量级。

2. BFS：无权图的最短路径

2.1 思路：按层扩散

从起点出发，先访问距离 1 的邻居、再距离 2 的……用队列保证「先到先处理」：

from collections import deque

def bfs(graph, s):
    dist = {s: 0}
    q = deque([s])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if v not in dist:
                dist[v] = dist[u] + 1   # 首次访问即最短路
                q.append(v)
    return dist

2.2 为什么 BFS 求的是最短路

# 无权图边长为 1：第一次到达某顶点时，经过的边数必然最少
# BFS 保证"按距离分层"——先处理的永远是更近的
# 复杂度 O(V+E)，比 Dijkstra 快，无权图别用 Dijkstra

2.3 变体

# 记录路径：存 prev[v]，最后回溯
# 多源 BFS：多个起点同时入队（求最近源距离）

记忆：BFS 用队列按层扩散，首次到达即最短路——无权图最短路直接上 BFS（O(V+E)），比 Dijkstra 快且无需加权。

3. DFS：连通性与回溯

3.1 思路：一条路走到底再回头

递归或栈实现，深入探索再回溯：

def dfs(graph, u, visited):
    visited.add(u)
    for v in graph[u]:
        if v not in visited:
            dfs(graph, v, visited)

3.2 DFS 的典型场景

# 连通分量：一次 DFS 跑出一个连通块，标记计数
# 环检测：记录"在栈中"的节点，回边即环
# 拓扑排序（见 §8）：DFS 后序也能做
# 回溯搜索：全排列/组合/路径问题
# 迷宫寻路：能找到一条路径（不保证最短）

3.3 BFS vs DFS 选谁

# 求最短路/按层 → BFS
# 找一条路径/连通性/回溯枚举 → DFS
# 都行但 DFS 栈深可能爆递归：显式栈替代

记忆：DFS 一条路走到底再回溯——管连通分量、环检测、拓扑与回溯搜索；求最短路用 BFS、找路径/连通性用 DFS；递归可能爆栈就用显式栈。

4. Dijkstra：加权最短路与堆优化

4.1 思路：贪心扩展最近未确定点

维护「当前已知最短路」，每次取最小距离的顶点固定它，再松弛它的邻居：

import heapq

def dijkstra(graph, s):
    dist = {v: float('inf') for v in graph}
    dist[s] = 0
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue          # 过期条目跳过
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

4.2 堆优化的复杂度

# 朴素：O(V²)（稠密图适用）
# 堆优化：O((V+E) log V)（稀疏图默认）
# 前提：边权非负

4.3 关键点

# 贪心正确性依赖"非负权"——固定某个点后它的最短路不再变化
# 跳过过期的堆条目（dist[u] > 记录）避免重复处理
# 无权图别用 Dijkstra，BFS 更快

记忆：Dijkstra 贪心扩展最近未确定点+堆优化（O((V+E) log V)）——加权非负最短路的标准解；堆优化用优先队列、跳过过期条目、朴素版 O(V²) 用于稠密图。

5. Bellman-Ford：负权与检测负环

5.1 为什么需要它

# Dijkstra 假设非负权，遇到负权会错
# Bellman-Ford 容忍负权，还能检测负环
# 代价：O(VE)，比 Dijkstra 慢

5.2 思路：松弛 V-1 轮

每一轮对所有边松弛一次，第 k 轮后最短路至少覆盖 k 条边的路径：

def bellman_ford(edges, n, s):
    dist = [float('inf')] * n
    dist[s] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    # 再跑一轮：还能松弛 → 存在负环
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return "negative cycle!"
    return dist

5.3 负环意味着什么

# 负环 = 能无限降低总权重的环 → 最短路无定义
# 应用：外汇套利检测（环上汇率乘积 > 1）、差分约束
# 无负权时别用它（慢），用 Dijkstra

记忆：Bellman-Ford 松弛 V-1 轮容忍负权、再跑一轮检测负环（O(VE)）——负权/负环检测才用它；外汇套利与差分约束是典型应用。

6. 最小生成树：Prim 与 Kruskal

6.1 问题：用最省的总边权连起所有点

最小生成树（MST）用 V-1 条边连起全部顶点且总权最小。

6.2 Prim：从点长边

类似 Dijkstra，但「距离」是到树的距离：

# 维护"到已选集合的最短边"，每次并入最近的点
# 堆优化 O(E log V)，稠密图可用朴素 O(V²)

6.3 Kruskal：从边并集

按边权从小到大选，用并查集判断「会不会成环」：

def kruskal(n, edges):   # edges: (w, u, v)
    edges.sort()
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]; x = parent[x]
        return x
    total = 0
    for w, u, v in edges:
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            total += w
    return total

6.4 选型

# 边稀疏 → Kruskal（O(E log E)，简单直观）
# 边稠密/顶点图 → Prim（O(E log V)）
# 两者结果相同（可能有多个 MST），应用场景看图的形态

记忆：最小生成树两种做法——Prim 从点长边（类 Dijkstra 堆优化）、Kruskal 按边权排序+并查集防环（O(E log E)）；边稀疏用 Kruskal、稠密用 Prim，结果都连通且总权最小。

7. 并查集：连通性的快速判定

7.1 用途

# 快速判定两点是否连通、动态合并集合
# 配合 Kruskal（判环）、连通分量计数、动态图问题
# 平均 O(α(n)) ≈ 常数级（α 是反阿克曼函数）

7.2 两个关键优化

# 路径压缩：find 时把路径上的点直接挂到根
# 按秩合并：矮树挂到高树下
# 两者结合 → 摊还 O(α(n))，实际接近 O(1)

7.3 典型题

# 判环（无向图）：合并前先 find，已在同一集合即成环
# 连通分量计数：初始 n 个集合，每次成功合并减一
# 带权并查集：维护到根的偏移（分类/相对关系）

记忆：并查集管「连通性快速判定」——路径压缩+按秩合并摊还 O(α(n))≈常数；Kruskal 判环、连通分量计数、带权并查集都是它的经典应用。

8. 拓扑排序：有向无环图的顺序

8.1 问题：给有依赖的任务排序

有向无环图（DAG）的线性排序：每条边 u→v 满足 u 在 v 前。

8.2 Kahn 算法：不断删零入度点

from collections import deque

def topo_sort(n, indeg, adj):
    q = deque([i for i in range(n) if indeg[i] == 0])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else None   # None = 有环

8.3 应用

# 课程安排（先修课程）、构建依赖、包管理排序
# 判环：拓扑排不满 n 个 = 有环
# 也可 DFS 后序逆序得拓扑，但 Kahn 更直观

记忆：拓扑排序给 DAG 的任务排线性顺序——Kahn 算法不断删零入度点；排不满 n 个即存在环；课程依赖/构建/包管理都靠它。

9. 选型表与常见陷阱

9.1 选型表

9.2 常见陷阱

• 无权图用 Dijkstra：BFS 更快且不用堆。
• 负权图用 Dijkstra：贪心前提被破坏，结果错误。
• Dijkstra 忘记跳过过期条目：堆里塞满旧距离，变慢。
• Kruskal 忘并查集：直接判连通会 O(n) 退化成高复杂度。
• 邻接矩阵当默认：稀疏图空间与遍历都浪费。
• 拓扑排不满就当成功：有环时会静默少节点，要检查数量。

记忆：选型四问——无权吗用 BFS、非负吗用 Dijkstra 堆、负权吗 Bellman-Ford、要连通吗并查集；陷阱集中在「用错前提（负权/无权）」与「少判环/少跳过过期条目」。

10. 速查表与一句话记忆

一句话记忆：图算法按问题对号入座——无权最短路用 BFS（队列分层 O(V+E)）、非负加权最短路用 Dijkstra（贪心+堆优化 O((V+E) log V)、跳过过期条目）、负权或要查负环用 Bellman-Ford（松弛 V-1 轮再跑一轮）、最小生成树边稀疏用 Kruskal（按权排序+并查集防环）、稠密用 Prim（从点长边）、连通性用并查集（路径压缩+按秩合并≈O(1)）、DAG 排序用拓扑（Kahn 删零入度，排不满即环）；图的表示默认邻接表（稀疏现实图）；三大陷阱是「无权用 Dijkstra、负权用 Dijkstra、Kruskal 忘了并查集」——「先问图的类型（有权/无权/负权/有环），再选算法」是解题的第一性原理。

延伸阅读

• /others-big-o-complexity-guide/ — 复杂度与递归主定理
• /others-sorting-algorithms/ — 堆与优先队列
• /others-hashing-guide/ — 哈希与结构选型
• /others-fuzzy-text-matching/ — 图/相似度算法
• 分布式系统专题 — 一致性协议与图的应用
• 可视化图算法
• OI Wiki 图论