От станций и дорог к абстракции

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

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

Мы будем нумеровать вершины идентификаторами от 0 до V − 1, где V — число вершин. Это не свойство графа, а удобство реализации: так проще хранить данные в массивах и ссылаться на вершины по числу. Рёбер в графе E штук. Каждое ребро соединяет две вершины.

Первое различие между графами: направленные и ненаправленные. В ненаправленном графе ребро между вершинами A и B означает связь в обе стороны: если A связано с B, то и B связано с A. Дорога между двумя городами двусторонняя. В направленном графе ребро идёт от одной вершины к другой, и обратное ребро не подразумевается. Ссылка со страницы A на страницу B не означает ссылку с B на A. Зависимость модуля A от модуля B означает, что A нужно собрать после B, но не наоборот.

Второе различие: взвешенные и невзвешенные. В невзвешенном графе ребро просто есть или его нет. Во взвешенном у каждого ребра есть число — вес: расстояние, стоимость, время. Веса — это отдельная характеристика ребра, не связанная с его направлением. Ребро может быть направленным и взвешенным, направленным и невзвешенным, ненаправленным и взвешенным, ненаправленным и невзвешенным. Мы будем держать эти характеристики отдельно, не смешивая.

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

Несколько терминов, без которых дальше не обойтись. Путь — это последовательность вершин, где каждая соседняя пара соединена ребром. Длина пути — число рёбер в нём. Вершина B достижима из A, если существует путь из A в B. В этом курсе простой цикл — замкнутый путь, в котором вершины, кроме совпадающих начала и конца, не повторяются. В простом ненаправленном графе он содержит хотя бы три ребра; проход по одному ребру туда и обратно циклом не считается. В ненаправленном графе цикл может выглядеть как треугольник: A—B—C—A.

Дерево, как мы его разбирали, — это связный ненаправленный граф без циклов. То есть дерево — частный случай графа. У дерева с V вершинами ровно V − 1 рёбер, и между любыми двумя вершинами существует единственный простой путь. Лес — это набор деревьев, не связанных друг с другом. Если граф несвязный, но каждая его связная компонента — дерево, то весь граф называют лесом. В нашем примере с изолированной вершиной 4 граф будет несвязным, но не лесом, потому что в компоненте из вершин 0, 1, 2, 3 есть цикл.

Три способа представления

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

Список рёбер — самый простой. Это массив пар (u, v), где u и v — концы ребра. Если в графе есть изолированные вершины, то для них в списке рёбер не будет записей, поэтому отдельно нужно указать число вершин V, чтобы они не потерялись. Если вершины заданы номерами 0..V−1, достаточно одного числа V и списка E рёбер: O(E + 1) памяти. Если отдельно хранятся записи всех вершин, вместе с ними потребуется O(V + E). Само число V не занимает O(V) памяти. Он удобен для алгоритмов, которые просто перебирают все рёбра: например, построение минимального остовного дерева. Но проверить, есть ли ребро между двумя конкретными вершинами, в списке рёбер стоит O(E) — нужно просмотреть все рёбра. Никакого «O(1) поиска ребра в списке рёбер» не существует.

Список смежности — массив, где для каждой вершины хранится список её соседей. Для ненаправленного графа ребро (u, v) добавляется дважды: v в список u и u в список v. Список смежности занимает O(V + E) памяти: V списков плюс суммарная длина списков, равная 2E для ненаправленного графа и E для направленного. Перебор соседей вершины занимает O(deg(v)), где deg(v) — степень вершины, то есть число её соседей. Проверка, есть ли ребро между u и v, занимает O(deg(u)): нужно просмотреть список соседей u. Список смежности — самое распространённое представление, потому что большинство алгоритмов работают именно с соседями вершин.

Матрица смежности — квадратная таблица V × V. Ячейка (i, j) равна 1, если между i и j есть ребро, и 0 иначе. Для ненаправленного графа матрица симметрична: (i, j) = (j, i). Память — O(V²), независимо от числа рёбер. Проверка, есть ли ребро между i и j, занимает O(1) — просто смотрим в ячейку. Но перебор соседей вершины i занимает O(V): нужно просмотреть всю строку i, даже если у вершины всего два соседа.

Выбор зависит от того, что мы будем делать с графом.

Разреженный граф — тот, в котором рёбер мало по сравнению с V²: E значительно меньше V². Плотный — тот, в котором рёбер много, близко к V². Для разреженных графов списки смежности экономнее: они занимают O(V + E), тогда как матрица всегда требует V² ячеек. Для плотных разница меньше, и матрица становится конкурентоспособной.

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

Чтобы не путаться с числами, приведём пример. Пусть V = 10 000. Тогда V² = 100 000 000 ячеек в матрице. Это сто миллионов ячеек независимо от того, сколько дорог реально существует. А для списка смежности при E = 30 000 мы храним около 10 000 списков и 60 000 записей в них — это на порядки меньше. Точные байты зависят от реализации и накладных расходов контейнеров, и обещать конкретные значения не стоит, но порядок величины виден: V² может стать проблемой задолго до того, как сам граф покажется большим.

Мы в этом уроке реализуем список смежности и матрицу смежности для одного и того же графа, чтобы сравнить их на практике.

