BFS 连通性遍历

数学 / 逻辑形态

从未访问起点入队，反复弹出队首并发现其未访问邻居；外层扫描所有节点即可分解 G 的全部分量。

识别信号

核心是遍历图或隐式状态图，而不是优化带权路径。
希望避免递归深度限制。
从近到远扩散的处理顺序有助于观察或调试。
需要在发现时记录父节点、层级或分量编号。

容易误判的相似信号

Signal	Why it is different
非等权最短路	FIFO 不按总代价排序；换 Dijkstra 或 0-1 BFS。
拓扑层次	依赖图的可执行层由入度决定，不是与任意起点的距离。

核心不变量

队列中的节点已被发现并归属当前分量，但尚未展开；未访问节点尚未被证明从当前起点可达。

状态、转移与处理顺序

Item	Definition
State	FIFO 队列、visited、分量编号，以及可选的 parent/level。
Transition	出队 u；对合法未访问邻居 v，立即标记并入队。
Frontier / order	FIFO queue，保持发现顺序；同层节点先于下一层被展开。

Python 骨架

from collections import deque

def bfs_groups(graph):
    seen, label = set(), {}
    group_id = 0
    for start in graph:
        if start in seen:
            continue
        seen.add(start)
        q = deque([start])
        while q:
            u = q.popleft()
            label[u] = group_id
            for v in graph[u]:
                if v not in seen:
                    seen.add(v)
                    q.append(v)
        group_id += 1
    return group_id, label

正确性思路

每次入队都由一条来自已可达节点的边触发，因此不会混入其他分量。
沿任意可达路径归纳，前驱迟早出队并发现后继，所以不会漏点。
发现时标记使节点只归属一次；外层扫描补齐其余分量。

复杂度

Time	Space	Parameters
O(V+E)	O(V)	V 为节点数，E 为邻接项总量；队列最宽可达 O(V)。

边界条件

单个节点本身就是一个分量。
多个孤点都须由外层循环启动。
重复边不能造成重复入队。
只作为终点出现的节点也要纳入节点集合。

错误模式

Pattern	Why it fails / fix
用 list.pop(0)	移位导致单次出队 O(n)；用 deque.popleft。
入队时不标记	菱形图会把同一节点重复入队。
把首次发现泛化到任意权	只有等权边的层数才代表最小总代价。

选择与排除规则

需要连通遍历且担心递归深度：默认 BFS。
需要最少边数：加入 distance，升级为 bfs-unweighted-shortest。
静态分量下 BFS/DFS 同阶，选择状态更易表达者。

Relation	Template	Boundary
增加距离语义	无权图最短路 BFS	要从遍历升级为最少步数。
常见判定器	答案空间二分	can(x) 是阈值下的连通性检查。
可互换遍历	DFS 连通块与可达性	递归聚合比按层顺序更自然。
共享队列外形	拓扑排序 / 入度消除	牢记入队依据是入度归零，不是首次可达。

原创微型例子

环节	内容
Result	a,b,c,d 编号 0，e 编号 1。
Setup	a 连 b、c，c 连 d，e 独立。
Trace	a 出队后 b/c 入队，c 再发现 d；队列清空后处理 e。

Recall prompts

队列里的节点处于 discovered 还是 processed？
为何发现时标记能避免重复？
怎样最小改动得到无权最短路？

数学 / 逻辑形态

识别信号

容易误判的相似信号

核心不变量

状态、转移与处理顺序

Python 骨架

正确性思路

复杂度

边界条件

错误模式

选择与排除规则

相关模板

原创微型例子

Recall prompts

我的补充