Когда указано несколько источников, это относится к начальному узлу поиска. Вы заметите, что параметры алгоритмов: 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)
и автоматически создавать отдельные деревья. Это небольшая модификация очереди, и я оставлю это как упражнение.
Как отмечают авторы, причина, по которой они не сделаны, заключается в том, что основное использование каждого алгоритма придает им полезность, как они есть. Хотя это хорошо сделано для размышлений об этом, это важный момент, который следует понимать.