algorithm - 图与 BFS 和 DFS 树的等价性

Question

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

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

Answer 1

来自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.