Когда это практично, чтобы использовать поиском в глубину (DFS) и против поиска в ширину (поиск в ширину)?

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

пример BFS

вот пример того, как будет выглядеть BFS. Это что-то вроде обхода дерева порядка уровней, где мы будем использовать очередь с итерационным подходом (в основном рекурсия закончится DFS). Цифры означают порядок, в котором узлы доступны в БФС:

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

пример DFS

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

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

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

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

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

глубину

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

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

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

---

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

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

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

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

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

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

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

---

на IDDFS

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

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

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

вот глубина-первый поиск неориентированного графа, если вы храните" уже посещенную " информацию в узлах:

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())

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

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

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

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

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

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

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

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

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