Отдельно скажем про взвешенные графы, чтобы не смешивать с невзвешенными. В невзвешенном графе матрица смежности хранит bool: ребро есть или нет. false означает «ребра нет», и это однозначно. Во взвешенном графе в ячейке матрицы хранится вес ребра. Но тогда ноль в ячейке неоднозначен: это может быть ребро с весом 0 или отсутствие ребра. Чтобы различать, нужно либо использовать отдельное значение для отсутствия (например, null для nullable-типа или бесконечность), либо хранить признак наличия ребра отдельно. Мы не будем реализовывать взвешенную матрицу в этом уроке, но полезно помнить: как только появляются веса, простое «ноль = нет ребра» перестаёт работать.

То же касается списка смежности для взвешенного графа: вместо простого списка соседей хранят список пар (сосед, вес). Это изменение структуры данных, а не алгоритма, и оно не влияет на основную логику обходов.

Программа

Соберём конкретный пример. Граф с пятью вершинами 0, 1, 2, 3, 4. Рёбра: (0, 1), (0, 2), (1, 3), (2, 3). Вершина 4 изолирована. Граф ненаправленный, без петель (рёбер из вершины в саму себя), без кратных рёбер (одно и то же ребро не повторяется). Мы построим из одного списка рёбер и список смежности, и матрицу смежности, чтобы увидеть оба представления в работе.

using System;
using System.Collections.Generic;

int V = 5;
var edges = new (int U, int V)[]
{
    (0, 1), (0, 2), (1, 3), (2, 3)
};

var adj = new List<int>[V];
for (int i = 0; i < V; i++) adj[i] = new List<int>();
var matrix = new bool[V, V];

foreach (var e in edges)
{
    if (e.U < 0 || e.U >= V || e.V < 0 || e.V >= V)
        throw new ArgumentException("Конец ребра вне диапазона.");
    if (e.U == e.V)
        throw new ArgumentException("Петли не поддерживаются.");
    if (matrix[e.U, e.V])
        throw new ArgumentException("Кратное ребро.");
    adj[e.U].Add(e.V);
    adj[e.V].Add(e.U);
    matrix[e.U, e.V] = true;
    matrix[e.V, e.U] = true;
}

for (int i = 0; i < V; i++)
{
    if (adj[i].Count == 0)
    {
        Console.WriteLine(i + ": (нет)");
    }
    else
    {
        Console.WriteLine(i + ": " + string.Join(" ", adj[i]));
    }
}

for (int i = 0; i < V; i++)
{
    var row = new List<int>();
    for (int j = 0; j < V; j++)
    {
        row.Add(matrix[i, j] ? 1 : 0);
    }
    Console.WriteLine(string.Join(" ", row));
}

Console.WriteLine(matrix[0, 3]);
Console.WriteLine(matrix[2, 3]);

Вывод:

0: 1 2
1: 0 3
2: 0 3
3: 1 2
4: (нет)
0 1 1 0 0
1 0 0 1 0
1 0 0 1 0
0 1 1 0 0
0 0 0 0 0
False
True

Разберём. Список смежности: у вершины 0 соседи 1 и 2, у вершины 1 соседи 0 и 3, у вершины 2 соседи 0 и 3, у вершины 3 соседи 1 и 2, у вершины 4 соседей нет — печатаем «(нет)». Матрица смежности симметрична: строки 0 и 3 совпадают по структуре, строки 1 и 2 тоже. Вершина 4 — нулевая строка и нулевой столбец: она изолирована. Проверка рёбер: между 0 и 3 ребра нет (False), между 2 и 3 ребро есть (True).

Валидация проверяет три вещи: что концы рёбер в диапазоне 0..V−1, что нет петель, и что нет кратных рёбер. Кратные мы ловим через матрицу: перед добавлением ребра проверяем, не установлена ли уже ячейка. Если бы мы работали только со списком смежности, пришлось бы дополнительно проверять, нет ли уже такого соседа в списке, — либо договориться, что вход не содержит кратных рёбер, и не проверять вовсе. Мы выбрали явную проверку через матрицу: она даёт O(1) на проверку и делает вход гарантированно простым.

Для нашего графа: V = 5, E = 4. Список смежности занимает 5 списков плюс 8 записей (2E для ненаправленного). Матрица занимает 25 ячеек. На таком маленьком графе разница незаметна, но с ростом V картина меняется.

Список смежности: память O(V + E), перебор соседей O(deg), проверка ребра O(deg). Матрица смежности: память O(V²), перебор соседей O(V), проверка ребра O(1). Для разреженных графов список смежности выигрывает и по памяти, и по перебору соседей. Для плотных графов матрица может оказаться удобнее за счёт быстрой проверки конкретных рёбер.

Но выбор — это не только арифметика. Модель тоже важна: что означают вершины, что означают рёбра, направлены ли они, есть ли веса, что значат эти веса, допустимы ли циклы. Один и тот же набор вершин и рёбер можно смоделировать по-разному, и от модели зависит, какие алгоритмы будут применимы. Например, если граф описывает зависимости «модуль A требует модуль B», то рёбра направленные: A → B. Если граф описывает дороги между городами, рёбра обычно ненаправленные. Если веса — это расстояния, они должны быть неотрицательными; если это стоимости, они могут быть и отрицательными, но тогда алгоритм поиска кратчайшего пути нужно выбирать аккуратно. Об этих деталях мы будем говорить по мере появления конкретных алгоритмов.

Следующий урок — обход графа в ширину, или BFS. Это один из двух классических способов посетить достижимые из старта вершины по уровням. Он опирается на очередь, которую мы уже разбирали, и на список смежности — то представление, которое мы только что построили.