首页 文章

图形与BFS和DFS树的等价性

提问于
浏览 次
1

我有这个问题，我无法证明 . 有人可以提供一些洞察这个问题

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

algorithm graph tree depth-first-search breadth-first-search

1 回答

  • 4

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

    BFS VS DFS

    dfs和bfs之间的主要区别在于它们是如何从root开始构建树的 . 一旦访问顶点，如何访问相邻顶点就会出现差异 . 让我们以简单的方式逐个遍历每个遍历 .

    1.BFS

    1.BFS首先访问root.It然后访问距离root 1个边缘的顶点 . 假设有4个顶点a，b，c，d与root相邻 . 然后bfs将在访问root之后访问这4个顶点 .

    2.一旦bfs完成访问距离根1边缘的顶点 . 然后在root之后访问 first vertex 并重复相同的过程 . 哪个顶点是第一个，这由 queue data structure. 处理

    这就是BFS也被称为级别顺序遍历的原因，当你使用它来遍历树时 . 因为它逐级访问顶点 and levels are clearly defined in case of tree.

    DFS

    1.DFS首先访问root . 访问root后，它不会访问与root相邻的所有顶点，但会进入图的深度 .

    2.一旦访问root，它只访问与root相邻的顶点，然后从该顶点本身启动dfs，即在访问与root相邻的所有顶点之前进入深度 . 只有在它开始dfs的方向深度访问顶点时才会到达它们 .

    So important thing to observe is that BFS builds the tree in TOP DOWN fashion while DFS builds the tree in BOTTOM UP fashion

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

    对于像这样的倾斜树的图形，这只能是正确的：

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

    在这种情况下，bfs和dfs都朝着一个方向 .

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

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

    Proof By statement

    与上面两棵树不同的任何其他树将类似于中间顶点v在x级存在并且它具有多于1个子节点（比如2）c1和c2在级别x 1，bfs将做什么是访问v然后c1和c2，但是dfs会做的是访问v然后是c1然后是c1的子代，所以在这两种情况下，遍历不会是相同的 .

    回复于

相关问题