DFS (深度优先搜索)树的DFS深度算法

Question

根植于顶点的任何DFS (深度优先搜索)树的深度至少与根植于同一顶点的任何BFS树的深度相同。对还是错？

我不明白这句话意味着什么？它要求的是堆栈深度吗？

请用这个例子解释

Answer 1

搜索树的深度是从根到叶的最长路径的长度(以边数表示)。

问题是让您比较两种搜索算法，DFS和BFS，更具体地说，它们的搜索树是从同一个顶点开始的。

下面是一个示例图(它是无向的)：

​

假设选定的根顶点是"a“。我们可以想象一个DFS按以下顺序访问顶点:a。在e，没有更多的邻居还没有被访问，所以DFS算法返回到d，然后扩展到f，然后又一直回溯到根，却发现没有其他的顶点可访问。

因此，DFS的搜索树是：

​

​

最长的路径有4条边，所以我们说这个搜索树的深度是4：

• a-b-c-d-e
• a-b-c-d-f

让我们使用BFS进行搜索。在第一轮中，所有的邻居都会被拜访：

• a-b
• a-d
• a-e

然后将这些路径中的每一条扩展到尚未被访问的相邻顶点：

• a-b-c
• a-d-f

在e，没有更多的扩展可能。已经访问了所有的顶点。BFS搜索树如下：

​

​

因此，BFS找到了这些路径，其中最长的有2条边，因此搜索树的深度为2：

• a-b-c
• a-d-f
• a-e

因此，在这种情况下，DFS搜索树的深度大于BFS搜索树的深度。

您应该证明，BFS搜索树永远不会比DFS搜索树更深的情况(对于相同的图和相同的起始顶点)。

Answer 2

树的深度。意思是从树根到另一个节点的最短路径的最大长度。