Графы: определения и хранение

Граф — это множество вершин и множество рёбер между ними. Проще всего думать о нём как о карте: вершины — города, рёбра — дороги.

Обозначения стандартные: $n$ — число вершин, $m$ — число рёбер. Почти все оценки в теме записываются через них.

Термины

Ориентированное ребро проходится в одну сторону, неориентированное — в обе. Дорога с односторонним движением против обычной.

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

Степень вершины $\deg(v)$ — количество её соседей. Сумма степеней всех вершин равна $2m$: каждое ребро считается дважды.

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

Компонента связности — максимальный по включению связный кусок.

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

Полный граф — граф, где есть все возможные рёбра. Их $\frac{n(n-1)}{2}$ — это и есть максимум для графа без петель и кратных рёбер.

Матрица смежности

vector<vector<char>> g(n, vector<char>(n, 0));
for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    g[u][v] = 1;
    g[v][u] = 1;   // только для неориентированного
}

У неориентированного графа матрица симметрична относительно главной диагонали, у ориентированного — вообще говоря, нет.

Память — $O(n^2)$. При $n = 10^5$ это $10^{10}$ ячеек, то есть матрица применима только при $n$ примерно до пяти тысяч.

Зато проверка «есть ли ребро между $u$ и $v$» стоит константу — единственная операция, где матрица выигрывает.

Список смежности

Для каждой вершины храним вектор её соседей.

vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
}

Память — $O(n + m)$. Обход всех соседей вершины — $O(\deg v)$, а обход всех соседей всех вершин — $O(n + m)$, потому что каждое ребро встретится дважды.

Это рабочий формат по умолчанию. Почти все алгоритмы в разделе написаны для него, и переписывать их под матрицу смысла нет.

Список рёбер

struct Edge { int u, v, weight; };
vector<Edge> edges(m);

Память — $O(m)$, минимальная из трёх. Но соседей вершины приходится искать проходом по всему списку, то есть за $O(m)$.

Формат кажется бесполезным, и почти всегда так и есть. Пригождается он ровно в двух местах: алгоритм Форда—Беллмана и алгоритм Краскала — там нужен именно перебор всех рёбер, а не соседей.

Обратите внимание на struct вместо pair<int, pair<int, int>>: как только у ребра появляется третье поле, пары становятся нечитаемыми. Подробнее — в статье про свои структуры.

Сравнение

операция	матрица	список смежности	список рёбер
память	$O(n^2)$	$O(n + m)$	$O(m)$
добавить ребро	$O(1)$	$O(1)$	$O(1)$
удалить ребро	$O(1)$	$O(\deg v)$	$O(m)$
есть ли ребро $u$–$v$	$O(1)$	$O(\deg v)$	$O(m)$
перебрать соседей $v$	$O(n)$	$O(\deg v)$	$O(m)$

Правило выбора: список смежности, если ограничения не говорят обратного. Матрица — когда $n$ мало (до 1000–2000) и нужны частые проверки наличия ребра. Список рёбер — когда алгоритм сам просит перебор рёбер.

Как граф обычно дают в условии

Чаще всего — списком рёбер: сначала $n$ и $m$, потом $m$ строк по паре вершин. Читают его при этом сразу в список смежности, как в коде выше.

Реже — матрицей из нулей и единиц. Ещё реже — списком соседей для каждой вершины.

Отдельная ловушка: нумерация вершин. В условиях почти всегда с единицы, в коде удобнее с нуля. Выберите одно и держитесь: смешение — источник ошибок, которые не видны на первом тесте, потому что нулевая вершина обычно тоже существует.