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

Question

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

Answer 1

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

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

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

Answer 2

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

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

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

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

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

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

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

Answer 3

@yurib правильно, но есть дальнейшее осложнение.

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