图与 BFS 和 DFS 树的等价性

Question

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

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

Answer 1

一旦你理解了 BFS 和 DFS 以及它们之间的基本区别，证明就很简单了。

BFS VS DFS

dfs 和 bfs 之间的主要区别在于它们如何从 root.The 开始构建树的不同之处在于 一旦访问一个顶点，如何访问相邻的顶点 .让我们以简单的方式逐一解决每个遍历。

1.BFS

1.BFS 首先访问根。然后访问距离根 1 条边的顶点。 假设有 4 个顶点 a,b ,c,d 与 root.Then bfs 相邻，访问完 root 后会访问这 4 个顶点。

2.Once bfs 完成访问距离根 1 条边的顶点。然后它取 第一个顶点 在根之后访问并重复相同的 procedure.Which 顶点是第一个，这是由 队列数据结构处理的。

这就是 BFS 也称为层序遍历的原因，当您使用它进行遍历时 trees.Because 它会逐层访问顶点 并且在树的情况下明确定义了层级。

DFS

1.DFS 从访问根目录开始。访问完root后不会访问所有与root相邻的顶点，而是会进入图的深度。

2.Once 它访问根，它只访问与根相邻的顶点，然后将从该顶点本身开始 dfs，即它在访问与根相邻的所有顶点之前进入深度。只有在它开始 dfs 的方向深度访问了顶点后，它才会出现。

需要注意的重要一点是，BFS 以 TOP DOWN 方式构建树，而 DFS 以 BOTTOM UP 方式构建树

如果两棵树相同，那么当您的图形本身是 tree.And 树只能是特殊的两种类型时就是这种情况。

这只能适用于像这样的倾斜树图：

root
|
|
V1
|
|
V2
|
|
.
.
.
Vn

在这种情况下，bfs 和 dfs 都在一个方向上。

或者像这样的星形拓扑图：

               V1
               /
              /
   Vn-----root------V2
          |  \
          |   \
          V4  V3

声明证明

不同于上述两棵树的任何其他树将类似于中间顶点 v 存在于 x 层并且它在 x+1 层有超过 1 个子节点（比如 2）c1 和 c2，bfs 将做的是访问 v，然后访问 c1 和 c2，但是 dfs 将访问 v，然后访问 c1，然后访问 c1 的子节点，所以很明显在这两种情况下遍历不会相同。

Answer 2

来自Berkeley CS Course Solution

Suppose the input graph G is undirected and connected but is not a tree.

Then G must contain a cycle C. Suppose C consists of the k nodes v1, v2, ..., vk i.e. C is the cycle v1 → v2 → . . . → vk → v1.

Now, in the DFS tree, nodes v1, v2, ..., vk will all be on the same path from the root to a leaf.

Why? Suppose vf is the first of these nodes to be visited. Then, the remaining nodes must be visited at some point during explore(vf) since the other vi are all strongly connected.

However, in the BFS tree, nodes v1, v2, ..., vk will form at least two branches, braching from the node first visited (imagine performing BFS on the cycle). Therefore, BFS and DFS produce the same tree iff the input graph is a tree.

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

It is true, if the graph is simple, connected and undirected, and the very basic observation is that G is a tree if and only if every edge was traversed in the BFS/DFS search.

Suppose that TBFS=T=TDFS, but that there is e∈E(G)∖E(T), that is, an edge that was not visited by any of the algorithms.

The only reason the edge was not traversed could be that the vertex on the other side was already visited, but if there is a DFS-back-edge then BFS must have used it before.

图与 BFS 和 DFS 树的等价性

Equivalence of a graph and a BFS and DFS tree

algorithm

graph

tree

depth-first-search

breadth-first-search