Обход графа 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;
}

function bfsDistances(adj: Record<string, string[]>, source: string): Record<string, number> {
    const dist: Record<string, number> = { [source]: 0 };
    const queue: string[] = [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;
}

from collections import deque

def bfs_distances(adj, source):
    dist = {source: 0}
    queue = deque([source])
    while queue:
        node = queue.popleft()
        for nxt in adj.get(node, []):
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist

function bfsDistances(array $adj, $source): array {
    $dist = [$source => 0];
    $queue = [$source];
    while ($queue) {
        $node = array_shift($queue);
        foreach ($adj[$node] ?? [] as $next) {
            if (!isset($dist[$next])) {
                $dist[$next] = $dist[$node] + 1;
                $queue[] = $next;
            }
        }
    }
    return $dist;
}

    public static Map<String, Integer> bfsDistances(Map<String, List<String>> adj, String source) {
        Map<String, Integer> dist = new HashMap<>();
        dist.put(source, 0);
        Queue<String> queue = new ArrayDeque<>();
        queue.add(source);
        while (!queue.isEmpty()) {
            String node = queue.poll();
            for (String next : adj.getOrDefault(node, List.of())) {
                if (!dist.containsKey(next)) {
                    dist.put(next, dist.get(node) + 1);
                    queue.add(next);
                }
            }
        }
        return dist;
    }

    public static Dictionary<string, int> BfsDistances(Dictionary<string, List<string>> adj, string source) {
        var dist = new Dictionary<string, int> { [source] = 0 };
        var queue = new Queue<string>();
        queue.Enqueue(source);
        while (queue.Count > 0) {
            string node = queue.Dequeue();
            if (!adj.TryGetValue(node, out var neighbours)) continue;
            foreach (string next in neighbours) {
                if (!dist.ContainsKey(next)) {
                    dist[next] = dist[node] + 1;
                    queue.Enqueue(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: когда применять?

Паттерн «Обход графа BFS / DFS» нужен, когда в условии есть слова «кратчайший путь в невзвешенном графе», «минимальное число шагов/рёбер между узлами» или «достижим ли узел Y из узла X». Решение на нём обычно укладывается в O(V+E).

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «Обход графа BFS / DFS» чаще всего путают с этими паттернами: Обход дерева, Алгоритм Дейкстры, Компоненты связности и Бэктрекинг.

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

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

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

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

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

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

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

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

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

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

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

Паттерн «Обход графа BFS / DFS» решает такие задачи с собеседований: Число островов, Гниющие апельсины, Лестница слов, Клонирование графа, Кратчайший путь в двоичной матрице, Расписание курсов и Сток воды в два океана.

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

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

У паттерна «Обход графа BFS / DFS» целевая сложность O(V+E).

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