Обход графа BFS / DFS

Обход графа BFS / DFS: как это работает?

Положите стартовую вершину в контейнер и пометьте её. Контейнером служит очередь или стек.

Достаньте одну вершину. Посмотрите на всех её соседей.

Пропускайте уже помеченных соседей. Именно эта проверка не даёт обходу зациклиться.

Пометьте каждого нового соседа и положите в контейнер. Помечайте при вставке, а не при извлечении.

Очередь берёт самую старую вершину, поэтому обход растекается по уровням. Так до каждой вершины выходит минимум рёбер.

Стек берёт самую свежую, поэтому обход сначала уходит вглубь. Оба посещают каждую достижимую вершину один раз.

1. очередь = [1], помечены = {1}Рёбра это 1-2, 1-3 и 2-4. Старт помечается первым.
2. берём 1, очередь = [2, 3]Оба соседа новые. Они помечаются при вставке.
3. берём 2, очередь = [3, 4]Вершина 4 новая. Вершина 1 уже помечена и пропускается.
4. берём 3, очередь = [4]У вершины 3 непомеченных соседей нет.
5. берём 4, очередь = []Ничего не осталось. Четыре вершины, каждая посещена один раз.

function bfsDistances(adj, source) {
    const dist = { [source]: 0 };
    const queue = [source];
    while (queue.length) {
        const node = queue.shift();
        for (const next of adj[node] || []) {
            if (!(next in dist)) {
                dist[next] = dist[node] + 1;
                queue.push(next);
            }
        }
    }
    return dist;
}

Обход графа BFS / DFS: разбор примера

Через сколько минут сгниют все апельсины

В сетке лежат пустые клетки, свежие апельсины и гнилые. Каждую минуту гнилой заражает четырёх соседей.

Верните число минут до исчезновения свежих или минус один.

Все гнилые апельсины попадают в очередь ещё до начала обхода.

За минуту обрабатывается целый уровень очереди. Оставшийся свежий апельсин означает минус один.

function orangesRotting(grid) {
    const rows = grid.length;
    const cols = grid[0].length;
    let queue = [];
    let fresh = 0;

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === 2) queue.push([r, c]);
            if (grid[r][c] === 1) fresh++;
        }
    }

    const steps = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    let minutes = 0;

    while (queue.length && fresh > 0) {
        const next = [];

        // one whole level per minute
        for (const [r, c] of queue) {
            for (const [dr, dc] of steps) {
                const nr = r + dr;
                const nc = c + dc;
                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                if (grid[nr][nc] !== 1) continue;

                grid[nr][nc] = 2; // marked on entry, so it is queued once
                fresh--;
                next.push([nr, nc]);
            }
        }

        queue = next;
        minutes++;
    }

    return fresh === 0 ? minutes : -1;
}

Обход графа BFS / DFS: когда применять?

Эти формулировки в условии ведут сюда:

• •кратчайший путь в невзвешенном графе
• •минимальное число шагов/рёбер между узлами
• •достижим ли узел Y из узла X
• •исследовать кольцо за кольцом / слой за слоем
• •граф задан списком смежности, возможны циклы

Обход графа BFS / DFS: с чем путают?

• Обход дерева (Tree traversal): В дереве в узел нельзя попасть дважды, поэтому множество посещённых не нужно. В графе можно, поэтому нужно всегда.
• Алгоритм Дейкстры (Dijkstra's algorithm): Веса на рёбрах ломают порядок по уровням. Тогда очередь заменяется кучей.
• Компоненты связности (Connected components): Та страница считает группы в графе. Здесь описан сам обход, из которого счёт и складывается.
• Бэктрекинг (Backtracking): Бэктрекинг откатывает состояние на выходе. Обход помечает узел и никогда не снимает пометку.

Обход графа BFS / DFS: частые ошибки

• Помечают при извлечении, а не при вставке

  Тогда одна вершина попадает в очередь много раз. Помечайте её в момент вставки.

• Берут стек, когда ответ это расстояние

  Обход в глубину может дойти до вершины окольным путём. Минимум рёбер даёт только очередь.

• Вызывают shift на длинной очереди

  В JavaScript shift на массиве стоит O(n). Используйте индекс чтения или список уровня.

• Забывают, что граф бывает несвязным

  Один обход достаёт только одну компоненту. Пройдите по всем ещё не посещённым вершинам.

Обход графа BFS / DFS: задачи с собеседований

• Число островов: По одному обходу на каждую непосещённую клетку суши.
• Гниющие апельсины: Все гнилые клетки стартуют в очереди вместе.
• Лестница слов: Слова это вершины, а замены одной буквы это рёбра.
• Клонирование графа: Словарь посещённых хранит ещё и созданные копии.
• Кратчайший путь в двоичной матрице: Восемь направлений, одна очередь, счёт по уровням.
• Расписание курсов: Поиск цикла в ориентированном графе.
• Сток воды в два океана: Два обхода, оба стартуют от краёв.

Обход графа BFS / DFS: сложность по времени и памяти

O(V+E)

V вершин и E рёбер дают O(V + E). Память O(V) на множество посещённых и на фронт.