6.3 选择题：遍历状态与复杂度

BFS 的核心容器是队列，DFS 是栈/递归。两者在邻接表上都为 O(V+E)，矩阵上都需扫描 V 行、每行 V 列，为 O(V²)。

手工状态

非连通图只从0出发可能漏点；外层按编号启动会产生若干遍历树，树数等于连通分量数（无向图）。

结构与代码

多选：A BFS可求无权最短路；B DFS序列唯一；C 入队时标记可防重复；D 邻接矩阵遍历必为O(V+E)。答案 A、C。

正确性依据

正确性依赖首次发现状态；序列差异来自邻接枚举顺序，不影响访问集合。

错解反馈

只给起点却声称遍历全图；把访问次数和边扫描次数混淆；忽略有向可达性。

迁移训练

邻接顺序反转，BFS距离会变吗？答案不会；同长度路径的父结点和访问次序可能改变。