Представление графа

Прежде чем обходить граф, его надо где-то хранить. Два главных способа и их компромиссы.

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

Зачем это нужно

Графы — самая частая тема олимпиад после ДП. Карта городов с дорогами, друзья в соцсети, зависимости между задачами, переходы между состояниями игры — всё это графы. Но прежде чем запускать BFS или Дейкстру, граф нужно представить в памяти, и от выбора представления зависит и скорость, и память. Неправильный выбор (например, матрица смежности при большом числе вершин) сразу даёт MLE. Поэтому начинаем с фундамента — как хранить граф.

Базовая терминология

• Вершины (vertices) — объекты (города, люди), обычно нумеруются 0..n−1.
• Рёбра (edges) — связи между вершинами. Бывают неориентированные (дорога в обе стороны) и ориентированные (одностороннее движение).
• Вес — у ребра может быть число (длина дороги, стоимость).
• Степень вершины — число инцидентных ей рёбер.

Способ 1. Список смежности

Для каждой вершины храним список её соседей. Это самое частое представление: оно компактно (память O(n + m), где m — число рёбер) и удобно для обходов, ведь соседей вершины можно перебрать напрямую.

n = 5
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]

g = [[] for _ in range(n)]        # список соседей для каждой вершины
for u, v in edges:
    g[u].append(v)
    g[v].append(u)                # неориентированный: добавляем в обе стороны

for u in range(n):
    print(u, "->", g[u])

Ключевой момент — для неориентированного графа каждое ребро добавляем дважды: и v в список u, и u в список v. Для ориентированного — только одно направление. Перебор соседей вершины u — это просто for v in g[u].

Вывод:

0 -> [1, 2]
1 -> [0, 3]
2 -> [0, 3]
3 -> [1, 2, 4]
4 -> [3]

Способ 2. Матрица смежности

Двумерная таблица n×n, где adj[u][v] = 1, если есть ребро (или вес ребра). Проверка «есть ли ребро между u и v?» — мгновенная O(1). Но память — O(n^2), что при n = 10^5 недопустимо. Поэтому матрица годится только для малых графов (примерно n ≤ 1000–2000) или плотных графов.

n = 5
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]

adj = [[0] * n for _ in range(n)]
for u, v in edges:
    adj[u][v] = 1
    adj[v][u] = 1

print("Есть ребро 0-2?", adj[0][2] == 1)
print("Есть ребро 1-2?", adj[1][2] == 1)
for row in adj:
    print(row)

Матрица удобна, когда часто спрашивают «связаны ли две конкретные вершины» или когда граф плотный (рёбер близко к n^2). В алгоритме Флойда-Уоршелла, например, матрица — естественное представление.

Вывод:

Есть ребро 0-2? True
Есть ребро 1-2? False
[0, 1, 1, 0, 0]
[1, 0, 0, 1, 0]
[1, 0, 0, 1, 0]
[0, 1, 1, 0, 1]
[0, 0, 0, 1, 0]

Граф с весами

Если у рёбер есть веса, в списке смежности храним пары (сосед, вес). Это представление понадобится для Дейкстры и MST.

n = 4
weighted_edges = [(0, 1, 5), (0, 2, 3), (1, 3, 2), (2, 3, 7)]
g = [[] for _ in range(n)]
for u, v, w in weighted_edges:
    g[u].append((v, w))
    g[v].append((u, w))
for u in range(n):
    print(u, "->", g[u])

Вывод:

0 -> [(1, 5), (2, 3)]
1 -> [(0, 5), (3, 2)]
2 -> [(0, 3), (3, 7)]
3 -> [(1, 2), (2, 7)]

Когда что выбирать

Правило по умолчанию: используй список смежности. Он подходит к подавляющему большинству задач и не упрётся в память. Матрицу бери осознанно — для малых плотных графов или алгоритмов, которым она нужна (Флойд).

Подводные камни

• Неориентированное ребро — два добавления. Самая частая ошибка: забыть g[v].append(u), и половина рёбер «исчезает».
• Кратные рёбра и петли. Уточняй в условии, бывают ли несколько рёбер между парой вершин или ребро из вершины в себя.
• Нумерация с 1. Многие задачи нумеруют вершины с 1; либо заводи массив на n+1, либо вычитай единицу при чтении.

Итог

• Граф — вершины и рёбра; рёбра бывают ориентированные/неориентированные, с весами или без.
• Список смежности — память O(n+m), удобен для обходов; представление по умолчанию.
• Матрица смежности — O(1) проверка ребра, но O(n^2) памяти; только для малых/плотных графов.
• Неориентированное ребро добавляй в оба списка; следи за нумерацией вершин.