Топология и хранение графовGraph topology & storage

Граф G = (V, E) — это пара из множества вершин (vertices, узлы, V) и множества рёбер (edges, E), где каждое ребро связывает две вершины. Всё остальное — терминологические уточнения этой одной идеи: ориентированный граф (directed, digraph) — ребро имеет направление (A→B не то же самое, что B→A); неориентированный — связь симметрична (A—B значит одновременно и A→B, и B→A); взвешенный граф — у каждого ребра есть число (вес: расстояние, стоимость, пропускная способность).A graph G = (V, E) is a pair: a set of vertices (V) and a set of edges (E), where each edge connects two vertices. Everything else is a terminological refinement of that one idea: a directed graph (digraph) — an edge has a direction (A→B isn't the same as B→A); an undirected graph — the connection is symmetric (A—B means both A→B and B→A at once); a weighted graph — every edge carries a number (weight: distance, cost, capacity).

Дополнительная терминология, которая пригодится дальше: степень вершины (degree) — число инцидентных ей рёбер (для ориентированного графа отдельно считают in-degree и out-degree); путь — последовательность рёбер без повторения вершин; цикл — путь, начинающийся и заканчивающийся в одной вершине; граф без циклов называется ациклическим (DAG — Directed Acyclic Graph, если он ещё и ориентированный).Extra terminology you'll need going forward: a vertex's degree — the number of edges touching it (a directed graph counts in-degree and out-degree separately); a path — a sequence of edges with no repeated vertices; a cycle — a path that starts and ends at the same vertex; a graph with no cycles is called acyclic (a DAG — Directed Acyclic Graph — if it's also directed).

Граф — это абстракция; в памяти его нужно представить конкретной структурой данных. Выбор представления определяет асимптотику почти всех операций дальше, поэтому это первое, а не последнее решение при работе с графом.A graph is an abstraction; in memory it must be represented by a concrete data structure. That choice determines the time complexity of almost every later operation, which makes it the first decision when working with a graph, not an afterthought.

Матрица смежности (Adjacency Matrix)Adjacency matrix

Двумерный массив V×V, где ячейка [i][j] хранит 1 (или вес), если между i и j есть ребро, иначе 0. Проверка "есть ли ребро между i и j" — O(1), но память — O(V²) независимо от того, сколько реальных рёбер в графе. Оправдана только для плотных графов (E близко к V²) или когда V мало (сотни, а не миллионы вершин).A V×V 2D array where cell [i][j] holds 1 (or a weight) if an edge exists between i and j, otherwise 0. Checking "is there an edge between i and j" is O(1), but memory is O(V²) regardless of how many edges actually exist. Justified only for dense graphs (E close to V²) or when V is small (hundreds, not millions of vertices).

Как именно строится матрица, шаг за шагом: рисуем пустую таблицу V×V, где и строки, и столбцы подписаны вершинами графа. Затем берём рёбра графа по одному — для каждого ребра (u,v) ставим 1 в ячейку [u][v]. Если граф неориентированный, дополнительно ставим 1 и в "зеркальную" ячейку [v][u] — раз связь симметрична, матрица тоже получается симметричной относительно главной диагонали. Все ячейки, для которых ребра не было, остаются 0.How the matrix is actually built, step by step: draw an empty V×V table, with both rows and columns labeled by the graph's vertices. Then take the graph's edges one at a time — for each edge (u,v), put a 1 in cell [u][v]. If the graph is undirected, also put a 1 in the "mirror" cell [v][u] — since the connection is symmetric, the matrix ends up symmetric across its main diagonal too. Every cell with no corresponding edge stays 0.

std::vector<std::vector<int>> adj(V, std::vector<int>(V, 0));
adj[u][v] = 1; adj[v][u] = 1; // неориентированное ребро u-v// undirected edge u-v
// проверка ребра: O(1)// edge check: O(1)
bool connected = adj[u][v];

Для ориентированного графа "зеркальную" ячейку не заполняют — ребро u→v даёт только [u][v]=1, а [v][u] остаётся 0, если нет отдельного обратного ребра. Матрица в этом случае перестаёт быть симметричной, и именно эта асимметрия — то место, откуда считывается направление связи.For a directed graph, the "mirror" cell isn't filled in — an edge u→v only sets [u][v]=1, and [v][u] stays 0 unless a separate reverse edge exists. The matrix stops being symmetric in this case, and that asymmetry is exactly where the connection's direction is read from.

Список смежности (Adjacency List)Adjacency list

Массив (или хэш-таблица) из V списков — для каждой вершины хранится только список её реальных соседей. Память — O(V + E), что для разреженных графов (реальный мир: соцсети, дорожные сети, веб-граф — почти всегда разреженные) кардинально экономнее матрицы. Проверка ребра деградирует до O(deg(v)) — нужно пройти список соседей, — но обход всех соседей вершины (главная операция в BFS/DFS) становится ровно O(deg(v)), без лишнего сканирования нулей.An array (or hash table) of V lists — each vertex stores only the list of its real neighbors. Memory is O(V + E), which for sparse graphs (the real world — social networks, road networks, the web graph — is almost always sparse) is dramatically cheaper than a matrix. Edge-check degrades to O(deg(v)) — you must walk the neighbor list — but iterating a vertex's neighbors (the main operation in BFS/DFS) becomes exactly O(deg(v)), with no wasted scanning of zeros.

std::vector<std::vector<int>> adj(V);
adj[u].push_back(v); adj[v].push_back(u); // неориентированное ребро// undirected edge
// обход соседей: O(deg(u))// iterating neighbors: O(deg(u))
for (int v : adj[u]) { /* ... *//* ... */ }

CSR (Compressed Sparse Row)

Список смежности как std::vector<std::vector<int>> — это V отдельных аллокаций, разбросанных по куче: обход соседей одной вершины — это последовательный проход по памяти, но переход от вершины к вершине — случайный прыжок по куче, что плохо для кэша процессора. CSR решает это, храня все списки соседей в одном непрерывном массиве (`edges`), плюс отдельный массив смещений (`offsets`), где `offsets[v]` — индекс начала соседей вершины v в `edges`. Соседи вершины v — это `edges[offsets[v] .. offsets[v+1])`. На графах с миллионами вершин (веб-граф, графовые нейросети) переход на CSR — стандартная оптимизация, дающая на порядок лучшую локальность обращений к памяти при том же O(V+E) по объёму.An adjacency list as std::vector<std::vector<int>> is V separate heap allocations scattered across memory: iterating one vertex's neighbors is a sequential memory scan, but moving from vertex to vertex is a random heap jump, which is bad for the CPU cache. CSR fixes this by storing all neighbor lists in one contiguous array (`edges`), plus a separate offsets array, where `offsets[v]` is the index where vertex v's neighbors start in `edges`. Vertex v's neighbors are `edges[offsets[v] .. offsets[v+1])`. On graphs with millions of vertices (the web graph, graph neural networks), switching to CSR is a standard optimization, giving an order-of-magnitude better memory locality at the same O(V+E) size.

// граф: 0→{1,2}, 1→{2}, 2→{}// graph: 0→{1,2}, 1→{2}, 2→{}
std::vector<int> offsets = {0, 2, 3, 3}; // offsets[v+1]-offsets[v] = degree(v)// offsets[v+1]-offsets[v] = degree(v)
std::vector<int> edges   = {1, 2, 2};       // один сплошной массив// one flat array
// соседи вершины 0: edges[offsets[0]..offsets[1]) = edges[0..2) = {1, 2}// vertex 0's neighbors: edges[offsets[0]..offsets[1]) = edges[0..2) = {1, 2}