图的表示与遍历
本节目标
用邻接表、visited 不变量和 DFS/BFS 统一处理显式图、网格与多源扩散问题。
图题先要回答“一个状态能走到哪些状态”。顶点可以是城市、房间或对象节点；边可以在输入中显式给出，也可以由网格相邻规则隐式生成。表示法决定枚举邻居的代价，遍历法则负责保证每个状态只被处理一次。
识别信号
- 输入给出边集、邻居编号或对象的
neighbors，问题问两点是否连通、能否全部到达或如何复制结构。 - 二维网格中的上下左右移动构成隐式图，问连通块数量时通常要把每块陆地完整走完。
- 一个状态会同时向四周扩散，题目要求最少轮数或最少分钟时，应优先想到按层推进的 BFS。
- 图中可能有环、重复边或多条路径；只靠递归终止条件无法防止重复访问，必须维护访问状态。
问题模型与核心不变量
邻接矩阵用 matrix[u][v] 表示边是否存在，查询一条边是 O(1)，但稀疏图会占用 O(V^2) 空间，并且枚举 u 的邻居要扫描整行。邻接表为每个顶点保存实际邻居，空间为 O(V + E)，在稀疏图中能直接按边数枚举，是本栏显式无权图的默认表示。
网格不需要真的建出邻接表：坐标 (r, c) 是顶点，合法的上下左右坐标是它的隐式邻居。克隆图也不需要按节点值建表，原节点对象本身就是身份；memo[old] = copy 是连接原图与副本图的映射。
遍历的共同不变量是：节点进入栈或队列的瞬间就标记为已访问（或原地改写为已处理）。因此任何节点最多入容器一次，环不会回到已处理状态；克隆图则先登记副本，再递归邻居，回边总能返回同一个副本。多源 BFS 的队列始终保存“已腐烂且等待向下一层传播”的橘子，循环开始的每一层对应同一分钟。
通用模板
建立（或隐式定义）邻居关系
把起点 / 所有初始源点放入容器，并立刻标记
while 容器非空：
取出一个节点（DFS 用栈，BFS 用队列）
检查当前答案条件
枚举邻居：
若邻居尚未访问：
标记邻居
将邻居放入容器
无权图的“是否可达”只需从起点 DFS 或 BFS；遍历结束后仍未遇到目标即不可达。连通块题在外层扫描所有顶点，每发现一个未访问陆地就把答案加一并启动一次 DFS。需要最少扩散轮数时，BFS 每轮先固定当前队列长度，再统一处理这一层。
模板变体
- 邻接矩阵适合顶点数小、边查询极多或图接近稠密的场景；否则优先邻接表。
grid[r][c]既可作为输入状态，也可改写为 visited 标记；如必须保留输入，改用同尺寸visited数组。- 克隆结构时，visited 不是布尔值，而是“原节点到新节点”的映射；创建副本后立刻写入映射，才能正确处理环。
- 只关心可达性时 DFS/BFS 都正确；需要最短边数、最少轮数或按距离分层时使用 BFS。
- 多源 BFS 先把所有源点入队，等价于添加一个连向所有源点的虚拟起点，第一层距离为零。
母题序列
按必学顺序练习：
- 寻找图中是否存在路径（必学）：把无向边建成邻接表，从 source 迭代 DFS 到 destination。
- 岛屿数量（必学）：把陆地连通块看作隐式图的分量，扫描到新陆地时完整淹没它。
- 克隆图（必学）：用原节点身份到副本节点的映射，在含环图中保留邻接关系。
- 钥匙和房间（必学）：从房间 0 出发，比较已访问房间数与房间总数。
- 腐烂的橘子（必学）：将全部腐烂橘子作为同一时刻的源点，按 BFS 层数计分钟。
常见误区
- 把无向边只加入一个方向，导致从反向起点无法到达。
- 出栈或出队时才标记 visited，使同一节点可被多条边反复放入容器。
- 网格 DFS 没有在入栈前改写陆地，遇到相邻格会重复压栈甚至反复计数。
- 克隆图只按值记录节点；节点值相同或图有环时都不能唯一确定副本关系。
- 用单源 BFS 处理多源扩散，错误地把不同初始腐烂橘子的距离串联起来。
- fresh 变为零后仍多加一分钟；分钟只代表真正完成的一层传播。
迁移方向
图遍历解决的是“沿边扩张”。下一步可把边方向和入度加入状态，得到拓扑排序；把父节点和集合归并加入状态，得到连通性与并查集；把路径长度或权重加入状态，才进入最短路与最小生成树。先守住入容器即标记的不变量，再改变状态含义。