Spark Notes

Appearance

图遍历 ​

图遍历的核心动作可以概括为一句循环：处理当前节点，试探下一个节点，决定是否进入。所有遍历算法——DFS、BFS、回溯——都是这三个动作在不同顺序和不同数据结构上的编排。理解这个框架，遍历问题就从"背诵模板"变成"排列三个动作"。

试探与进入：DFS 的本质 ​

DFS 的每一步都遵循"试探 → 决定 → 进入"的模式：当前节点处理后，考察一个邻居节点（试探），判断它是否值得进入（决定：未访问过？满足约束？），满足则递归进入，不满足则考虑下一个邻居。回溯不是额外的操作——它就是"试探失败后尝试下一个"的自然结果。

python
def dfs(node, visited):
    # 处理当前节点
    visited.add(node)
    for neighbor in node.neighbors:   # 试探下一个节点
        if neighbor not in visited:   # 决定是否进入
            dfs(neighbor, visited)    # 进入

"试探"和"进入"的分离是 DFS 灵活性的来源。试探阶段可以做任何过滤——检查边界、检查约束、剪枝；进入阶段才真正消耗资源（递归栈、标记状态）。剪枝的本质就是在试探阶段提前决定"不进入"——DFS 的性能上限由试探阶段的判断质量决定。

矩阵可以看作隐式图——每个格子是一个节点，上下左右四邻域是边。矩阵遍历不需要显式的邻接表，试探动作变成边界检查和值检查：0 <= r < rows and 0 <= c < cols and matrix[r][c] != visited。岛屿数量、矩阵连通域这类问题的解法都是同一个 DFS 骨架换不同的试探条件。

状态管理：visited 的三层语义 ​

visited 集合是遍历正确性的关键，它的状态管理有三种精度：

最简单的布尔 visited（访问过/未访问）适合大多数遍历。更精细的"三色标记"（白色未访问/灰色访问中/黑色访问完成）在检测环时必不可少——DFS 过程中遇到灰色节点说明有环，遇到黑色节点说明是已完成的子树。有向图的环检测（课程表问题）依赖这个区分：visited 中的节点可能是"本路径上的祖先"（环）或"其他分支已访问"（不是环）——只有三色标记能区分这两种情况。

回溯场景的 visited 需要"进入时标记、退出时撤销"——同一条路径上不能重复访问，但不同路径之间互不影响。撤销标记是回溯与普通 DFS 的关键区别：普通 DFS 的 visited 是全局的（访问过就不再访问），回溯的 visited 是路径局部的（当前路径上的节点集合）。

BFS：层次扩展 ​

BFS 与 DFS 的差异只在"下一个节点"的选择策略：DFS 用栈（递归栈或显式栈）——深入优先；BFS 用队列——宽度优先。BFS 的天然产物是"层"：距离起点 k 步的节点在队列的第 k 轮全部出队。

python
from collections import deque

def bfs(start):
    queue = deque([start])
    visited = {start}
    while queue:
        # 当前层的全部节点
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()          # 处理当前节点
            for neighbor in node.neighbors: # 试探下一个节点
                if neighbor not in visited: # 决定是否进入
                    visited.add(neighbor)
                    queue.append(neighbor)  # 进入

level_size 快照是 BFS 处理"层"的经典技巧——不加快照，队列中会混合多层节点，无法判断距离。最短路径、树的层序遍历、感染扩散模拟都依赖这个分层。

BFS 的 visited 标记时机有一个经典陷阱：必须入队时标记而非出队时标记。如果出队时才标记，同一节点可能被多个邻居同时入队——队列膨胀，极端情况下（稠密图）复杂度从 O(V+E) 退化为指数级。

选择：DFS 还是 BFS ​

选择标准主要由问题要回答的性质决定。问"是否存在路径"和"最短路径长度"——BFS（无权图的最短路径是 BFS 的自然产物）。问"所有可能的路径"和"所有连通分量"——DFS（深入一条路走到底，天然适合枚举和回溯）。问"能否到达"但状态空间巨大——DFS + 剪枝（试探阶段的判断可以大幅剪掉无效分支，BFS 没有这种剪枝机会）。

空间复杂度是另一个考量：DFS 的栈深度是最长路径长度，BFS 的队列是最大层宽。树的层宽远大于深度——DFS 的空间优势明显。但 DFS 在深图上有栈溢出风险——递归实现转换为显式栈可以解除限制。

图遍历的工程联系 ​

遍历范式在工程中的存在感远超算法题。垃圾回收的标记-清除是图遍历（对象图的三色标记）；依赖解析是拓扑排序（DFS 的变体）；编译器的活跃变量分析是数据流上的定点迭代；网络路由是带权图上的 BFS 变体（Dijkstra）。图遍历不是"算法题技巧"，而是"在关系结构上系统性探索"的基础能力——凡是问题可以建模为"对象 + 关系"，遍历框架就适用。