图与 BFS 和 DFS 树的等价

Question

我有这个问题，我无法证明。有人可以对这个问题提供一些见解吗

我们有一个连通图 G = (V,E)，并且作为特定的顶点 u ? V.假设我们计算一个以 u 为根的深度优先搜索树，并得到一棵包含 G 的所有节点的树 T。假设我们然后计算一个以 u 为根的广度优先搜索树，并得到相同的树 T。证明G = T。（换句话说，如果 T 既是深度优先搜索树，又是以 u 为根的广度优先搜索树，则 G 不能包含任何不属于 T 的边。）

Answer 1

来自伯克利 CS 课程解决方案

• 假设输入图G是无向且连通的，但不是树。
• 那么G必须包含一个循环C。假设C由 k 个节点v1, v2, ..., vk 组成，即C是循环v1 ？v2 ? . . . ? vk ? v1 .
• 现在，在DFS树中，节点v1、v2、...、vk都将位于从根到叶的同一路径上。
• 为什么？假设vf是这些节点中第一个被访问的节点。然后，剩余的节点必须在某个时间点被访问，explore(vf) 因为其他vi都是强连接的。
• 但是，在BFS树中，节点v1、v2、...、vk至少会形成两个分支，从最先访问的节点开始（想象在循环上执行BFS）。因此，当输入图是一棵树时，BFS和DFS产生相同的树。

@dtldarek 在math.stackechange 中的另一种方法：

• 这是真的，如果图是简单的、连通的和无向的，并且非常基本的观察是 G 是一棵树，当且仅当在 BFS/DFS 搜索中遍历每条边。
• 假设TBFS=T=TDFS，但是存在e?E(G)?E(T)，即任何算法都没有访问过的边。
• 这条边没有被遍历的唯一原因可能是另一边的顶点已经被访问过，但是如果有一个 DFS-back-edge 那么 BFS 之前肯定已经使用过它。