Когда целесообразно использовать поиск в глубину (DFS) по сравнению с поиском в ширину (BFS)?

Question

Я понимаю разницу между DFS и BFS, но мне интересно знать, когда практичнее использовать один поверх другого?

Может ли кто-нибудь привести примеры того, как DFS превзойдет BFS и наоборот?

Answer 1

Ниже приводится исчерпывающий ответ на ваш вопрос.

Проще говоря:

Алгоритм поиска в ширину (BFS), от его имени «Ширина», обнаруживает всех соседей узла через внешние ребра узла, затем он обнаруживает невидимых соседей ранее упомянутых соседей через их внешние ребра и так далее до тех пор, пока не будут посещены все узлы, доступные из исходного источника (мы можем продолжить и взять другой исходный источник, если есть оставшиеся не посещенные узлы и т. д.). Вот почему его можно использовать для поиска кратчайшего пути (если он есть) от узла (исходного источника) к другому узлу, если вес ребер одинаков.

Алгоритм поиска в глубину (DFS), получивший название «Глубина», обнаруживает невидимые соседи самого последнего обнаруженного узла x через его внешние ребра. Если нет невидимого соседа от узла x, алгоритм возвращает назад, чтобы обнаружить не посещенных соседей узла (через его внешние края), из которого был обнаружен узел x, и так далее, пока все узлы, достижимые из исходного источника, не будут посещены (мы можем продолжить и взять другой исходный источник, если останутся не посещенные узлы и т. д.).

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

Следовательно, мы можем сделать вывод, когда использовать BFS и DFS. Предположим, мы имеем дело с управляемым ограниченным фактором ветвления и управляемой ограниченной глубиной. Если искомый узел пологий, т. Е. Достижим после некоторых ребер из исходного источника, то лучше использовать BFS. С другой стороны, если искомый узел является глубоким, то есть достижимым после большого количества ребер из исходного источника, тогда лучше использовать DFS.

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

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

В конце концов, если мы имеем бесконечную глубину и бесконечный коэффициент ветвления, мы можем использовать итеративный углубленный поиск (IDS).

Answer 2

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

Answer 3

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

Answer 4

Я думаю, это зависит от того, с какими проблемами вы сталкиваетесь.

1. кратчайший путь на простом графе -> bfs
2. все возможные результаты -> dfs
3. поиск на графе (трактуйте дерево, мартикс как граф) ->дфс ....

Answer 5

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

Answer 6

Это хороший пример, чтобы продемонстрировать, что BFS в некоторых случаях лучше, чем DFS.https://leetcode.com/problems/01-matrix/

При правильном применении оба решения должны посещать ячейки, которые находятся дальше, чем текущая ячейка +1.Но DFS неэффективен и неоднократно посещал одну и ту же ячейку, что приводит к сложности O (n * n).

Например,

1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
0,0,0,0,0,0,0,0,