无向图BFS中不存在回边与前向边？我的反例与权威结论存疑

我认为这一结论并不正确，以下是我的反例（图以邻接表形式表示）：

0 : 1
1 : 0, 1, 2
2 : 1, 3, 3
3 : 2, 2

在该示例中，顶点编号为0至3，顶点1存在自环，顶点2与3之间存在多条边。对该图执行BFS后得到树0-1-2-3，顶点右侧的节点为其后代。顶点1的自环根据定义可被视为前向边或回边；2与3之间的多条边中，一条为树边，其余则可被视为前向边或回边。

令我困惑的是，网络资料及CLRS教材均指出无向图BFS中不存在回边和前向边。以下是教材原文：

[...]证明在无向图的广度优先搜索中，以下性质成立：

1. 不存在回边和前向边。
2. 对于每条树边(u, v)，有v.d = u.d + 1。
3. 对于每条交叉边(u, v)，有v.d = u.d 或 v.d = u.d + 1。

我是否忽略了什么关键点？

你忽略的核心关键点在于CLRS中对无向图BFS边分类的前提定义，以及回边、前向边在无向图语境下的特殊处理：

1. 教材默认讨论「简单无向图」
   CLRS的结论是基于无自环、无重边的简单无向图展开的，你的例子包含的自环和重边属于特殊情况，不在默认讨论范围内：

   • 自环：在无向图BFS的标准定义中，自环会被归类为特殊的交叉边，或在遍历中直接跳过（访问自身时，自身已标记为已访问且不是父节点），不会被视为回边或前向边。
   • 重边：2到3的多条边中，第一条成为树边，后续边遍历到的时候，3已处于已访问状态且不是2的父节点（2的父节点是1），因此这些重边会被归类为交叉边，而非回边或前向边。

2. 无向图中回边/前向边的定义不适用
   回边和前向边是针对有向图定义的：

   • 回边：节点指向其祖先的边
   • 前向边：节点指向其后裔的边
     无向图的边是双向的，遍历边u->v时，若v已被访问：
   • 若v是u的父节点，这是树边的反向，直接跳过，不归类为非树边；
   • 若v不是u的父节点，此时v和u的距离差只能是0或1（对应CLRS第三条性质），这类边被统一归为交叉边——因为无向图没有明确方向，无法区分「祖先指向后代」或「后代指向祖先」，自然不会产生回边或前向边。

3. 标准BFS的遍历规则
   标准BFS处理节点u的邻接节点v时：

   • 若v未被访问，标记u为v的父节点，将v入队，这条边是树边；
   • 若v已被访问且不是u的父节点，这条边视为交叉边；
   • 若v是u的父节点，直接忽略（避免重复处理无向边的反向）。
     你的例子中的自环和重边，都会被归为第二类或直接忽略，因此不会产生回边或前向边。

总结来说，CLRS的结论针对的是标准简单无向图的BFS，你引入的自环和重边属于特殊情况，在教材的定义框架下，这些边不会被归类为回边或前向边。

内容的提问来源于stack exchange，提问作者Infinite