Я изучил два алгоритма обхода графа, первый поиск по глубине и первый поиск по ширине. Поскольку оба алгоритма используются для решения одной и той же проблемы обхода графика, я хотел бы знать как выбрать между ними. Я имею в виду, что это эффективнее, чем другая, или по какой-либо причине, почему я бы выбрал один из них в конкретном сценарии?Преимущество глубины первого поиска по ширине первого поиска или наоборот
Thank you
Основное отличие от меня несколько теоретическое. Если бы у вас был граф с бесконечным размером, тогда DFS никогда не найдет элемент, если он существует вне первого выбранного пути. Он по существу продолжит идти по первому пути и никогда не найдет элемент. BFS в конечном итоге найдет элемент.
Если размер графика конечный, DFS, скорее всего, найдет элемент outlier (большее расстояние между корнем и целью) быстрее, когда BFS быстрее найдет более близкий элемент. За исключением случая, когда DFS выбирает путь неглубокого элемента.
Это не плохой ответ, но DFS и BFS могут сбой в бесконечном случае - DFS может выйти из строя, если график бесконечно глубокий, а BFS может работать. Тем не менее, DFS будет работать, если граф не бесконечно глубокий, а бесконечно * широкий * - в то время как BFS не удастся. Пересечение бесконечных графов (из того, что я понимаю) сильно отличается от пересечения конечных графов. –
В целом, BFS лучше справляется с проблемами, связанными с поиском кратчайших путей или некоторыми связанными проблемами. Потому что здесь вы переходите от одного узла ко всему узлу, который находится рядом с ним, и, следовательно, вы фактически перемещаетесь от длины пути один к длине пути два и так далее.
В то время как DFS на другом конце помогает больше в проблемах с подключением, а также в поиске циклов в графике (хотя я думаю, что вы можете найти циклы с небольшим изменением BFS тоже). Определение связи с DFS тривиально, если вы дважды вызываете процедуру исследования из процедуры DFS, тогда график отключается (это для ненаправленного графика). Здесь вы можете увидеть сильно связанный компонентный алгоритм для ориентированного графа, который является модификацией DFS. Другим применением DFS является топологическая сортировка.
Вот некоторые приложения обоих алгоритмов:
DFS:
Connectivity
Сильно Connected Components
Топологическая Сортировка
BFS:
кратчайшего пути (Дейкстра является то, что некоторые модификации BFS).
Проверка, является ли график Двусторонней.
Для полного/идеального дерева DFS занимает линейное пространство относительно глубины дерева, тогда как BFS занимает экспоненциальное пространство по отношению к глубине дерева. Это связано с тем, что для BFS максимальное количество узлов в очереди пропорционально количеству узлов на одном уровне дерева. В DFS максимальное количество узлов в стеке пропорционально глубине дерева.
При перемещении многосвязного графика порядок прохождения узлов может значительно повлиять (на много порядков) количество узлов, которые будут отслеживаться методом перемещения. Некоторые виды алгоритмов будут значительно лучше при использовании ширины; другие будут значительно лучше при использовании поиска глубины.
С одной стороны, выполнение поиска по глубине в двоичном дереве с N листовыми узлами требует, чтобы метод перемещения отслеживал узлы lgN, в то время как поиск в ширину потребовал бы отслеживания не менее N/2 узлов (так как он может сканировать все остальные узлы до того, как он сканирует любые листовые узлы, сразу перед сканированием первого листового узла он столкнулся бы с N/2 родительских узлов листьев, которые нужно отслеживать отдельно, поскольку ни один из них не ссылается друг на друга) ,
С другой стороны, делая заливку заливки сеткой NxN с помощью метода, который, если его пиксель еще не был окрашен, цвета, которые пиксель, а затем наводнения для его соседей, потребуют запирания O (N) пиксельные координаты при использовании поиска по ширине, но O (N^2) пиксельные координаты при использовании глубины-первой. При использовании поиска по ширине краска будет казаться «разбросанной», независимо от формы, которую нужно нарисовать; при использовании алгоритма глубины для рисования прямоугольной спирали, каждая линия которой прямая с одной стороны и зубчатая на другой (какие стороны должны быть прямыми и зубчатыми, зависит от используемого точного алгоритма), все прямые участки будут окрашены перед любой из зубчатых, что означает, что система должна отслеживать местоположение каждого зубца отдельно.
В некоторых языках, а также BFS является немного лучшим выбором , потому что самая простая реализация DFS является рекурсивной, который вводит накладные расходы, а также может привести ваш код достиг предельного размера стека для больших графов. Очевидным преимуществом (и приложением) BFS является , что в невзвешенных графах его можно использовать для построения кратчайшего пути от u до v. У этого есть множество приложений - например, вы можете вычислить наименьшее количество ходов необходимо решить заданную головоломку , запустив BFS в ее пространстве состояний. BFS может даже дать вам кратчайшие расстояния от одной вершины u ко всем остальным вершинам на графике: для каждой вершины просто запомните край, который использовался для .
см. Http://stackoverflow.com/questions/687731/breadth-first-vs-depth-first ... содержит полезную информацию и ссылки, в том числе 3 части блога, связанные с одним из двух последних ответов. – hatchet
Спасибо, что поделились этим. Это выглядит действительно полезно. На самом деле, я понимаю, как работают оба алгоритма, просто хочу знать, почему нам нужны два из них: – Kris
похоже на http://stackoverflow.com/questions/1657174/what- is-breadth-first-search-useful-for – hatchet