Обычно, когда мне приходилось ходить по графику, я всегда использовал поиск по глубине из-за более низкой сложности пространства. Я, честно говоря, никогда не видел ситуации, требующей поиска по ширине, хотя мой опыт довольно ограничен.
Когда имеет смысл использовать поиск в ширину?
UPDATE. Я полагаю, что мой ответ здесь показывает ситуацию, когда я использовал BFS (потому что я думал, что это DFS). Мне все еще интересно узнать, почему это было полезно в этом случае.
Если вы хотите достичь node, пройдя как можно меньше ребер, т.е. когда вы хотите найти кратчайший путь в невзвешенном графике.
Кроме того, пространственная сложность первого поиска глубины может быть выше, чем ширина первого поиска по ширине, например, каждый node имеет только один дочерний элемент node, т.е. когда граф является глубоким, но не очень широким.
Если ваш поисковый домен бесконечен, поиск по глубине не гарантирует прекращения/поиска решения, даже если существует конечное решение.
Также вы можете видеть, что более сложные алгоритмы, такие как A *, являются специальным подтипом поиска по ширине и ширине.
В общем случае bfs является оптимальным и полным (с конечным коэффициентом ветвления), а dfs не является.
Может использоваться для решения проблемы поиска с минимальным количеством шагов. Вначале углубление может привести (если не ограничиться) к бесконечной глубине.
Пример: поиск ближайшего node к корню, который удовлетворяет условию.
Никто еще не упомянул ключевой фактор в случаях, когда поиск по ширине полезен: посещение node в одном случае может исключить необходимость посещения node каким-либо другим способом. В некоторых случаях каждый будет выполнять одну и ту же работу независимо от порядка, в котором посещаются узлы, но в BFS будет выполняться гораздо меньше ожидающих действий, чем DFS. В других случаях посещение узлов в одной последовательности может потребовать больше работы, чем другие; В качестве примера приведены различные алгоритмы кратчайшего пути. Если посещение node требует посещения его соседей, если известно, что node недоступен по пути, короче текущего, узлы посещения в порядке ширины обычно приводят к тому, что узлам назначается самый короткий путь - или что-то рядом с ним - при первом посещении. Напротив, поиск по глубине приведет к тому, что многие узлы будут посещаться по очень длинным путям в первый раз, затем по несколько более коротким путям, затем немного более коротким путям и т.д., Требующим поистине чудовищного общего объема работы.
Кстати, одна приятная графическая иллюстрация разницы между алгоритмами глубины и первой ширины - это заливка области, где белый node заполнен потоком, рисуя его черным и заливая наводнения его соседями. Если попытаться заполнить квадратную область NxN, начиная с кукурузы, операция с глубиной заполнит квадрат в спиральной или зигзагообразной последовательности, а операции NxN-1 останутся в стеке. Сначала заполнение шириной будет "выливаться" из начальной точки и будет работать не более O (N), независимо от формы, которую нужно заполнить. BTW, заполнение залива в IBM BASICA работало именно так (я не уверен в QBASIC).
Одним из примеров является перемещение файловой системы (с ограниченной рекурсивной глубиной).
В соответствии с wikipedia, это также полезно для определенных алгоритмов графа (бипартитность, связанные компоненты).
Когда имеет смысл использовать поиск в ширину?
Например, когда вам нужно найти кратчайший путь в графе - DFS просто не может этого сделать. Есть и другие приложения, но, в общем, DFS и BFS - это тот же алгоритм, который работает с разными структурами данных (BFS использует очередь, а DFS работает со стеком).
Когда вам нужно получить кратчайший путь к вершине из графика без веса края.
В глубине первого поиска вы можете найти "локальные" решения - поистине найти глобальное решение, необходимое для прохождения всего графика (или использования эвристики).
BFS иногда очень полезен. Предположим, у вас есть дерево, которое представляет, пусть говорят WBS. Вы можете представить своему пользователю только 1 уровень.
Алгоритм поиска по ширине лучше всего подходит как можно ближе к исходной точке. Некоторые из ситуаций, о которых я могу думать, следующие: