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

346

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

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

Parth
источник
4
Может быть, вы могли бы упомянуть полные термины для DFS и BFS к вопросу - люди могут не знать эти сокращения.
Ганс-Петер Стёрр
Аналогичный вопрос по информатике : поиск в графе: сначала ширина, а потом глубина
Жиль "ТАК, перестань быть злым"
Возможная копия структуры данных Графики: DFS против BFS?
Сиро Сантилли 郝海东 冠状 病 六四 事件 法轮功
1
programmerinterview.com/index.php/data-structures/dfs-vs-bfs
Канагавелу Сугамар
примечание упоминает некоторые сценарии применения BFS и ДПП
Yossarian42

Ответы:

354

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

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

  • Если дерево очень широкое, BFS может потребоваться слишком много памяти, поэтому оно может быть совершенно непрактичным.

  • Если решения часто, но расположены глубоко в дереве, BFS может быть непрактичным.

  • Если дерево поиска очень глубокое, вам все равно придется ограничить глубину поиска для поиска в глубину (DFS) (например, с итеративным углублением).

Но это всего лишь эмпирические правила; вам, вероятно, нужно будет поэкспериментировать.

Ханс-Петер Стёрр
источник
4
AFAIK-рекурсия обычно требует больше памяти, чем итерация.
Марек Марчак
3
@MarekMarczak Я не совсем понимаю, что вы хотите сказать. Если вы берете BFS в качестве итерации - если пространство решения не легко перечислить, вам может потребоваться сохранить весь n-й уровень дерева поиска в памяти, чтобы перечислить n + 1-й уровень.
Ганс-Петер Стёрр
11
@MarekMarczak Итеративная версия DFS использует стек. Рекурсия против итерации - это отдельная тема.
Клинт Дейгу
Еще один случай, который пришел в голову: BFS полезен (необходим) в случае, когда граф «бесконечен». Как скажем, шахматная доска, которая простирается до бесконечности во всех направлениях. DFS никогда не вернется. BFS гарантированно найдет то, что ищет, если условие выполнено.
ThePartyTurtle
158

Поиск в глубину

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

введите описание изображения здесь

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

Только некоторые пути в игровом дереве ведут к вашей победе. Некоторые приводят к победе вашего противника, когда вы достигаете такого конца, вы должны вернуться назад или вернуться к предыдущему узлу и попробовать другой путь. Таким образом, вы исследуете дерево, пока не найдете путь с успешным завершением. Затем вы делаете первый шаг по этому пути.


Поиск в ширину

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

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

Йогеш Умеш Ваиты
источник
113

Хорошее объяснение с http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/

Пример БФС

Вот пример того, как будет выглядеть BFS. Это что-то вроде обхода дерева порядка уровней, когда мы будем использовать QUEUE с подходом ITERATIVE (в основном, RECURSION заканчивается DFS). Числа представляют порядок, в котором к узлам обращаются в BFS:

введите описание изображения здесь

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

Пример ДФС

Вот пример того, как будет выглядеть DFS. Я думаю, что обратный порядок в двоичном дереве сначала начнет работать с уровня Leaf. Числа представляют порядок, в котором к узлам обращаются в DFS:

введите описание изображения здесь

Различия между DFS и BFS

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

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

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

Канагавелу Сугамар
источник
Что такое «обратный порядок в двоичном дереве»?
Кайл Делани
8
Находит ли DFS кратчайший путь лучше, чем BFS? Я думаю, что это наоборот. Я думаю, что BFS найти кратчайший путь. Не так ли?
Навин Габриэль
1
Был бы признателен больше, если бы вы дали кредиты источнику. Часть сравнения взята из «Структуры данных, упрощенной в Java» Нарасимхи Каруманчи.
learntogrow-growtolearn
Конечно, я могу обновить это, но не ожидаю, что кто-то оценит здесь. Просто хочу помочь бедному технику, как я.
Канагавелу Сугамар
1
@KyleDelaney Есть три порядка, в которых вы можете пройти по дереву - предзаказ, порядок и порядок. Они соответствуют префиксным инфиксным и постфиксным обозначениям соответственно. Когда вы перемещаетесь по дереву вниз, а затем обратно, если вы выбираете узел в первый раз, когда вы посещаете его, это предварительный заказ, если во второй раз он переупорядочивается, если в последний раз он переупорядочивается. На самом деле вы можете сериализовать дерево таким образом и, если вы помните порядок, который вы использовали, вы можете перестроить дерево из сериализации.
Дэйв
43

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

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

