Поиск в ширину против поиска в глубину - PullRequest
Новая
       92

Поиск в ширину против поиска в глубину

0 голосов
/ 19 декабря 2018

Кто-нибудь может дать простое объяснение по BFS и DFS?Я хочу понять, когда предпочитать BFS, а не DFS.

1 Ответ

0 голосов
/ 26 декабря 2018

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

DFS , представьте, что у вас есть следующий график, и мы хотим начатьОбход с узла 1: 

          1
         / \
        2   3
       / \   \
      4   5   6

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

  • начинать с узла1 тогда ищи его детей.Он находит узел 2.
  • , переходит на узел 2, затем ищет его дочерние элементы.Он находит узел 4.
  • , переходит на узел 4, затем обнаруживает, что у него нет дочерних элементов.
  • снова переходит Up на узел 2 и видит его других потомков.Он находит узел 5.
  • , идет к узлу 5, затем обнаруживает, что у него нет дочерних элементов.
  • снова поднимается к узлу 2 и обнаруживает, что у него больше нетchildren.
  • перейдите к узлу 1 и найдите его потомков.Он находит узел 3.
  • , переходит на узел 3 и ищет его дочерние элементы.Он находит узел 6.
  • , переходит в узел 6 и обнаруживает, что у него нет дочерних элементов.
  • переходит в узел 3 и обнаруживает, что у него больше нет дочерних элементов..
  • подойдите к узлу 1 и выясните, что у него больше нет дочерних элементов, поэтому на этом этапе обход графа завершен.

Если вы заметили, как работает этот алгоритмсначала идет на глубину , поэтому, обнаружив, что узел 2 является дочерним узлом 1, он пошел за ним и начал искать своих потомков, не заботясь об остальных дочерних узлах 1(узел 3) в этот момент времени, затем после перехода к самому глубокому из возможных узлов (узлы 4, 5) он начал идти Up, ища остальных потомков узла 1.

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

          1         (level 0)
         / \
        2   3       (level 1)
       / \   \
      4   5   6     (level 2)

Таким образом, обход графика будет следующим:

  • начните с узла 1, затем найдите его дочерние элементы (узлы 2, 3) [следующий уровень].
  • пройти узлы уровня 1 (2, 3) и найти их потомков (узлы 4, 5, 6) [следующий уровень].
  • пройти узлы уровня 2 (4, 5, 6) и найти этих детей (без детей) [без следующего уровня].
  • затем обход графика завершается наэтот момент.

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

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

...