«Обход в ширину» или «Поиск в ширину» (Breadth first traversal or Breadth first Search) - это рекурсивный алгоритм поиска всех вершин графа или древовидной структуры данных. Для простоты предполагается, что все вершины достижимы из начальной вершины. BFS использует для обхода структуру данных: очередь (queue) Стандартная реализация ВFS помещает каждую вершину графа в одну из двух категорий: Цель алгоритма - пометить каждую вершину, как посещенную, избегая циклов. Алгоритм работает следующим образом: Давайте посмотрим, как алгоритм «поиска в ширину» работает на примере...

Базовая задача без подводных камней на один из основных алгоритмов теории графов - поиск в ширину. Читаем условие: Поиск в ширину (волновой алгоритм, BFS) - один из способов обхода графа. Применяется для определения всех вершин, доступных из стартовой (например для нахождения компонент связности), и расстояния до них в невзвешенных графах. Часто алгоритм называют волновым, потому что схема его работы похожа на расширение кругов на воде: В алгоритмической реализации нет необходимости явно выделять...