Алгоритмы

BFS: Поиск в ширину

Цели урока

Понять идею обхода «волнами»
Реализовать BFS с очередью
Найти кратчайший путь в невзвешенном графе
Знать типичные применения BFS

Предварительные знания

Очередь (Queue)
Представление графов

Как GPS находит путь с минимумом поворотов? Как найти всех друзей друзей в социальной сети? Как игровой AI находит путь к цели? Один алгоритм решает все эти задачи - BFS.

GPS-навигация в метро
«Люди, которых вы можете знать» в LinkedIn
Pathfinding в играх (для невзвешенных карт)
Web crawlers для поисковых систем

Цузе, Мур и Ли: BFS из задач трассировки

BFS изобретали несколько раз и независимо. Первым, около 1945 года, его описал Конрад Цузе в неопубликованной диссертации как алгоритм поиска компонент связности графа, но работа пролежала в столе десятилетиями. Канонический источник это статья Эдварда Ф. Мура The Shortest Path Through a Maze 1959 года, представленная на симпозиуме по теории переключательных схем в Гарварде. Мур решал конкретную инженерную задачу: найти кратчайший путь через лабиринт, и его волновой обход уровень за уровнем и есть BFS в чистом виде. Почти сразу, в 1961 году, Чин Ян Ли в Bell Labs применил ту же идею к трассировке проводников на печатных платах и в микросхемах, и алгоритм Ли до сих пор знают разработчики САПР. Любопытно, что BFS родился не из абстрактной теории графов, а из практических задач: маршрутизация в лабиринте и разводка проводов. Очередь FIFO, гарантия кратчайшего пути по числу рёбер и сложность O(V + E) были там с самого начала.

Идея: волны от источника

**Представьте камень, брошенный в воду.** Волны расходятся кругами: сначала ближайшие точки, потом дальние. BFS работает так же - сначала все соседи, потом соседи соседей.

**Ключевая структура - очередь (Queue).** FIFO гарантирует, что мы обработаем всех на расстоянии k до расстояния k+1.

**BFS = Queue, DFS = Stack (или рекурсия).** Запомните это навсегда.

Если BFS стартует из вершины A и находит B на итерации 3, что это значит?

Реализация BFS

**Важно:** добавляем в visited ПРИ ДОБАВЛЕНИИ в очередь, не при извлечении. Иначе вершина может попасть в очередь несколько раз.

Операция	Сложность	Почему
Время	O(V + E)	Каждая вершина и ребро - один раз
Память	O(V)	visited + queue максимум V вершин

**Используйте deque, не list!** `list.pop(0)` - это O(n), а `deque.popleft()` - O(1).

Почему visited.add() должен быть ДО queue.append(), а не после queue.popleft()?

Кратчайший путь (невзвешенный)

BFS автоматически находит **кратчайший путь по числу рёбер**. Нужно только запомнить, откуда мы пришли.

**Расстояния до всех вершин:**

**GPS-навигатор** для метро использует именно BFS - все станции равноценны, важно число пересадок.

BFS нашёл путь A→B→C→D. Может ли существовать более короткий путь A→D?

Применения BFS

**Классические задачи на BFS:**

**Социальные сети:** степени разделения (6 handshakes)
**Игры:** поиск пути для NPC, flood fill
**Web crawlers:** обход страниц по уровням
**Компиляторы:** garbage collection (mark phase)

Для какой задачи BFS НЕ подходит?