Алгоритмы DFS глубины любого дерева DFS (Depth First Search)

Question

Глубина любого дерева DFS (поиск в глубину) с корнем в вершине не меньше глубины любого дерева BFS с корнем в той же вершине. Верно или неверно?

Я не понимаю, что означает это утверждение, глубина чего? Требуется ли глубина стека?

Пожалуйста, объясните на примере

Answer 1

Глубина дерева. Это означает, что максимальная длина кратчайшего пути от root до другого узла в дереве.

Answer 2

Глубина (поискового) дерева - это длина самого длинного пути (выраженного в количестве ребер) от root до листа, который имеет такое дерево.

Вопрос просит вас сравнить два алгоритма поиска, DFS и BFS, а точнее их деревья поиска, которые начинаются в одной и той же вершине.

Вот пример графа (он неориентированный):

Допустим, выбранная вершина root - "a" . Мы можем представить себе DFS, который посещает вершины в следующем порядке: ab- c -de . В e больше нет соседа, который еще не был посещен, поэтому алгоритм DFS возвращается к d , а затем расширяется до f . Затем он снова возвращается к root, но обнаруживает, что другой вершины нет.

Итак, дерево поиска DFS:

Самые длинные пути имеют 4 ребра, поэтому мы говорим, что глубина этого дерево поиска - 4:

• ab- c -de
• ab- c -df

Сделаем поиск с помощью BFS. В первом раунде посещаются все соседи a :

• ab
• ad
• ae

Затем каждый из этих путей расширяется до соседних вершин, которые еще не посещены:

• ab- c
• adf

При e расширение невозможно. Все вершины посещены. Дерево поиска BFS выглядит следующим образом:

Таким образом, BFS нашла эти пути, из которых у самого длинного есть 2 края, поэтому глубина этого поиска дерево равно 2:

• ab- c
• adf
• ae

Таким образом, в этом случае глубина дерева поиска DFS больше, чем глубина дерева поиска BFS.

Это ваше дело доказать, что у вас никогда не будет ситуация, когда дерево поиска BFS глубже, чем дерево поиска DFS (для того же графа и той же начальной вершины).