Поиск в ширину (BFS)
Обходим граф волной: сначала всех соседей, потом соседей соседей — слой за слоем.
1function bfs(graph: Map<string, string[]>, start: string): string[] {2 const queue: string[] = [start]3 const visited = new Set([start])4 const order: string[] = []5 6 while (queue.length > 0) {7 const node = queue.shift() as string8 order.push(node)9 10 for (const next of graph.get(node) ?? []) {11 if (!visited.has(next)) {12 visited.add(next)13 queue.push(next)14 }15 }16 }17 18 return order19}Проблема
Найти кратчайший путь (по числу рёбер) от одной вершины графа до всех остальных. Или просто обойти все достижимые вершины, не заблудившись и не зациклившись.
Что вы видите
Граф — карта станций. Очередь внизу — «волна»: кто ждёт обработки. Текущий узел обрабатывается, его непосещённые соседи встают в хвост очереди. Уровни волны = расстояние от старта.
Как это работает
BFS кладёт стартовую вершину в очередь и повторяет: взять из головы очереди, обработать, всех непосещённых соседей добавить в хвост. Очередь (FIFO) — ключ: она гарантирует, что сначала обрабатываются более близкие вершины, поэтому первый раз дойдя до вершины, мы пришли кратчайшим путём.
Пошаговый разбор
- 01
Старт
Стартовая вершина — в очередь, помечена посещённой.
- 02
Извлечение
Берём вершину из головы очереди — это текущая.
- 03
Соседи
Каждого непосещённого соседа помечаем и ставим в хвост.
- 04
Волна
Вершины обрабатываются в порядке неубывания расстояния от старта.
- 05
Финал
Очередь пуста — все достижимые вершины обойдены.
Complexity и ограничения
Работает на ориентированных и неориентированных графах. Память O(V) — очередь и метки.
Edge cases
- Изолированные вершины
Остаются непосещёнными: BFS обходит только компоненту связности старта.
- Циклы
Метки посещённости защищают от повторов и бесконечного цикла.
- Весь граф — линия
Очередь никогда не длиннее одного-двух элементов.
Где встречается в реальности
Навигатор
Кратчайший путь по числу перекрёстков: BFS от точки А до точки Б.
Социальные графы
«Ты знаком с N через 3 рукопожатия» — BFS фиксированной глубины.
Индексация сайтов
Краулер обходит веб слоями от стартовых URL.
Связанные алгоритмы
«Как навигатор находит кратчайший путь, ни разу не «угадывая»?»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.