Теория графов для программистов / Habr

Что забыли Графы в программировании?

Для начала уточню: граф Монте‑Кристо и прочие персонажи тут ни при чём. Речь пойдёт о математических графах — структуре, которая помогает решать массу задач в программировании, математике и олимпиадной информатике.

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

Впервые я встретил графы примерно в четвёртом классе, но начал активно использовать, только когда начал заниматься олимпиадным программированием.

В этой статье я расскажу вам про:

Основные элементы графа
Виды графов
Представление графов на примере кода C++

Граф и его элементы

Графом в математике называют абстрактную систему, состоящую из двух множеств — множеством вершин и множеством рёбер (связей между ними).

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

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

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

Виды графов

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

Полный граф

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

Это означает, что в данном графе каждая вершина соединена со всеми остальными вершинами и нет отсутствия ребер или нескольких ребер, соединяющих одинаковые вершины. Представьте, что в из каждого города ведут дороги в каждый другой, но между городом A и городом B есть только одна дорога.

Количество рёбер в полном графе считается просто.
Пусть есть n вершин. Каждая вершина соединена со всеми остальными, то есть из одной вершины выходит рёбер (степень каждой вершины). Если просто перемножить, получим , но это число учитывает каждое неориентированное ребро дважды — один раз от первой вершины, и второй раз от второй. Получим формулу:

$\frac{n(n-1)}{2}$

Ориентированный граф

Ориентированным графом называют граф, ребра которого имеют направление от одной вершины к другой.

Неформально, можно сказать, что если вершины A идет ребро в вершину B, то это означает, что из A в B можно добраться по нему, но необязательно, что из B можно добраться в A . В реальной жизни аналогом такого ребра может служить односторонняя дорога.

В примере выше из вершины A невозможно попасть куда-либо, так как в нее не выходит ни одно ребро. Вершин C и D соединены двумя ребрами, благодаря чему из C можно попасть в D и наоборот.

В таком графе важны понятия:

Входящая степень (сколько рёбер входит в вершину);
Исходящая степень (сколько выходит);
Источник (вершина с нулевой входящей степенью);
Сток (вершина с нулевой исходящей степенью).

Циклы в ориентированном графе могут существовать только, если движение по всем рёбрам совпадает с направлением.

Вместо обычной связности, тут появляются термины:

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

Взвешенный граф

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

Например, представьте карту Московской области. На ней есть города (вершины) и дороги между ними (рёбра). У каждой дороги указана её длина — это и есть вес ребра. Такая карта как раз и представляет собой взвешенный граф.

Вес играет ключевую роль, потому что именно от него зависит выбор оптимального пути — будь то минимальное расстояние, наименьшая стоимость или минимальное время.

Дерево

Деревом, называется связанный неориентированный граф без циклов.

Примером из жизни может служить структура папок в файловой системе: из любой папки есть путь к родительской, циклов нет, и из корневой можно добраться до любой вложенной.

Пример дерева (оно необязательно должно выглядеть именно так)

Важно отметить несколько свойства такого графа:

Граф содержит n вершин и ровно рёбер;
Добавление любого ребра создаёт цикл;
Удаление любого ребра нарушает связность;
У дерева нет циклов;
Между двумя вершинами всегда существует единственный путь.

Деревья обеспечивают быстрый поиск, эффективное хранение данных и хорошую логическую структуру.

Представление графов

Для работы с графами в программе необходимо их как-то хранить. В этом разделе будут представлены три основных способа. Каждый из них имеет свою асимптотику и удобен по-своему.

В программировании буквами признано записывать вершины, под буквой - вес.

Список рёбер

Список рёбер — это представление графа, в котором хранятся все рёбра в виде набора пар или троек числе. Каждое ребро записывается в виде () для невзвешенного графа или () для взвешенного соответственно. Его просто хранить, и оно хорошо обрабатывается глобально.

Такое представление удобно в работе с именно рёбрами, а не со структурой соседей (связанных вершин).

Пример чтения ориентированного взвешенного графа в виде списка рёбер на C++:

int n, m; // количество вершин и рёбер
cin >> n >> m;

vector<tuple<int,int,int>> edges; // рёбра

for (int = 0; i < m; i++){
  int u, v, w;
  cin >> u >> v >> w;
  edges.push_back({u, v, w});
}

Память:

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

Список смежностей — это представление графа, где для каждой вершины хранится список её соседей (иногда с их весами) (: (),..., ()). Стандарт для большинства алгоритмов.

Отлично подходит для алгоритмов требующих частых обходов, поисков путей и работы с соседями вершины.

Пример чтения ориентированного взвешенного графа в виде списка смежностей на C++:

int n, m;
cin >> n >> m;

vector<vector<pair<int,int>>> g(n+1); // для 1 .. n вершины (v, w)

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

Память:

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

Матрица смежностей — это представление графа с помощью квадратной таблицы размером , где — количество вершин. Для элемента матрицы $a_{ij}$ существует два значения: 1 (во взвешенном графе будет равен ), если есть ребро , иначе 0.

Если граф небольшой и много рёбер, данное представление наиболее удобное и эффективное.

Пример чтения ориентированного взвешенного графа в виде матрицы смежностей на C++:

int n, m;
cin >> n >> m;

vector<vector<int>> g(n+1, vector<int>(n+1, INF)); 

for (int i = 1; i <= n; i++) g[i][i] = 0; // отсутсвует ребро из v в v


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

Память:

В этой статье я постарался максимально понятно объяснить основную теорию по графам для программистов. В следующей статье я поведаю об основных алгоритмах и их примененьям.

Для более точных, с математической стороны, определений всех понятий рекомендую обратиться к википедии и другим более научным статьям.