Описание тега breadth-first-search
В теории графов поиск в ширину (BFS) - это алгоритм поиска графа, который начинается с корневого узла и исследует все соседние узлы. Затем для каждого из этих ближайших узлов он исследует их неисследованные соседние узлы и так далее, пока не найдет цель.
BFS - это неинформированный метод поиска, который направлен на расширение и исследование всех узлов графа или комбинации последовательностей путем систематического поиска по каждому решению. Другими словами, он тщательно просматривает весь граф или последовательность, не учитывая цель, пока не найдет ее. Он не использует эвристический алгоритм.
Алгоритм
С точки зрения алгоритма все дочерние узлы, полученные в результате расширения узла, добавляются в очередь FIFO (т. Е. "Первым пришел - первым вышел"). В типичных реализациях узлы, которые еще не были проверены на предмет своих соседей, помещаются в некоторый контейнер (например, очередь или связанный список), называемый открытыми, а затем после проверки помещаются в закрытый контейнер.
- Поставить корневой узел в очередь
- Удалите узел из очереди и изучите его
- Если искомый элемент найден в этом узле, прекратите поиск и верните результат.
- В противном случае поставьте в очередь всех наследников (прямые дочерние узлы), которые еще не были обнаружены.
- Если очередь пуста, значит, все узлы на графе проверены - прекратите поиск и верните "не найден".
- Если очередь не пуста, повторите с шага 2.
Приложения
- Поиск всех узлов в одном связном компоненте
- Копирование коллекции, алгоритм Чейни
- Нахождение кратчайшего пути между двумя узлами u и v (длина пути измеряется количеством ребер)
- Проверка графа на двудольность
Источник