Графы: представление и обходы

Что такое граф

Граф — это точки и связи между ними. Точки называются вершинами, связи — рёбрами. Ты постоянно пользуешься графами:

• карта метро: станции — вершины, перегоны — рёбра;
• соцсеть: люди — вершины, дружба — ребро;
• зависимости пакетов: пакет A требует пакет B.

Рёбра бывают двух видов:

• Ненаправленные. Дружба взаимна: если Аня дружит с Борей, то и Боря дружит с Аней. Ребро A — B проходимо в обе стороны.
• Направленные. Подписка в соцсети односторонняя: ты подписан на блогера, а он на тебя нет. Ребро A → B ведёт только в одну сторону.

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

Как хранить граф

Обычно граф дают списком рёбер, например [[0,1],[0,2],[1,3]]. Из него строят одно из двух представлений.

Список смежности — для каждой вершины хранится список её соседей: graph[0] = [1, 2]. Матрица смежности — таблица n × n, где m[i][j] = 1, если есть ребро i → j.

	Список смежности	Матрица смежности
Память	O(V + E)	O(V²)
Есть ли ребро i–j?	O(deg)	O(1)
Перебрать соседей	O(deg)	O(V)
Когда брать	почти всегда	граф маленький и плотный

Здесь V — число вершин, E — число рёбер, deg — число соседей вершины. На собесе в 9 случаях из 10 нужен список смежности: defaultdict(list) в Python, List<List<Integer>> в Java. Если граф ненаправленный, ребро добавляй дважды: a → b и b → a.

Сетка — это тоже граф

Очень частый формат задач — двумерная сетка: лабиринт, карта островов, поле с апельсинами. Список смежности строить не нужно, граф там уже есть:

• вершина — клетка (r, c);
• рёбра ведут к соседям сверху, снизу, слева и справа: (r±1, c) и (r, c±1).

Соседей удобно перебирать через массив направлений dirs = [(1,0),(-1,0),(0,1),(0,-1)]. Каждого соседа проверяем на две вещи: не вышли ли за границы и можно ли туда ступать, то есть не стена ли это.

Обходы: DFS и BFS

Обойти граф значит посетить все вершины, достижимые из старта. Главное отличие от дерева в том, что в графе можно ходить по кругу: A → B → A → B… Поэтому нужно множество посещённых (visited). Вершину отмечаем, и больше в неё не заходим.

DFS (поиск в глубину) — как исследовать лабиринт, держась рукой за стену: идёшь вперёд, пока можешь, упёрся — вернулся на шаг назад. Реализуется рекурсией или стеком. Подходит, когда нужно просто «дойти до всех»: найти компоненты связности, посчитать острова, найти цикл.

BFS (поиск в ширину) — как круги на воде от брошенного камня. Сначала обходим всех соседей старта, потом их соседей, и так слой за слоем. Реализуется очередью.

Главная суперсила BFS

В невзвешенном графе BFS находит кратчайший путь. Вершины достаются из очереди строго по возрастанию расстояния: сначала все на расстоянии 1, потом все на расстоянии 2 и так далее. Поэтому когда BFS впервые дошёл до вершины, он дошёл до неё самым коротким путём. DFS такого не гарантирует: он может уйти далеко в обход.

	DFS	BFS
Структура	стек / рекурсия	очередь
Кратчайший путь	❌	✅ (если все рёбра одинаковые)
Код	короче	чуть длиннее

Если в задаче есть слова «минимальное число шагов», «кратчайший путь», «за сколько минут» — почти наверняка это BFS.

Шаблон: BFS по сетке

Шаблон считает расстояние от стартовой клетки до каждой достижимой клетки. Стены обозначены '#'. Массив dist здесь работает и как visited: значение -1 значит «ещё не были».

from collections import deque

def bfs_grid(grid, sr, sc):
    rows, cols = len(grid), len(grid[0])
    dist = [[-1] * cols for _ in range(rows)]  # -1 = не посещали
    dist[sr][sc] = 0
    q = deque([(sr, sc)])
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while q:
        r, c = q.popleft()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            # в границах, не стена, ещё не посещали
            if 0 <= nr < rows and 0 <= nc < cols \
                    and grid[nr][nc] != '#' and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1  # отмечаем сразу при добавлении
                q.append((nr, nc))
    return dist

Хочешь DFS? Замени очередь на стек, то есть бери элемент с конца, или напиши рекурсию с той же проверкой соседей. Отмечать посещённые нужно точно так же.

Сложность

• Граф: время O(V + E), потому что каждую вершину и каждое ребро смотрим по разу. Память O(V) уходит на visited и очередь.
• Сетка R × C: время и память O(R · C), ведь у каждой клетки не больше 4 соседей.

Как это звучит на собесе

«Представлю сетку как граф: клетки — вершины, соседи по четырём направлениям — рёбра. Нужен минимум шагов, а рёбра невзвешенные, значит BFS. Посещённые отмечаю при добавлении в очередь. Сложность — O(R·C) по времени и памяти».

Проговорить почему BFS, а не просто «сделаю BFS», — это то, за что дают плюсы.

Частые ошибки

• Нет visited — обход зацикливается или работает экспоненциально долго.
• Отмечать посещённой при извлечении, а не при добавлении. Тогда одна клетка попадает в очередь несколько раз. Отмечай сразу, как кладёшь в очередь.
• Перепутаны rows и cols в проверке границ. Особенно легко ошибиться, когда сетка не квадратная.
• В ненаправленном графе ребро добавлено только в одну сторону.
• Медленная очередь: list.pop(0) в Python и shift() в JS работают за O(n). Бери deque или указатель head.
• BFS для взвешенного графа. Если у рёбер разные веса, BFS не даёт кратчайший путь. Там нужен Дейкстра, до него дойдём позже.

Ты уже знаешь главное: граф — это вершины и рёбра, сетка — тоже граф, а обход — это «очередь или стек + visited». Дальше в практике этот шаблон будет почти в каждой задаче главы.