Algorithms DFS depth of any DFS (Depth First Search) tree

Question

The depth of any DFS (Depth First Search) tree rooted at a vertex is atleast as depth of any BFS tree rooted at the same vertex. True or False?

I don't understand what this statement means depth of what? Is it asking for stack depth ?

Please explain with the example

Answer 1

The depth of a (search) tree is the length of the longest path (expressed in number of edges) from root to leaf that such a tree has.

The question is asking you to compare two search algorithms, DFS and BFS, and more specifically their search trees, which start at the same vertex.

Here is an example graph (it is undirected):

Let's say the chosen root vertex is "a". We can imagine a DFS that visits vertices in the following order: a-b-c-d-e. At e there is no more neighbor that has not yet been visited, so the DFS algorithm backtracks to d and then extends to f. It then backtracks again all the way to the root, only to find there is no other vertex to visit.

So the search tree of DFS is:

The longest paths have 4 edges, so we say that the depth of this search tree is 4:

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

Let's do the search with BFS. In a first round all the neighbors of a are visited:

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

Then each of these paths are extended to neighboring vertices that are not visited yet:

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

At e there is no more extension possible. All vertices have been visited. The BFS search tree is as follows:

BFS has thus found these paths, of which the longest have 2 edges, so the depth of this search tree is 2:

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

So in this case the depth of the DFS search tree is greater than the depth of the BFS search tree.

It is up to you to prove that you can never have the situation where the BFS search tree is deeper than the one of the DFS search tree (for the same graph and same starting vertex).