1. Теория. BFS

«Простейшие методы часто оказываются самыми глубокими: исследуя мир концентрическими кругами, мы находим кратчайший путь прежде, чем успеем заблудиться в лабиринте».
— Эдсгер Вибе Дейкстра

Поиск в ширину (Breadth-First Search, BFS) — фундаментальный алгоритм теории графов, исследующий вершины по принципу концентрических волн. Если поиск в глубину (DFS) устремляется вглубь по первой попавшейся ветке до самого тупика, то BFS методично проверяет всех непосредственных соседей стартовой точки (шаг 1), затем соседей соседей (шаг 2) и так далее.

В архитектуре высоконагруженных бэкенд-систем BFS — это не просто инструмент обхода лабиринтов на алгоритмических секциях. На принципах BFS построены:

• Сетевая маршрутизация (OSPF, Dijkstra): поиск кратчайших сетевых путей с минимальным числом транзитных узлов (хопов).
• Service Discovery & Load Balancing: распространение gossip-протоколов (HashiCorp Memberlist / Consul) и поиск ближайших реплик в топологии ЦОД.
• Распределенные социальные графы: поиск графа связей через $K$ рукопожатий (LinkedIn, Facebook).
• Сборка мусора в рантаймах (Tracing GC): волновой обход живых объектов в алгоритмах трёхцветной маркировки (Tri-color marking), где плотная очередь гарантирует отличную пространственную локальность кэша процессора.

1. Анатомия алгоритма: FIFO-очередь и маркировка фронта

Классический алгоритм BFS опирается на строгий инвариант: вершины извлекаются в порядке неубывания их расстояния от начальной вершины. Для этого используется очередь первого входа — первого выхода (FIFO).

  Волна 0 (Старт)          Волна 1 (Шаг 1)            Волна 2 (Шаг 2)
      [ S ]       ───►      [ A ]   [ B ]     ───►     [ C ] [ D ] [ E ]
   дистанция: 0              дистанция: 1                дистанция: 2

Канонический волновой инвариант BFS

1. В момент, когда обрабатывается вершина на расстоянии $d$, в очереди могут находиться только вершины на расстоянии $d$ и $d + 1$.
2. В невзвешенном графе (где вес каждого ребра равен $1$) первый момент достижения целевой вершины $T$ гарантирует нахождение кратчайшего пути.

2. Визуализация волнового фронта BFS

flowchart TD
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error   fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef accent  fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc

    subgraph Level0["Уровень 0 (Старт)"]
        S["S (Старт)"]:::entry
    end

    subgraph Level1["Уровень 1 (Волна 1)"]
        A["Узел A"]:::process
        B["Узел B"]:::process
    end

    subgraph Level2["Уровень 2 (Волна 2)"]
        C["Узел C"]:::accent
        D["Узел D"]:::accent
        E["Узел E (Цель)"]:::success
    end

    S --> A
    S --> B
    A --> C
    A --> D
    B --> D
    B --> E
  

3. Mechanical Sympathy в Go: Ловушка queue = queue[1:]

При реализации очереди в Go разработчики нередко совершают грубейшую ошибку, наивно отрезая первый элемент слайса:

// АНТИПАТТЕРН: Скрытая утечка памяти и деградация GC!
queue := []*Node{root}

for len(queue) > 0 {
    curr := queue[0]
    queue = queue[1:] // ОПАСНО!
    // ...
}

Как реализовать очередь в Go эффективно: три подхода

1. Сдвиг индекса головы (head pointer):
   Самый простой и быстрый способ для алгоритмических задач. Срез растёт через append, а чтение идёт по индексу head. При исчерпании очереди базовый массив можно переиспользовать через queue = queue[:0].
2. Зануление пройденных указателей:
   Если в очереди лежат указатели (*Node), перед сдвигом head ячейку обнуляют: queue[head] = nil, чтобы GC мог забрать пройденный узел.
3. Кольцевой буфер (Ring Buffer):
   Производственный стандарт для бесконечных очередей фиксированной емкости, исключающий любые аллокации в цикле.

package main

// Queue представляет zero-alloc очередь на базе среза с занулением ссылок.
type Queue[T any] struct {
    data []T
    head int
}

func NewQueue[T any](initialCap int) *Queue[T] {
    return &Queue[T]{
        data: make([]T, 0, initialCap),
    }
}

func (q *Queue[T]) Push(val T) {
    q.data = append(q.data, val)
}

func (q *Queue[T]) Pop() T {
    val := q.data[q.head]
    var zero T
    q.data[q.head] = zero // Зануляем ячейку для помощи Garbage Collector
    q.head++

    // Если вся очередь вычитана, сбрасываем указатели в начало
    if q.head == len(q.data) {
        q.data = q.data[:0]
        q.head = 0
    }
    return val
}

func (q *Queue[T]) Len() int {
    return len(q.data) - q.head
}

func (q *Queue[T]) IsEmpty() bool {
    return q.head == len(q.data)
}

4. Почему непрерывный слайс превосходит container/list

В стандартной библиотеке Go есть пакет container/list, реализующий классический двусвязный список. Однако в высокопроизводительном коде его использовать категорически не рекомендуется:

Современный процессор за один такт загружает из оперативной памяти в кэш-линию L1 блок размером 64 байта (8 указателей или целых чисел). При чтении последовательного среза следующие 7 элементов уже находятся в L1d кэше с нулевой задержкой!

5. Сравнение фундаментальных характеристик: BFS vs DFS

flowchart LR
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error   fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef accent  fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc

    subgraph BFS["Поиск в ширину (BFS)"]
        direction TB
        B1["Структура данных: Очередь (FIFO)"]:::entry
        B2["Гарантирует кратчайший путь в 1-графах"]:::success
        B3["Память: O(W) — ширина графа"]:::warning
    end

    subgraph DFS["Поиск в глубину (DFS)"]
        direction TB
        D1["Структура данных: Стек (LIFO)"]:::accent
        D2["Не гарантирует кратчайший путь"]:::error
        D3["Память: O(H) — глубина/высота"]:::process
    end
  

6. Собеседование: ключевые вопросы и ловушки

Резюме

1. Инвариант BFS: Послойное волновое расширение фронта гарантирует поиск кратчайшего пути в невзвешенных графах за $O(V + E)$ времени.
2. Очередь в Go: Избегайте наивного queue[1:]. Используйте скользящий индекс head с занулением ссылок для бережного отношения к GC.
3. Память: Потребление памяти пропорционально ширине графа ($O(W)$). На полных бинарных деревьях на последнем уровне скапливается до $50\%$ всех узлов дерева.

В следующей статье мы подробно изучим ключевой паттерн решения задач на деревья — послойную обработку: 2. Обход по уровням.