Блог

Я читаю об DFS этом во Введении к алгоритмам Кормена. Ниже приведен фрагмент текста.

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

В дополнение к приведенным выше замечаниям упоминается следующее.

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

Мой вопрос

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

Когда он говорит о нескольких источниках, он ссылается на начальный узел поиска. Вы заметите, что параметры алгоритмов равны BFS(G, s) и DFS(G) . Это уже должно быть намеком на то, что BFS имеет один источник, а DFS — нет, поскольку DFS не принимает какой-либо начальный узел в качестве аргумента.

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

Как упоминали авторы, ничто не мешает небольшим изменениям сделать DFS единственным источником. На самом деле это изменение простое. Мы просто принимаем другой параметр s , и в подпрограмме DFS (not 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 источник. я думаю, было бы более понятно, если вы возьмете источник в качестве родительского узла.