Разница между BFS и DFS
Я читаю о DFS Введение в алгоритмы Кормена. Ниже приведен фрагмент текста.
В отличие от BFS, чей подграф-предшественник образует дерево, подгруппа-предшественник, создаваемая DFS, может состоять из нескольких деревьев, поскольку поиск может повторяться из нескольких источников.
В дополнение к вышеупомянутым примечаниям, упомянуто следующее.
Может показаться произвольным, что BFS ограничен только одним источником, поскольку DFS может выполнять поиск из нескольких источников. Хотя концептуально BFS может исходить из нескольких источников, а DFS может ограничиваться одним источником, наш подход отражает то, как обычно используются результаты этих поисков.
Мой вопрос
- Кто-нибудь может привести пример того, как BFS используется с несколькими источниками, а DFS используется с одним источником?
2 ответа
Когда он говорит о нескольких источниках, он ссылается на начальный узел поиска. Вы заметите, что параметры алгоритмов BFS(G, s) а также DFS(G), Это уже должно быть намеком на то, что BFS является одним источником, а DFS - нет, поскольку DFS не принимает ни один начальный узел в качестве аргумента.
Основное различие между этими двумя, как указывают авторы, состоит в том, что результатом BFS всегда является дерево, тогда как DFS может быть лесом (коллекцией деревьев). Это означает, что если BFS запускается с узла s, то она построит дерево только из тех узлов, которые достижимы из s, но если в графе есть другие узлы, их не трогать. Однако DFS продолжит поиск по всему графу и создаст лес всех этих связанных компонентов. Это, как они объясняют, желаемый результат каждого алгоритма в большинстве случаев использования.
Как отмечают авторы, ничто не мешает внести небольшие изменения в единый источник DFS. На самом деле это изменение легко. Мы просто принимаем другой параметр sи в рутине DFS (не DFS_VISIT) вместо строк 5-7, повторяющихся во всех узлах графа, мы просто выполняем DFS_VISIT(s),
Точно так же изменение BFS возможно, чтобы он работал с несколькими источниками. Я нашел реализацию в Интернете: http://algs4.cs.princeton.edu/41undirected/BreadthFirstPaths.java.html хотя это немного отличается от другой возможной реализации, которая автоматически создает отдельные деревья. Это означает, что алгоритм выглядит так BFS(G, S) (где S это набор узлов), тогда как вы можете реализовать BFS(G) и сделать отдельные деревья автоматически. Это небольшое изменение в очереди, и я оставлю это в качестве упражнения.
Как указывают авторы, причина, по которой они этого не делают, заключается в том, что основное использование каждого алгоритма делает их полезными сами по себе. Хотя хорошо подумать об этом, это важный момент, который следует понимать.
Вы поняли определение? Вы видели несколько картинок в священной книге?
Когда он говорит, что DFS может состоять из нескольких деревьев, это происходит потому, что он идет глубже, пока не достигает листа, а затем возвращается назад. Итак, представьте себе дерево, сначала вы ищите левое поддерево, а затем правое поддерево. левое поддерево может содержать несколько поддеревьев. вот почему.
Когда вы думаете о BFS, он основан на уровне. Уровень первого поиска другими словами. Таким образом, у вас есть один источник (узел), чем вы ищете все подузлы этого уровня.
DFS с одним источником, если есть только один дочерний узел, поэтому у вас есть только 1 источник. Я думаю, что было бы более понятно, если вы берете источник в качестве родительского узла.