Список смежности или матрица смежности: что выбрать и сколько это памяти?
Когда граф хранить списком смежности vector<int> g[], а когда матрицей bool adj[N][N]? У меня в задаче N до 2·10^5 вершин — матрица вообще влезет? И как это влияет на сложность обхода и проверки «есть ли ребро»?
2 ответа
Коротко: почти всегда список смежности. Матрица — только для маленьких плотных графов.
Список смежности vector<int> g[N]:
- Память O(V + E) — для каждого ребра пара чисел.
- Обход всех соседей v — O(deg(v)); полный обход графа O(V+E).
- Проверка «есть ли ребро (u,v)» — O(deg(u)) (надо просканировать список). Медленно, если часто нужна.
Матрица смежности bool adj[N][N]:
- Память O(V²) — фатально для больших N. При N=2·10^5 это 4·10^10 ячеек ≈ 40 ГБ даже по биту → не влезет никак.
- Проверка ребра (u,v) — O(1).
- Перебор соседей v — O(V) (идём по всей строке), даже если соседей мало.
Правило выбора:
- N до ~2000–5000 И граф плотный / нужны частые запросы «есть ли ребро» / алгоритм сам O(V²) (Флойд, плотный Прим) → матрица.
- N большое или граф разрежен (E ≈ V) → список смежности.
Для вашего N=2·10^5 матрица невозможна — только список. Память списка ≈ O(V+E), укладывается.
Если при списке нужны и быстрые запросы «есть ребро», держите рядом unordered_set/отсортированный список или хешируйте пары (u,v) — O(1)/O(log) на проверку, ценой памяти O(E).
Добавлю про производительность и константу. На больших графах вместо vector<int> g[N] иногда берут CSR-представление (Compressed Sparse Row): один массив всех соседей подряд + массив смещений start[v]. Это убирает накладные расходы на отдельные векторы и кэш-промахи — рёбра одной вершины лежат непрерывно. Строится за O(V+E) подсчётом степеней + префиксными суммами. На задачах с E ~ 10^6–10^7 это заметно быстрее.
И про матрицу для плотных графов есть приятный трюк: bitset<N> adj[N]. Память в 8 раз меньше обычного bool, а пересечения/объединения множеств соседей делаются битовыми операциями за O(N/64) — это ускоряет, например, подсчёт треугольников или транзитивное замыкание (Флойд-Уоршелл по достижимости на bitset работает за O(V³/64)).