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