Структура данных графиков: DFS по сравнению с BFS?
если дали проблема графика, как мы знаем, должны ли мы использовать алгоритм DFS или bfs??? или когда делают мы используем алгоритм DFS или bfs алгоритм. Каковы различия и преимущества одного по другому?
2 ответа
BFS будет использовать больше памяти в зависимости от фактора ветвления ... однако BFS - это полный алгоритм ... это означает, что если вы используете его для поиска чего-либо на минимально возможной глубине, BFS предоставит вам оптимальную решение.
Сложность пространства BFS составляет O (b ^ d) ... коэффициент ветвления, увеличенный до глубины (может быть ОЧЕНЬ много памяти).
DFS, с другой стороны, гораздо лучше использует пространство, однако может найти неоптимальное решение. Это означает, что если вы просто ищете путь от одной вершины к другой, вы можете найти неоптимальное решение (и остановиться на нем) до того, как найдете реальный кратчайший путь. Сложность пространства DFS составляет O (| V |) ... это означает, что наибольший объем памяти, который он может занять, - это самый длинный путь.
У них одинаковая временная сложность.
С точки зрения реализации, BFS обычно реализуется с помощью Queue , тогда как DFS использует стек .
При поиске по ширине сначала ищутся братья и сестры. При поиске по глубине сначала ищутся дети. Так что, я думаю, это зависит от того, какой тип поиска вы хотите выполнить. Поиск отношений по полям, вероятно, подходит для bfs, а иерархический поиск (деревья, папки, ранги и т.д.) больше подходит для dfs.