如何证明括号定理对广度优先搜索（BFS）不成立？

括号定理的核心回顾 #

在深度优先搜索（DFS）中，任意两个节点u和v的发现-完成时间区间[d[u], f[u]]和[d[v], f[v]]必然满足以下三者之一：

• 区间完全不相交，且u、v彼此不是对方的后代；
• [d[u], f[u]]完全包含在[d[v], f[v]]内，且u是v的后代；
• [d[v], f[v]]完全包含在[d[u], f[u]]内，且v是u的后代。

要证明该定理对BFS不成立，只需构造一个反例：找到一个图及其BFS遍历的时间戳，使得存在两个节点的区间既不嵌套也不相交，同时其中一个是另一个的后代。

具体反例构造 #

我们使用简单的链式图 s → a → b，定义BFS时间戳规则：

• 发现时间d[x]：节点首次被访问（加入队列）的时刻；
• 完成时间f[x]：节点出队后，遍历完所有未访问邻接节点的时刻。

BFS遍历的时间线：

1. 初始状态：所有节点未访问，队列为空。
2. 访问节点s，记录d[s] = 1，将s加入队列。
3. 出队s，遍历其邻接节点a：
   • a未访问，记录d[a] = 2，将a加入队列；
   • 处理完s的所有邻接节点，记录f[s] = 3。
4. 出队a，遍历其邻接节点s（已访问）和b：
   • b未访问，记录d[b] = 4，将b加入队列；
   • 处理完a的所有邻接节点，记录f[a] = 5。
5. 出队b，遍历其邻接节点a（已访问）：
   • 无未访问节点，记录f[b] = 6。

区间分析

各节点的发现-完成时间区间：

• s: [1, 3]
• a: [2, 5]
• b: [4, 6]

观察s和a的关系：s是a在BFS树中的父节点（a是s的后代），但它们的区间[1,3]和[2,5]既不嵌套（f[a]=5大于f[s]=3，a的区间超出了s的区间），也不完全不相交（重叠部分为[2,3]）。这直接违反了括号定理的核心要求——父节点的区间必须完全包含后代节点的区间。

结论 #

通过上述反例可直接证明：括号定理的核心性质在BFS中不成立，因此该定理不适用于广度优先搜索。

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