遍历与连通性 · HTML
数学 / 逻辑形态
给定图 G=(V,E) 与合法节点集合 A。对每个尚未访问的 v∈A 启动一次 DFS；一次搜索访问的节点恰组成 v 所在的连通分量。
识别信号
- 题意出现 connected、reachable、component、group 或 region。
- 只问能否到达、分成几组或每组统计，不问最少步数。
- 后继可即时生成且每个状态只需处理一次。
- 深入任一分支不会破坏答案，处理顺序无关紧要。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 无权最短路 | DFS 首次到达不保证最少边数；改用 bfs-unweighted-shortest。 |
| 依赖顺序 | 有向依赖的重点是入度或递归颜色，不是普通连通遍历。 |
核心不变量
节点一旦标记 visited，就已被归入当前搜索代表的分量，之后不会属于另一分量。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 当前节点 u、全局 visited，以及可选的分量聚合器（大小、和、边界等）。 |
| Transition | 枚举 u 的邻居 v；若合法且未访问，则先标记，再递归或压栈。 |
| Frontier / order | 递归调用栈或显式 LIFO 栈，保存已发现但尚未完全展开的节点。 |
Python 骨架
def components(graph):
seen, groups = set(), []
for start in graph:
if start in seen:
continue
seen.add(start)
stack, group = [start], []
while stack:
u = stack.pop()
group.append(u)
for v in graph[u]:
if v not in seen:
seen.add(v)
stack.append(v)
groups.append(group)
return groups
正确性思路
- 可靠性：只有沿真实边从 start 可达的节点才会被压栈。
- 完备性：对任意可达节点取一条路径；沿路径归纳，每个前驱展开时都会发现后继。
- 不重不漏：发现时标记使节点至多入栈一次；外层循环为每个尚未归类节点启动新分量。
复杂度
| Time | Space | Parameters |
|---|
| O(V+E) | O(V) | V 为节点数，E 为邻接表中的边记录总数。 |
边界条件
- 空图返回空集合。
- 孤立节点各自形成分量。
- 自环不能触发重复入栈。
- 深链递归可能溢出，改用显式栈。
错误模式
| Pattern | Why it fails / fix |
|---|
| 弹出后才标记 | 同一节点可能被多个邻居重复压栈；通常发现时标记。 |
| 只搜一个起点 | 只能得到一个分量；统计全图必须扫描所有节点。 |
| 边方向建错 | 漏建无向图的反向边会把连通性误算成单向可达性。 |
选择与排除规则
- 只问存在性或分组且无距离目标：DFS/BFS 都可。
- 退出递归时要携带区域摘要：DFS 更自然。
- 深度可能接近 V：优先显式栈。
相关模板
| Relation | Template | Boundary |
|---|
| 递归反转替代 | 链表指针改线 | 递归返回后重连，但需承担 O(n) 调用栈。 |
| traversal-foundation | 树形 DP | DFS 提供 parent 与 postorder 骨架。 |
| 动态连通替代 | 并查集动态连通性 | 边持续加入且要反复查询连通性。 |
原创微型例子
| 环节 | 内容 |
|---|
| Result | 得到 {p,q,r} 与 {s} 两个分量。 |
| Setup | p—q—r 相连，s 孤立。 |
| Trace | 从 p 依次发现 q、r；外层跳过它们，再从 s 启动。 |
Recall prompts
我的补充