Ch14 §04 图 · 讲解稿¶

章节定位: 图算法。教"在图上做搜索 + 优化": BFS / DFS / 最短路 / MST / Union-Find / 拓扑排序。承接: §03 树 → §04 一般图 (含环) 走向: §05 排序篇幅: ~3800 字 / 阅读 11 分钟 / 讲解 22-25 分钟

一 · 一句话总览¶

图算法 = 在图上做遍历 + 优化。BFS / DFS (遍历) / Dijkstra (最短路) / Kruskal / Prim (MST) / Union-Find (连通性) / 拓扑 (DAG)。AI 应用: GNN 邻居采样 (Ch12), SLAM 回环 (Ch11), 知识图谱 (Ch07)。

二 · 章节主线 (5 段)¶

第 1 段 · 图的表示 (5 分钟)¶

# 邻接表 (稀疏图常用)
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}

# 邻接矩阵 (稠密图)
matrix = [
    [0, 1, 1, 0],
    [1, 0, 1, 1],
    [1, 1, 0, 1],
    [0, 1, 1, 0]
]

表示	空间	找邻居	加边
邻接表	\(O(V+E)\)	\(O(d)\)	\(O(1)\)
邻接矩阵	\(O(V^2)\)	\(O(V)\)	\(O(1)\)

第 2 段 · BFS 与 DFS (8 分钟)¶

3.2.1 BFS (广度优先)¶

from collections import deque

def bfs(graph, start):
    visited = {start}
    q = deque([start])
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nb, _ in graph[node]:
            if nb not in visited:
                visited.add(nb)
                q.append(nb)
    return order

\(O(V + E)\)。

应用: 无权最短路, 层序, 拓扑, 连通块。

3.2.2 DFS (深度优先)¶

def dfs(graph, start, visited=None):
    if visited is None: visited = set()
    visited.add(start)
    for nb, _ in graph[start]:
        if nb not in visited:
            dfs(graph, nb, visited)
    return visited

或迭代:

def dfs_iter(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited: continue
        visited.add(node)
        for nb, _ in graph[node]:
            if nb not in visited:
                stack.append(nb)
    return visited

\(O(V + E)\)。

应用: 拓扑, 强连通分量, 回溯。

3.2.3 BFS vs DFS¶

维度	BFS	DFS
数据结构	队列	栈
最短路 (无权)	✓	✗
空间	宽	深
应用	层序, 拓扑	回溯, 路径

第 3 段 · 最短路 (12 分钟)¶

3.3.1 Dijkstra¶

适用: 加权非负图。

import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

\(O((V + E) \log V)\)。

3.3.2 Bellman-Ford¶

适用: 有负权 (但无负环)。

def bellman_ford(edges, n, start):
    # edges: [(u, v, w), ...]
    dist = [float('inf')] * n
    dist[start] = 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 None  # 有负环
    return dist

\(O(VE)\)。

3.3.3 Floyd-Warshall¶

所有点对最短路。

def floyd(graph):
    n = len(graph)
    dist = [[float('inf')] * n for _ in range(n)]
    for i in range(n): dist[i][i] = 0
    for u in range(n):
        for v, w in graph[u]:
            dist[u][v] = w
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

\(O(V^3)\)。

3.3.4 A* 算法¶

启发式搜索, 加速 Dijkstra。

\[f(n) = g(n) + h(n)\]

\(g\) 实际代价, \(h\) 启发式 (e.g., 欧氏距离)。\(h\) 可采纳 (< 真实) 保证最优。

3.3.5 总结¶

算法	适用	时间
BFS	无权	\(O(V+E)\)
Dijkstra	加权非负	\(O((V+E) \log V)\)
Bellman-Ford	有负权	\(O(VE)\)
Floyd	全对	\(O(V^3)\)
A*	启发式	取决于 \(h\)

第 4 段 · 最小生成树与 Union-Find (10 分钟)¶

3.4.1 MST 定义¶

包含所有 \(V\) 个节点的最小权重生成树, 边数 \(V-1\)。

3.4.2 Prim 算法¶

从某点出发, 每次加最小跨边。

def prim(graph, n):
    visited = [False] * n
    min_edge = [float('inf')] * n
    min_edge[0] = 0
    total = 0
    for _ in range(n):
        u = -1
        for v in range(n):
            if not visited[v] and (u == -1 or min_edge[v] < min_edge[u]):
                u = v
        visited[u] = True
        total += min_edge[u]
        for v, w in graph[u]:
            if not visited[v] and w < min_edge[v]:
                min_edge[v] = w
    return total

\(O(V^2)\) (邻接矩阵) 或 \(O(E \log V)\) (堆)。

3.4.3 Kruskal 算法¶

按边权重排序, 用 Union-Find 检查是否成环。

def kruskal(edges, n):
    # edges: [(w, u, v), ...]
    edges.sort()
    uf = UnionFind(n)
    total = 0
    for w, u, v in edges:
        if uf.union(u, v):
            total += w
    return total

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # 路径压缩
            x = self.parent[x]
        return x
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False
        if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1
        return True

\(O(E \log E)\)。

3.4.4 Union-Find 应用¶

Kruskal MST
连通分量
等价类 / 朋友圈
离线最小生成树

第 5 段 · 拓扑排序与 SCC (5 分钟)¶

3.5.1 拓扑排序 (DAG)¶

def topo_sort(graph, n):
    in_degree = [0] * n
    for u in range(n):
        for v, _ in graph[u]:
            in_degree[v] += 1

    q = deque([u for u in range(n) if in_degree[u] == 0])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v, _ in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                q.append(v)
    return order if len(order) == n else None  # 有环返回 None

3.5.2 强连通分量 (Tarjan / Kosaraju)¶

\(O(V + E)\)。用于社区检测。

三 · 易错点 (5 条)¶

Dijkstra 负权: 不能用, 用 Bellman-Ford。
BFS 最短路: 仅无权图。
Prim 起点: 任一起点都行。
Union-Find 路径压缩: 必须有, 否则 \(O(\log n)\)。
拓扑排序环: 检测方法 — 入度无法清空。

四 · 跨章连接¶

章节	关联
Ch12 §03 GNN	BFS 邻居采样
Ch11 §05 SLAM	A* 路径规划
Ch07 §04 Transformer	Beam search 拓扑
Ch05 §05 决策树	树是图特例

五 · 自测 5 题¶

BFS vs DFS 适用场景?
Dijkstra 不适用什么?
最短路算法时间复杂度对比?
Prim vs Kruskal?
拓扑排序前提?

六 · 一句话总结¶

图算法 = 遍历 (BFS/DFS) + 最短路 (Dijkstra) + MST (Prim/Kruskal) + Union-Find (连通) + 拓扑 (DAG)。AI 应用: GNN (邻居采样) / SLAM (路径) / 知识图谱。Ch14 §05 进入排序。

七 · 板书建议¶

[板书 1: 表示]
   邻接表 $O(V+E)$
   邻接矩阵 $O(V²)$

[板书 2: 遍历]
   BFS 队列
   DFS 栈

[板书 3: 最短路]
   Dijkstra: 非负
   Bellman-Ford: 负权

[板书 4: MST]
   Prim: 从点
   Kruskal: 从边 + UF

八 · 参考资料¶

Cormen et al., CLRS Ch 22-26 (图)
NetworkX 文档
Ch12 §03 GNN (本套书)
Ch11 §05 SLAM (本套书)