Ник Джонсон
источник
26

DFS более компактен, чем BFS, но может пойти на ненужную глубину.

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


По IDDFS

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

polygenelubricants
источник
1
Это не обязательно более экономно. Рассмотрим, например, граф путей.
РБ
16

Когда вы подходите к этому вопросу как к программисту, выделяется один фактор: если вы используете рекурсию, тогда поиск в глубину проще реализовать, потому что вам не нужно поддерживать дополнительную структуру данных, содержащую узлы, которые еще предстоит исследовать.

Вот поиск в глубину для неориентированного графа, если вы храните «уже посещенную» информацию в узлах:

def dfs(origin):                               # DFS from origin:
    origin.visited = True                      # Mark the origin as visited
    for neighbor in origin.neighbors:          # Loop over the neighbors
        if not neighbor.visited: dfs(next)     # Visit each neighbor if not already visited

При хранении «уже посещенной» информации в отдельной структуре данных:

def dfs(node, visited):                        # DFS from origin, with already-visited set:
    visited.add(node)                          # Mark the origin as visited
    for neighbor in node.neighbors:            # Loop over the neighbors
        if not neighbor in visited:            # If the neighbor hasn't been visited yet,
            dfs(node, visited)                 # then visit the neighbor
dfs(origin, set())

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

Жиль "ТАК - перестань быть злым"
источник
5

Для BFS мы можем рассмотреть пример Facebook. Мы получаем предложение добавить друзей из профиля FB из профиля других друзей. Предположим, что A-> B, а B-> E и B-> F, поэтому A получит предложение для E And F. Они должны использовать BFS для чтения до второго уровня. DFS больше основан на сценариях, в которых мы хотим прогнозировать что-то на основе данных, которые мы имеем от источника до места назначения. Как уже упоминалось о шахматах или судоку. Как только у меня все по-другому, я считаю, что DFS следует использовать для кратчайшего пути, потому что DFS сначала будет покрывать весь путь, а затем мы сможем выбрать лучший. Но так как BFS будет использовать подход жадности, может показаться, что это самый короткий путь, но конечный результат может отличаться. Дайте мне знать, верно ли мое понимание.

user2056463
источник
Теперь мой комментарий немного опоздал. Но чтобы найти кратчайший путь, следует использовать BFS. Тем не менее, «DFS больше основывается на сценариях, в которых мы хотим прогнозировать что-то на основе данных, которые мы имеем от источника до места назначения», - это блестящая вещь, которую вы сказали! Престижность !!
Оскарзито
4

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

Рафал Доугирд
источник
4

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

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

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

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

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

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

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

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

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

Мосаб Шахин
источник
2

По свойствам DFS и BFS. Например, когда мы хотим найти кратчайший путь. мы обычно используем BFS, это может гарантировать «самый короткий». но только dfs может гарантировать, что мы можем прийти с этой точки, может достичь этой точки, не может гарантировать «самый короткий».

yeuyanglou
источник
2

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

  1. кратчайший путь на простом графике -> BFS
  2. все возможные результаты -> DFS
  3. поиск по графику (трактуйте дерево, мартикс как график) -> dfs ....
BenDan
источник
Если вы добавите пустую строку перед списком, ответ будет выглядеть намного лучше.
Монтонерос
1

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

Дж. Майкл Вюрт
источник
1

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

nil96
источник
0

Это хороший пример, чтобы продемонстрировать, что 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,
coderek
источник
0

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

ankur314
источник