图与BFS和DFS树的等价性

Question

我有一个问题无法证明。能否有人提供一些关于这个问题的见解？

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

- Ankit Mishra

---

如有任何疑问，请随时提出。 - Sumeet

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回边，则BFS必须先使用它。

- Gilad Gur

Answer 2

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

BFS和DFS之间的主要区别在于它们从根节点开始构建树的方式。当访问了一个顶点后，它们访问相邻顶点的方式不同。我们逐个遍历这两种方法。

1. BFS

BFS从访问根节点开始。然后它会访问距离根节点1个边的顶点。假设有4个与根节点相邻的顶点a、b、c、d，则BFS将在访问根节点后立即访问这4个顶点。

2. 一旦BFS完成了访问距离根节点1个边的顶点，它会取第一个访问过的顶点并重复相同的过程。哪个顶点是第一个，这由队列数据结构处理。

这就是为什么当你用它来遍历树时，BFS也被称为层序遍历。因为它逐层访问顶点，并且在树的情况下，层级是清晰定义的。

2. DFS

DFS从访问根节点开始。它不会在访问根节点后访问所有与根节点相邻的顶点，而是会深入图的深处。

一旦它访问了根节点，它只会访问与根节点相邻的顶点，然后会从那个顶点本身开始进行DFS，也就是说，在访问所有与根节点相邻的顶点之前，它会先进入它开始DFS的方向的深度。只有在访问了该方向上的顶点后，它才会回到这些顶点。

所以需要注意的重要事情是，BFS以自上而下的方式构建树，而DFS以自下而上的方式构建树。

如果两棵树相同，那么你的图本身就是一棵树。而树只能是特殊的两种类型之一。

这只对斜树这样的图形成立：

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

在这种情况下，广度优先搜索和深度优先搜索都沿着一个方向进行。

或者是像这样的星型拓扑结构图：

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

通过语句证明

与上述两棵树不同的任何其他树都将是这样的：一个中间顶点v存在于x级别，并且它在x+1级别有多于1个孩子（比如说2个）c1和c2。BFS将访问v，然后访问c1和c2，但是DFS将访问v，然后访问c1，然后访问c1的子节点，因此明显这两种情况下的遍历方式是不同的。

- Sumeet

---

我不理解DFS是如何自下而上构建树的。因为它并不是先构建所有叶子节点，然后再向上一层，以此类推直到顶部。它会遍历整个树的深度，然后继续访问根节点的下一个邻居。所以我不清楚什么是自下而上的方式。你能否解释一下？因为我无法看到所有叶子节点首先被访问，然后是下一层，以此类推。 - Ankit Mishra

@AnkitMishra 你是对的，但我的意思是首先完成树的较低层级，然后再完成上层层级。 - Sumeet

而且我知道这对于这两个图形是成立的。但是让我们考虑一个一般情况，考虑G中不存在的边（u，v），它不在T中。我如何证明这条边也将存在于T中。我认为这将证明任何一般情况。如果您能提供一些解释，那将非常好。 - Ankit Mishra