Каковы преимущества BFS над DFS для нахождения кратчайшего пути? [dубликат]
Теперь std::experimental::erase_if доступен в заголовке <experimental/map>.
См. http://en.cppreference.com/w/cpp/experimental/map/erase_if
5 ответов
BFS будет использовать больше памяти в зависимости от фактора ветвления ... однако BFS - это полный алгоритм ... что означает, что если вы используете его для поиска чего-то на самой низкой глубине, BFS даст вам оптимальное решение. Сложность BFS - это O (b ^ d) ... коэффициент ветвления, поднятый на глубину (может быть МНОГО памяти).
DFS, с другой стороны, гораздо лучше о пространстве, однако он может найти субоптимальное решение. Если вы просто ищете путь от одной вершины к другой, вы можете найти субоптимальное решение (и остановиться там), прежде чем найти самый короткий путь. Сложность DFS-пространства - O (| V |) ... что означает, что наибольшая возможная память может быть самым длинным путем.
Они имеют одинаковую сложность времени. [ ! d6]
С точки зрения реализации, BFS обычно реализуется с Queue , тогда как DFS использует стек Stack .
-
1какова временная сложность? – Jony 13 April 2010 в 01:26
-
2Сложность времени для обоих: O (b ^ d) ... что означает, что она основана на коэффициенте ветвления и исследуемой глубине. BFS и DFS имеют одинаковый худший случай ... поиск по всему дереву. – Polaris878 13 April 2010 в 06:16
-
3В книге (введение в алгоритмы) говорится, что временная сложность BFS равна O (V + E), но DFS - θ (V + E). Почему это? – Rocky 4 August 2012 в 00:41
-
4Re O vs Theta: Это тоже должно быть Theta для BFS (что не делает утверждение противоречивым), потому что каждый узел изначально окрашен в белый цвет, и мы должны относиться к краям Theta (E). Сложность рекомбинации: как DFS, так и BFS выполняются в линейном пространстве, но DFS часто не попадает в худший случай. Если это так, набор посещенных узлов (цвета в Cormen) опущен и могут использоваться алгоритмы, такие как IDDFS, которые не нуждаются в линейном пространстве (или, по крайней мере, могут адаптивно адаптироваться). – Sebastian Graf 3 August 2015 в 16:43
-
5Ответ неправильный в использовании памяти. Оба могут потреблять худшую память O (V). Хуже того, для BFS есть один родитель с n дочерним, в худшем случае для DFS - цепочка из n узлов с одним дочерним элементом на родителя. Поэтому, в зависимости от топологии графа, BFS или DFS имеют равные шансы на выигрыш. – ShitalShah 17 September 2015 в 07:11
BFS очень хорош для кратчайших путей, а DFS - нет.
-
1Пожалуйста, добавьте более подробную информацию к вашему ответу. – Tom Aranda 28 October 2017 в 17:04
Вначале ширина сначала ищет родных братьев. Сначала глубина сначала сначала ищет детей. Поэтому, я думаю, это будет зависеть от того, какой поиск вы хотите делать. поиск типов отношений по полям, вероятно, будет использоваться для bfs, где иерархические (деревья, папки, ранги и т. д.) будут более подходящими как dfs.
Оба обхода графика обещают одно: полный обход графа, посещение каждой вершины на графике. Если у вас нет ограничений памяти, DFS - хороший выбор, так как BFS занимает много места. Таким образом, выбор между этими двумя зависит от вашего требования.
Хотите найти (сильно /) связанные компоненты графика? или решить лабиринт или судоку? Используйте DFS. Если вы внимательно присмотритесь, предварительный заказ, пост-порядок и порядок ввода - все варианты DFS. Итак, да, это интересные приложения.
BFS, если вы хотите проверить, является ли граф двудольным, найдите кратчайший путь между двумя узлами или приложениями, требующими таких задач.
В bfs очередь используется, тогда как в стеке dfs используется для хранения вершин в соответствии с обходом графика. 2- в процессе bfs выполняется уровень до уровня (в соответствии с направленным или неориентированным графиком), тогда как в dfs процесс выполняется до глубины (процесс первого посещения корневого узла, а другой - далеко, а затем применяется обратное отслеживание от последнего узла до корневой узел).