Обход графа: BFS или DFS, код на Python и задача Number of Islands

Короткий ответ. Обход графа это способ побывать в каждой вершине, до которой можно дойти. BFS идёт по слоям через очередь и находит кратчайший путь в рёбрах. DFS идёт вглубь через стек или рекурсию. Он находит компоненты, циклы и порядок. Оба стоят O(V + E). Ниже таблица выбора, код на Python для списка смежности и сетки, задача Number of Islands.

Что такое обход графа?

Граф это вершины и рёбра. Обход стартует из одной вершины и посещает все достижимые. Каждую вершину посещает один раз, для этого нужен набор visited.

Разница между BFS и DFS в порядке. BFS сначала все соседи, потом соседи соседей. DFS сначала один сосед до упора, потом возврат.

Граф может быть задан списком смежности, матрицей или сеткой клеток. Код обхода одинаковый, меняется только способ получить соседей.

Как выбрать между BFS и DFS?

Признак	BFS	DFS
Структура	Очередь	Стек или рекурсия
Кратчайший путь без весов	Да	Нет
Компоненты, острова	Да	Да, короче в коде
Поиск цикла, топологический порядок	Неудобно	Да
Память	Ширина слоя	Глубина пути
Риск	Большая очередь на широком графе	Переполнение стека на глубоком

Правило простое. Слово «кратчайший» или «минимальное число шагов», берите BFS. Всё остальное, берите DFS.

По каким словам в задаче узнать обход графа?

• «Число островов», «компоненты связности», «заливка области».
• «Минимальное число шагов до выхода», «кратчайший путь в лабиринте».
• «Можно ли дойти из A в B», «есть ли путь».
• «Клетки, соседние по четырём сторонам».

Сетка это тоже граф. Клетка это вершина, четыре соседа это рёбра. Многие задачи на матрицы на самом деле про обход графа.

Как это выглядит на примере?

Граф: A связана с B и C. B и C связаны с D. Старт A.

BFS: очередь [A]. Снимаем A, кладём B и C. Снимаем B, кладём D. Снимаем C, D уже видели. Снимаем D. Порядок A, B, C, D, расстояния 0, 1, 1, 2.

DFS: идём A, потом B, потом D. Из D соседей нет, возврат. Из B больше нет, возврат в A. Идём в C, D уже видели. Порядок A, B, D, C.

Как написать обход графа на Python?

from collections import deque

def bfs(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        v = queue.popleft()
        for u in graph[v]:
            if u not in dist:
                dist[u] = dist[v] + 1
                queue.append(u)
    return dist

def dfs(graph, start, visited=None):
    visited = visited if visited is not None else set()
    visited.add(start)
    for u in graph[start]:
        if u not in visited:
            dfs(graph, u, visited)
    return visited

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = set()

    def sink(r, c):
        stack = [(r, c)]
        while stack:
            r, c = stack.pop()
            for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
                if 0 <= nr < rows and 0 <= nc < cols \
                        and grid[nr][nc] == "1" and (nr, nc) not in seen:
                    seen.add((nr, nc))
                    stack.append((nr, nc))

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in seen:
                seen.add((r, c))
                sink(r, c)
                count += 1
    return count

В num_islands DFS написан через явный стек. На сетке 1000 на 1000 рекурсия упрётся в лимит глубины Python.

Как решить Number of Islands?

Сетка из нулей и единиц. Остров это группа единиц, соседних по сторонам. Нужно число островов.

Идём по всем клеткам. Нашли непосещённую единицу, значит новый остров. Запускаем обход из неё и помечаем все клетки острова. Считаем запуски.

Каждая клетка посещается один раз. Время O(rows · cols).

Как BFS находит кратчайший путь?

Очередь обрабатывает вершины по возрастанию расстояния. Все вершины на расстоянии 1, потом все на расстоянии 2. Первое попадание в вершину и есть кратчайший путь.

Это работает только без весов. С весами нужен алгоритм Дейкстры.

Как решить задачу про кратчайший путь в лабиринте?

Сетка с проходами и стенами, старт и выход. Нужно минимальное число шагов. Это BFS от старта. Каждая клетка получает расстояние при первом попадании в очередь. Дошли до выхода, вернули его расстояние. Очередь пуста, а выхода нет, значит пути нет.

На каких ошибках ломается обход графа?

• Помечают вершину посещённой при снятии из очереди, а не при добавлении. Одна вершина попадает в очередь много раз.
• Используют list.pop(0) вместо deque. Каждое снятие стоит O(n).
• Рекурсивный DFS на глубоком графе. Лимит Python около тысячи вызовов.
• Забывают проверить границы сетки до чтения клетки.

Как объяснить обход графа на собеседовании?

Назовите, чем задан граф и что считать соседом. Скажите, BFS или DFS, и почему. Назовите O(V + E). Объясните: каждая вершина и каждое ребро смотрятся один раз.

Для сетки сразу скажите про явный стек или очередь. Это показывает, что вы думали о размере входа.

Отработать узнавание приёма можно на странице обход графа BFS / DFS. Соседний приём разобран на странице компоненты связности.

Вопросы и ответы

Как восстановить сам путь после BFS?

Храните словарь parent. При добавлении вершины в очередь записывайте, откуда пришли. От цели идите по parent назад до старта.

Что такое многоисточниковый BFS?

В очередь кладут сразу несколько стартовых вершин с расстоянием 0. Так решают «расстояние до ближайшего нуля» за один проход.

Как найти цикл через DFS?

Держите три цвета: белый не был, серый в работе, чёрный закончен. Ребро в серую вершину и есть цикл. В неориентированном графе достаточно проверять, что сосед не родитель.

Где обход графа встречается в реальных системах?

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

Когда обход графа не подходит?

Когда у рёбер есть веса и нужен кратчайший путь. Тогда Дейкстра. И когда граф меняется между запросами, тогда система непересекающихся множеств.