Алгоритм для нетерпеливых, который исследует мир слой за слоем. Почему очередь и терпение — ваше секретное оружие для поиска оптимального маршрута в лабиринте, графе друзей или на игровой карте. Мы с вами освоили инструменты для работы с линейными данными: сортировали их, искали в них, хранили для мгновенного доступа. Но мир редко бывает линейным. Чаще он похож на паутину связей. Как найти минимальное количество пересадок в метро? Как определить, через сколько рукопожатий вы знакомы с президентом? Как понять, какой ход в игре приведёт к победе за наименьшее число шагов? Все эти вопросы объединяет одно: они о поиске кратчайшего пути в структуре, которая называется граф. Сегодня мы познакомимся с алгоритмом, который решает эту задачу с элегантной простотой и железной логикой. Его имя — поиск в ширину (BFS, Breadth-First Search). Он не ходит наугад и не углубляется в одну тропинку, надеясь на удачу. Он методичен и справедлив: сначала исследует всех «ближайших соседей», потом соседей этих
Публикация доступна с подпиской
Базовый