12.2 Поиск в ширину (Breadth-First Search)¶

Поиск в ширину (BFS) — это алгоритм обхода графа, который посещает вершины в порядке увеличения расстояния от стартовой вершины. Это означает, что сначала рассматриваются все вершины на расстоянии 1, затем на расстоянии 2 и так далее.

Главная особенность BFS — он проходит граф по уровням.

Идея алгоритма¶

Алгоритм работает следующим образом:

1. Начинаем с некоторой стартовой вершины.
2. Сначала посещаем всех её соседей.
3. Затем — соседей соседей.
4. И так далее, пока не обработаем весь граф.

Другими словами, мы двигаемся «волнами» от начальной вершины.

Пример¶

Рассмотрим граф:

graph TD
    1 --> 2
    1 --> 4
    2 --> 3
    4 --> 5
    3 --> 6
    5 --> 6

Пусть стартовая вершина — 1.

Тогда порядок обхода будет таким:

• Уровень 0: 1
• Уровень 1: 2, 4
• Уровень 2: 3, 5
• Уровень 3: 6

Таким образом, BFS постепенно расширяет фронт поиска.

Расстояния¶

Одно из ключевых применений BFS — нахождение кратчайших расстояний в невзвешенном графе.

Для нашего примера:

BFS гарантирует, что найденные расстояния — минимальные.

Сложность¶

Время работы алгоритма:

где:

• (n) — число вершин
• (m) — число рёбер

Каждая вершина и каждое ребро обрабатываются не более одного раза.

Реализация¶

В отличие от DFS, BFS использует очередь.

Идея:

• кладём стартовую вершину в очередь
• извлекаем вершину
• добавляем в очередь её непосещённых соседей

Код (C++)¶

queue<int> q;
bool used[N];
int dist[N];

void bfs(int start) {
    used[start] = true;
    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int u : adj[v]) {
            if (used[u]) continue;

            used[u] = true;
            dist[u] = dist[v] + 1;
            q.push(u);
        }
    }
}

Как это работает¶

flowchart LR
    A[Стартовая вершина] --> B[Добавить в очередь]
    B --> C[Достать из очереди]
    C --> D[Обработать вершину]
    D --> E[Добавить соседей]
    E --> C

Где применяется BFS¶

Поиск в ширину используется в задачах:

• поиск кратчайшего пути в невзвешенном графе
• проверка связности графа
• поиск компонент связности
• проверка двудольности
• обход уровней (например, в деревьях)

Важное понимание¶

• BFS = поиск по слоям
• гарантирует кратчайший путь (если веса = 1)
• работает через очередь
• идеально подходит для задач «минимального количества шагов»

Итог¶

Поиск в ширину — один из самых важных алгоритмов в графах. Если в задаче нужно найти минимальное число шагов, почти всегда стоит начинать именно с BFS.