第九章：图算法基础

本章目标

本章学习图算法基础。图用节点和边表示关系，适合建模路线、依赖、社交关系和状态转移。

你会构建邻接表，用 BFS 求无权图最短路，用 DFS 做遍历和连通性检查。

核心概念

邻接表用 dict 或 list 保存每个节点的相邻节点，空间通常是 O(V + E)。稀疏图中它比邻接矩阵更节省空间。

BFS 按层扩展，因此在无权图中第一次到达某个节点时就是最短步数。DFS 会沿一条路径走到底，适合搜索结构。

Python 示例

邻接表可以直接从边列表构造。

from collections import deque, defaultdict

def build_graph(edges):
    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    return graph

BFS 求无权图最短步数；DFS 遍历则可以用递归或显式栈。

def shortest_steps(graph, start, target):
    queue = deque([(start, 0)])
    seen = {start}
    while queue:
        node, dist = queue.popleft()
        if node == target:
            return dist
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append((nxt, dist + 1))
    return -1

复杂度与常见误区

BFS 和 DFS 都会在最坏情况下访问所有节点和边，时间复杂度是 O(V + E)，额外空间也可能达到 O(V)。

常见误区是忘记 visited，导致有环图无限循环。另一个误区是用 DFS 求无权最短路，DFS 第一次到达不保证最短。

本章要点

图题先明确节点是什么、边是什么、是否有方向、是否有权重，再选择 BFS、DFS 或最短路算法。

掌握邻接表、BFS、DFS 后，就能继续学习拓扑排序、Dijkstra、并查集等进阶内容。