Почему вы гарантированно найдете свой результат, если он находится на графике с BFS, но не с DFS?

Question

Я где-то читал, что DFS не гарантирует, что найдет решение, а BFS ... почему? Я действительно не понимаю, как это правда .. может кто-то продемонстрировать мне случай, который доказывает это?

Answer 1

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

root -> v1 -> v2-> v3 -> ... продолжается вечно
| -> u.

в этом примере, если DFS начинается с корня, а затем переходит к v1.оно никогда не достигнет вас, поскольку ветвь, в которую он вошел, бесконечна.BFS перейдет от root к v1 или u, а затем к другому.

Answer 2

Вывод как DFS, так и BFS (на графах с конечным числом вершин) заканчивается и дает путь (или, скорее, дерево, но OP, кажется, интересуется только одним путем этого дерева).Неважно, есть ли в графе циклы, потому что обе процедуры хранят записи о том, какие вершины уже были посещены, и, таким образом, избегают посещения одной и той же вершины более одного раза.Любая вменяемая реализация DFS / BFS делает это - в противном случае вы будете ограничены только ациклическими графами (см. Псевдокод, приведенный в CLRS).

Как упомянуто @yurib, если граф имеет бесконечное число узлов,DFS может занять вечность.Поскольку существуют бесконечные узлы, мы не можем практически отследить, какие вершины уже были посещены (что заняло бы потенциально бесконечную память), и даже если бы мы это сделали, возможно, существует бесконечный путь, содержащий уникальные вершины, которые не содержат искомую вершину, которую мы ищем.

Однако это не единственная причина, по которой DFS не всегда находит кратчайший путь.Даже в конечных графах DFS может не найти кратчайший путь.

Основная причина в том, что BFS всегда исследует все узлы на расстоянии x от корня, прежде чем перейти к узлам на расстоянии x + 1.Таким образом, если узел находится на расстоянии k, мы можем быть уверены, что минимальное расстояние от корня до этого узла равно k, а не k-1, k-2, ..., 0 (иначе мы бы столкнулись с ним раньше).

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

На изображении выше BFS будет исследовать B и Eсначала, а затем достигните D через E - давая нам путь к D как root-> E-> D.DFS может начать поиск с B сначала, найдя путь root-> B-> C-> D, который явно не самый короткий.

Обратите внимание, что решающее решение было пойти на исследование B, прежде чем E. DFS вполне могли бы выбрать E и прийти к правильному ответу.Но, как правило, нет способа узнать, по какому пути идти первым (если бы мы знали, что в любом случае знаем самый короткий путь).Для DFS путь, который он находит, просто зависит от порядка, в котором он исследует последующие узлы, которые могут или не могут дать кратчайший путь.

Answer 3

@ Юриб правильный, но есть еще одно осложнение.

Если нужная вершина НЕ находится в графе, то ни BFS, ни DFS не прекратят работу, если есть цикл ... если вы не предпримете шаги для обнаружения циклов.И если вы предпринимаете шаги для обнаружения циклов, и BFS, и DFS прекратят работу.