Поиск в ширину (BFS)

Исходный граф

Вершины A–H; неориентированные рёбра AB, AC, BD, BE, CE, CF, DG, EG и FG. У H нет рёбер. Изначально старт — A, цель — G.

Слои, а не геометрическое расстояние

BFS сначала обнаруживает старт с расстоянием 0, затем вершины в одном ребре от него, потом в двух и так далее. Расположение на рисунке условно: длина линии на экране не влияет на ответ. Граф остаётся неподвижным на протяжении всего воспроизведения.

В примере используется простой неориентированный граф без весов. Плеер полностью обходит компоненту, достижимую из старта, и только после этого восстанавливает путь до цели. При первом обнаружении цели поиск не останавливается. Остальные компоненты остаются необойдёнными.

Отмечаем вершину при добавлении в очередь

Берём вершину из начала очереди, рассматриваем соседей в заданном порядке и добавляем каждого ещё не обнаруженного соседа в конец. В этот же момент задаём расстояние и предка. Вершина может быть обнаружена, но ещё ждать обработки в очереди.

Каждая вершина попадает в очередь один раз. Поэтому цикл не приводит к бесконечному обходу, а два разных предка не добавляют одного соседа повторно. Расстояния вершин очереди не убывают. Текущая вершина уже извлечена из очереди; обработанная — та, у которой рассмотрены все соседи.

Цикл и вершина, которая уже в очереди

В основном примере соседи перебираются по алфавиту. После A очередь равна [B, C]. При обработке B добавляем D и E, получаем [C, D, E]. У C тоже есть сосед E, но он уже обнаружен: пропускаем и сохраняем предка B.

Полный порядок обработки: A, B, C, D, E, F, G. Расстояния: A — 0, B/C — 1, D/E/F — 2, G — 3. Изолированная H недостижима. Обход обнаруживает и обрабатывает 7 вершин, просматривает 18 записей соседей, максимум очереди — 3.

Счётчик просмотров учитывает записи списков смежности, включая пропуски. Неориентированное ребро рассматривается с двух концов: 9 рёбер достижимой компоненты дают 18 просмотров. Старт включён в число обнаруженных. Восстановление пути не меняет счётчики обхода.

Один кратчайший путь, но не обязательно единственный

Идём по предкам от G: G, D, B, A. Разворачиваем последовательность и получаем A → B → D → G длиной 3 ребра. У предка, выбранного при первом обнаружении, расстояние всегда на единицу меньше. Поэтому цепочка предков дойдёт до старта без цикла.

Через E или F тоже можно пройти за 3 ребра. Другой порядок соседей может изменить предка и выбранный путь, но не кратчайшее расстояние. Выберите целью H, чтобы увидеть отсутствие пути, или сам старт для пути длиной 0. В режиме «Без цели» плеер показывает только завершённый обход.

До окончания обхода прочерк означает, что вершина ещё не обнаружена. После него ∞ означает недостижимость из этого старта. Во время восстановления частичный путь показан от цели к старту, окончательный результат — от старта к цели.

Время, память и сохранённая история

При списках смежности верхняя граница времени — O(V + E). Инициализация расстояний и предков охватывает все вершины, сам обход рассматривает только достижимую компоненту. Очередь и данные вершин занимают O(V) дополнительной памяти, хранение графа — O(V + E). Восстановление одного пути требует O(V) времени и памяти результата.

У визуализации отдельная стоимость: до O(V + E) неизменяемых снимков с O(V) данными вершин в каждом, то есть O(V(V + E)) памяти истории плюс общий граф. Лимит сцены в восемь вершин нужен для читаемости, а не из-за ограничения BFS. В реализации используется индекс головы очереди вместо повторного сдвига массива через shift().

Реализация на JavaScript

Код принимает корректный простой неориентированный граф как Map от id вершины к упорядоченному массиву соседей, существующий старт и необязательную существующую цель. Полный обход и выбор предка совпадают с плеером. Исходные Map и массивы не меняются. Плеер дополнительно проверяет и копирует граф перед созданием снимков.

function breadthFirstSearch(adjacency, start, target = null) {
    // Map<vertexId, vertexId[]>; a valid undirected graph.
    const distance = new Map([...adjacency.keys()].map(id => [id, null]));
    const parent = new Map([...adjacency.keys()].map(id => [id, null]));
    const queue = [start];
    distance.set(start, 0);
    let edgeChecks = 0;
    let maxQueueSize = 1;

    for (let head = 0; head < queue.length; head++) {
        const vertex = queue[head];
        for (const neighbor of adjacency.get(vertex)) {
            edgeChecks++;
            if (distance.get(neighbor) !== null) continue;
            // Mark on enqueue, not when the vertex is removed.
            distance.set(neighbor, distance.get(vertex) + 1);
            parent.set(neighbor, vertex);
            queue.push(neighbor);
            maxQueueSize = Math.max(maxQueueSize, queue.length - head - 1);
        }
    }

    const path = [];
    if (target !== null && distance.get(target) !== null) {
        for (let vertex = target; vertex !== null; vertex = parent.get(vertex)) {
            path.push(vertex);
        }
        path.reverse();
    }
    return { distance, parent, path, order: queue, edgeChecks, maxQueueSize };
}

Где применим BFS

Кратчайший путь здесь — путь с минимальным числом рёбер. Если стоимость рёбер различается, обычный BFS не гарантирует минимальную суммарную стоимость. DFS идёт в глубину и полезен для других задач, но его первый путь в общем случае не кратчайший по числу рёбер.

Алгоритм и раскладки графов определены на сайте. AlgiViz 0.8.0 предоставляет оболочки шагов, временную шкалу и пользовательские объекты сцены. Граф, очередь и доступный текст описывают одно сохранённое состояние; перемотка не запускает обход заново.

Связанные материалы