В предыдущем блоке мы разобрали хеш-таблицы — структуру, которая отвечает на вопрос «есть ли этот ключ?» за O(1). Хеш-таблица хороша для точечного поиска. Но есть целый класс задач, где данные — это не просто набор элементов, а связи между ними. Кто с кем дружит? Какой сервер смотрит на какой? Какой пакет зависит от какого? Для таких задач нужна структура, которая умеет хранить не значения, а отношения. Эта структура — граф.

Вы уже работали с деревьями — это частный случай графа. У дерева есть корень, иерархия и нет циклов. Граф снимает все эти ограничения: вершины могут быть соединены как угодно, циклы допустимы, «корня» нет. Дерево — граф, но не любой граф — дерево.

Графы делятся по двум осям. По направленности: ориентированный (directed) — рёбра имеют направление, как односторонняя улица; неориентированный (undirected) — рёбра двусторонние, как дружба в соцсети. По весу: взвешенный (weighted) — у каждого ребра есть числовое значение (расстояние, стоимость, пропускная способность); невзвешенный (unweighted) — все рёбра равнозначны.

Реальных примеров — масса. Социальная сеть: пользователи — вершины, дружба — рёбра (неориентированные). Карта дорог: города — вершины, дороги — рёбра с весом (расстояние). Интернет: серверы — вершины, соединения — рёбра. Граф зависимостей пакетов: пакет A зависит от B — ориентированное ребро A → B. Git-история: каждый коммит ссылается на родителей — ориентированный граф.

Вот небольшой взвешенный граф с пятью вершинами, который мы будем использовать на протяжении всего урока:

Этот граф неориентированный (все рёбра двусторонние) и взвешенный. Вершин — 5, рёбер — 6. Вопрос: как хранить его в памяти? Первый способ — матрица смежности (adjacency matrix). Заводим двумерный массив V × V, где V — число вершин. Элемент matrix[i, j] хранит вес ребра из вершины i в вершину j (или 0, если ребра нет).

Для нашего графа из 5 вершин это массив 5×5:

//  Строка = откуда, столбец = куда, значение = вес (0 = нет ребра)
//     0  1  2  3  4
//  0 [0, 4, 0, 2, 6]
//  1 [4, 0, 5, 0, 0]
//  2 [0, 5, 0, 3, 0]
//  3 [2, 0, 3, 0, 7]
//  4 [6, 0, 0, 7, 0]

int[,] matrix = new int[5, 5];

// Добавляем рёбра (неориентированный граф — симметрично)
void AddEdge(int[,] m, int from, int to, int weight)
{
    m[from, to] = weight;
    m[to, from] = weight; // убираем эту строку для ориентированного графа
}

AddEdge(matrix, 0, 1, 4);  // Москва — Питер
AddEdge(matrix, 0, 3, 2);  // Москва — Екатеринбург
AddEdge(matrix, 0, 4, 6);  // Москва — Новосибирск
AddEdge(matrix, 1, 2, 5);  // Питер — Казань
AddEdge(matrix, 2, 3, 3);  // Казань — Екатеринбург
AddEdge(matrix, 3, 4, 7);  // Екатеринбург — Новосибирск

// Проверить, есть ли ребро: O(1)
bool hasEdge = matrix[1, 2] != 0;  // true

// Получить всех соседей вершины 0: O(V)
for (int j = 0; j < 5; j++)
{
    if (matrix[0, j] != 0)
        Console.WriteLine($"0 → {j}, вес {matrix[0, j]}");
}

Сильная сторона матрицы — проверка наличия ребра за O(1): просто обращение к элементу массива. Слабая сторона — память: всегда O(V²) независимо от числа рёбер. 1000 вершин — уже миллион ячеек. Если граф разреженный (рёбер мало по сравнению с V²), большинство ячеек будут нулями.

Ещё один минус: чтобы перечислить всех соседей вершины, нужно пройти всю строку — O(V), даже если у вершины только 2 соседа.

Второй способ — список смежности (adjacency list). Для каждой вершины хранится список её соседей. В C# это удобно реализовать через Dictionary<int, List<(int neighbor, int weight)>>.

var graph = new Dictionary<int, List<(int neighbor, int weight)>>();

// Инициализируем вершины
for (int i = 0; i < 5; i++)
    graph[i] = new List<(int, int)>();

// Добавляем рёбра
void AddEdge(int from, int to, int weight)
{
    graph[from].Add((to, weight));
    graph[to].Add((from, weight));  // для неориентированного графа
}

AddEdge(0, 1, 4);  // Москва — Питер
AddEdge(0, 3, 2);  // Москва — Екатеринбург
AddEdge(0, 4, 6);  // Москва — Новосибирск
AddEdge(1, 2, 5);  // Питер — Казань
AddEdge(2, 3, 3);  // Казань — Екатеринбург
AddEdge(3, 4, 7);  // Екатеринбург — Новосибирск

// Получить всех соседей вершины 0: O(degree) — только реальные соседи
foreach (var (neighbor, weight) in graph[0])
    Console.WriteLine($"0 → {neighbor}, вес {weight}");

// Проверить наличие ребра 0 → 2: O(degree)
bool hasEdge = graph[0].Any(e => e.neighbor == 2);

Список смежности хранит только существующие рёбра. Память — O(V + E), где E — число рёбер. Для нашего графа: 5 вершин + 12 записей (6 рёбер × 2 направления) = 17 единиц, а не 25 ячеек матрицы. Для реальных разреженных графов разница колоссальная.

Перечислить соседей — O(degree), то есть пропорционально числу реальных связей. Для соцсети с 300 друзьями — 300 операций вместо миллиарда. Зато проверить наличие конкретного ребра — тоже O(degree): нужно перебрать список. Если важна мгновенная проверка рёбер — можно заменить List на HashSet или Dictionary и получить O(1).

Третье представление — список рёбер (edge list). Просто набор всех рёбер в виде кортежей (from, to, weight):

var edges = new List<(int from, int to, int weight)>
{
    (0, 1, 4),  // Москва — Питер
    (0, 3, 2),  // Москва — Екатеринбург
    (0, 4, 6),  // Москва — Новосибирск
    (1, 2, 5),  // Питер — Казань
    (2, 3, 3),  // Казань — Екатеринбург
    (3, 4, 7),  // Екатеринбург — Новосибирск
};

// Можно отсортировать по весу — основа алгоритма Краскала
edges.Sort((a, b) => a.weight.CompareTo(b.weight));

Список рёбер занимает O(E) памяти — минимум из трёх вариантов. Но найти соседей вершины — O(E): надо просмотреть весь список. Это представление используется в алгоритмах, которые работают именно с рёбрами, а не с вершинами, — прежде всего в алгоритме Краскала для построения минимального остовного дерева: там рёбра сортируются по весу и обрабатываются одно за другим.

Сравнение всех трёх вариантов:

Граф — структура из вершин и рёбер, описывает произвольные связи между объектами. Бывает ориентированным / неориентированным и взвешенным / невзвешенным.

Матрица смежности — двумерный массив V×V; проверка ребра за O(1), но памяти O(V²). Подходит для плотных графов.

Список смежности — словарь или массив списков соседей; памяти O(V+E), перебор соседей O(degree). Выбор по умолчанию для разреженных графов.

Список рёбер — набор кортежей (from, to, weight); памяти O(E), удобен для алгоритмов, сортирующих рёбра (Краскал).

Разреженный граф — у большинства вершин мало рёбер; E ≪ V². Большинство реальных графов разреженные.