图与BFS和DFS树的等价性

来自 Berkeley CS Course Solution

• 假设输入图 G 是无向的和连接的,但不是树。
• 然后 G 必须包含循环 C 认为 C 由k个节点组成 v1、v2、…、vk 即 C 是循环 v1 v2…vk 第1版 .
• 现在,在 DFS公司 树,节点 v1、v2、…、vk 从根到叶都在同一条路径上。
• 为什么?认为 vf(沃尔沃) 是要访问的第一个节点。然后,必须在 explore(vf) 自从另一个 不及物动词 都是紧密相连的。
• 然而,在 高炉 树,节点 v1、v2、…、vk 将形成至少两个分支,从第一个访问的节点开始分支(想象一下 表演 高炉 在循环中)。因此 高炉 和 DFS公司 制作 同一棵树 敌我识别 输入图形是一棵树。

@dtldarek的另一种方法 math.stackechange :

• 如果图是简单的、连通的和无向的,那么这是真的,最基本的观察结果是,当且仅当在BFS/DFS搜索中遍历了每条边时,G是一棵树。
• 假设TBFS=T=TDFS,但存在eE(G)E(T),也就是说,没有任何算法访问的边缘。
• 未遍历该边的唯一原因可能是已经访问了另一侧的顶点,但如果存在DFS后边缘,则BFS必须以前使用过它。

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

BFS与DFS

dfs和bfs的主要区别在于它们如何从根开始构建树。不同之处在于 当访问一个顶点时,如何访问相邻顶点 。让我们用一种简单的方式处理每个遍历1乘1。

1.BFS(高炉)

1.BFS从访问根开始。 然后,它访问距离根1条边的顶点。 假设有4个顶点a、b、c、d与根相邻。然后,bfs将在访问根之后访问这4个顶点。

2.完成bfs后,访问距根1条边的顶点。然后需要 第一个顶点 在root之后访问并重复相同的过程。哪个顶点是第一个顶点,这由处理 队列数据结构。

这就是为什么在使用BFS遍历树时,它也称为级别顺序遍历。因为它逐级访问顶点 在树的情况下,级别是明确定义的。

DFS公司

1.DFS从访问根目录开始。访问根之后,它不会访问与根相邻的所有顶点,但会深入到图形的深度。

2.一旦访问根,它只访问与根相邻的顶点,然后将从该顶点本身开始dfs,也就是说,在访问与根邻接的所有顶点之前,它会深入。只有在访问了启动dfs的方向的深度顶点后,才会出现这种情况。

值得注意的是,BFS以“自顶向下”的方式构建树,而DFS以“自下而上”的方式创建树

如果这两棵树是相同的,那么当你的图本身是树的时候就是这样。树只能是特殊的两种类型。

这只适用于这样的斜树图形:

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

在这种情况下,bfs和dfs都朝一个方向。

或者一个星形拓扑图,如下所示:

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

证明人声明

与上述两棵树不同的任何其他树都将类似于中间顶点v存在于级别x,并且它在级别x+1上有1个以上的子节点(例如2个)c1和c2。bfs将访问v,然后访问c1和c 2,但dfs将访问v、c1,然后访问c 1的子节点,所以很明显,在这两种情况下,遍历将不同。