Я изучил два алгоритма обхода графа, поиск в глубину и поиск в ширину. Поскольку оба алгоритма используются для решения одной и той же проблемы обхода графа, я хотел бы знать, как выбирать между ними. Я имею в виду, что один более эффективен, чем другая или какая-либо причина, по которой я бы предпочел одно другому в конкретном сценарии?
Спасибо
Главное отличие для меня в некоторой степени теоретическое. Если бы у вас был граф бесконечного размера, DFS никогда бы не нашел элемент, если он существует за пределами первого пути, который он выбирает. По сути, он будет продолжать идти по первому пути и никогда не найдет элемент. В конечном итоге BFS найдет элемент.
Если размер графа конечен, DFS, скорее всего, быстрее обнаружит элемент выброса (большее расстояние между корнем и целью), тогда как BFS быстрее найдет более близкий элемент. За исключением случая, когда DFS выбирает путь мелкого элемента.
В общем, BFS лучше подходит для задач, связанных с поиском кратчайших путей или связанных с этим проблем. Потому что здесь вы переходите от одного узла ко всем смежным с ним узлам и, следовательно, эффективно переходите от длины пути один к длине пути два и так далее.
В то время как DFS на другом конце помогает больше в проблемах с подключением, а также в поиске циклов на графике (хотя я думаю, что вы также сможете найти циклы с небольшой модификацией BFS). Определение возможности подключения с помощью DFS тривиально, если вы дважды вызываете процедуру исследования из процедуры DFS, то граф отключается (это для неориентированного графа). Здесь вы можете увидеть сильно связанный компонентный алгоритм для ориентированного графа, который является модификацией DFS. Еще одно применение DFS - топологическая сортировка.
Вот некоторые применения обоих алгоритмов:
DFS:
Связность
Сильно связанные компоненты
Топологическая сортировка
BFS:
Кратчайший путь (Дейкстра - это своего рода модификация BFS).
Проверка двупартийности графа.
При обходе многосвязного графа порядок обхода узлов может сильно влиять (на много порядков) на количество узлов, которые будут отслеживаться методом обхода. Некоторые виды алгоритмов будут намного лучше при использовании в первую очередь в ширину; другие будут намного лучше при использовании глубинного поиска.
С одной стороны, выполнение поиска в глубину в двоичном дереве с N листовыми узлами требует, чтобы метод обхода отслеживал узлы lgN, в то время как поиск в ширину потребовал бы отслеживания как минимум N / 2 узлов (поскольку он может сканировать все остальные узлы перед сканированием любых листовых узлов; непосредственно перед сканированием первого листового узла он обнаружил бы N / 2 родительских узлов листьев, которые должны отслеживаться отдельно, поскольку ни один из них не ссылается друг на друга).
С другой стороны, выполнение заливки в сетке NxN с помощью метода, который, если его пиксель еще не был окрашен, окрашивает этот пиксель, а затем заливает его соседей, потребует постановки в очередь координат пикселей O (N) при использовании поиск в ширину, но координаты пикселей O (N ^ 2) при использовании поиска в глубину. При использовании поиска в ширину будет казаться, что краска «растекается» независимо от формы, которую нужно нарисовать; при использовании алгоритма в глубину для рисования прямоугольной спирали, каждая линия которой прямая с одной стороны и зубчатая с другой (какие стороны должны быть прямыми и зубчатыми, зависит от точного используемого алгоритма), все прямые участки будут окрашены перед любыми зазубринами, что означает, что система должна отслеживать местоположение каждой зазубрины отдельно.
Для полного / идеального дерева DFS занимает линейное количество пространства по отношению к глубине дерева, тогда как BFS занимает экспоненциальный объем пространства по отношению к глубине дерева. Это связано с тем, что для BFS максимальное количество узлов в очереди пропорционально количеству узлов на одном уровне дерева. В DFS максимальное количество узлов в стеке пропорционально глубине дерева.
