Алгоритмы теории графов на C++

Введение в графы: терминология и способы представления

Добро пожаловать на курс «Алгоритмы теории графов на C++». Мы начинаем наше путешествие с фундаментальных понятий. Графы — это не просто абстрактная математическая структура, это скелет современного цифрового мира. Социальные сети, навигаторы, интернет-маршрутизация, зависимости программных пакетов — всё это графы.

В этой статье мы разберем, из чего состоит граф, какие виды графов бывают и, самое главное для программиста, как эффективно хранить их в памяти компьютера, используя язык C++.

Что такое граф?

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

Формально граф $G$ определяется как пара множеств:

$$G = (V, E)$$

Где $G$ — сам граф, $V$ — множество вершин (от англ. vertex), а $E$ — множество ребер (от англ. edge), соединяющих эти вершины.

Основные термины

Чтобы говорить на одном языке, определим ключевые понятия:

• Вершина (Vertex/Node) — это фундаментальная единица графа (точка на схеме). В C++ мы часто обозначаем их целыми числами ($0, 1, 2...$) для удобства индексации.
• Ребро (Edge) — это связь между двумя вершинами. Если ребро соединяет вершины $u$ и $v$, мы говорим, что они смежны.
• Степень вершины — количество ребер, инцидентных (подсоединенных) данной вершине.

Классификация графов

Графы бывают разными, и выбор алгоритма часто зависит от типа графа.

1. Ориентированные и неориентированные

• Неориентированный граф: Ребра не имеют направления. Связь между $A$ и $B$ работает в обе стороны (как рукопожатие). Если вы можете пройти от $A$ к $B$, то можете и от $B$ к $A$.
• Ориентированный граф (орграф): Ребра имеют направление (стрелки). Связь $A o B$ не означает наличие связи $B o A$ (как подписка в социальной сети: вы подписаны на знаменитость, но она на вас — нет).

2. Взвешенные и невзвешенные

• Невзвешенный граф: Все ребра равнозначны. Нам важно только наличие связи.
• Взвешенный граф: Каждому ребру приписано число — вес (стоимость, длина, пропускная способность). Например, в навигаторе весом ребра может быть расстояние между перекрестками или время в пути.

3. Циклические и ациклические

Если, двигаясь по ребрам, можно вернуться в стартовую вершину, не проходя по одному ребру дважды (в обратном направлении для неориентированных), то в графе есть цикл. Графы без циклов часто называют деревьями (если они связны) или лесами.

Способы представления графа в C++

Компьютер не может «видеть» рисунок графа. Нам нужно перевести визуальную структуру в структуру данных. Существует два основных способа хранения графа: матрица смежности и списки смежности. Выбор зависит от плотности графа и ограничений по памяти.

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

Матрица смежности — это двумерный массив (таблица) размером $V imes V$, где $V$ — количество вершин.

Пусть у нас есть матрица $A$. Значение ячейки $A[i][j]$ определяет наличие ребра между вершиной $i$ и вершиной $j$.

• Для невзвешенного графа: $1$ (или true), если ребро есть, и $0$ (или false), если нет.
• Для взвешенного графа: в ячейке хранится вес ребра. Отсутствие ребра обычно обозначается специальным значением (например, бесконечностью или -1).

Рассмотрим пример реализации на C++:

#include <iostream>
#include <vector>

// Пример создания матрицы смежности для 5 вершин
int main() {
    int n = 5; // Количество вершин
    // Создаем матрицу n x n, заполненную нулями
    std::vector<std::vector<int>> adjMatrix(n, std::vector<int>(n, 0));

    // Добавляем ребро между вершиной 0 и 1 (неориентированное)
    adjMatrix[0][1] = 1;
    adjMatrix[1][0] = 1;

    // Добавляем ребро между 1 и 4
    adjMatrix[1][4] = 1;
    adjMatrix[4][1] = 1;

    // Проверка смежности
    if (adjMatrix[0][1] == 1) {
        std::cout << "Вершины 0 и 1 смежны" << std::endl;
    }

    return 0;
}

Анализ сложности:

Потребление памяти составляет:

$$S = O(V^2)$$

Где $S$ — объем занимаемой памяти, $O$ — асимптотическая оценка («О» большое), а $V$ — количество вершин в графе.

Плюсы:

• Проверка наличия ребра между двумя вершинами происходит мгновенно за $O(1)$, где $1$ означает константное время.
• Простота реализации.

Минусы:

• Требует много памяти. Если у вас 10 000 вершин, матрица займет около 400 МБ, даже если ребер почти нет.
• Перебор всех соседей вершины занимает $O(V)$, так как нужно пройти по всей строке матрицы.

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

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

В C++ для этого идеально подходит массив (или вектор) векторов: std::vector<std::vector<int>>.

Реализация на C++:

#include <iostream>
#include <vector>

int main() {
    int n = 5; // Количество вершин
    // Вектор векторов. adjList[i] хранит список соседей вершины i
    std::vector<std::vector<int>> adjList(n);

    // Добавляем ребро 0-1 (неориентированное)
    adjList[0].push_back(1);
    adjList[1].push_back(0);

    // Добавляем ребро 1-4
    adjList[1].push_back(4);
    adjList[4].push_back(1);

    // Перебор соседей вершины 1
    std::cout << "Соседи вершины 1: ";
    for (int neighbor : adjList[1]) {
        std::cout << neighbor << " ";
    }
    std::cout << std::endl;

    return 0;
}

Для взвешенного графа мы можем хранить пары (сосед, вес): std::vector<std::vector<std::pair<int, int>>> adjList;

Анализ сложности:

Потребление памяти:

$$S = O(V + E)$$

Где $S$ — память, $V$ — количество вершин, а $E$ — количество ребер.

Плюсы:

• Экономия памяти для разреженных графов (где ребер мало).
• Перебор соседей вершины занимает время, пропорциональное их количеству (степени вершины), что намного быстрее $O(V)$ в разреженных графах.

Минусы:

• Проверка наличия ребра между $u$ и $v$ не мгновенна, нужно пробежать по списку соседей $u$.

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

Чтобы выбрать правильную структуру, нужно оценить плотность графа.

Плотность определяется отношением количества ребер к максимально возможному количеству ребер. Максимальное количество ребер в неориентированном графе:

$$E_{max} = \frac{V(V-1)}{2}$$

Где $E_{max}$ — максимальное число ребер, а $V$ — число вершин.

Характеристика	Матрица смежности	Списки смежности
Память	$O(V^2)$	$O(V + E)$
Проверка смежности $(u, v)$	$O(1)$	$O(\text{degree}(u))$
Перебор всех соседей	$O(V)$	$O(\text{degree}(u))$
Добавление вершины	Сложно ($O(V^2)$ при пересоздании)	Легко ($O(1)$ амортизировано)
Удаление ребра	$O(1)$	$O(\text{degree}(u))$

«Если граф разреженный (ребер мало), используйте списки смежности. Если граф плотный (ребер почти $V^2$) или вершин очень мало — матрица смежности может быть удобнее». — Общее правило олимпиадного программирования.

Заключение

Мы познакомились с базовой терминологией теории графов и двумя основными способами их представления в C++. Матрица смежности хороша для быстрых проверок связей в небольших или плотных графах. Списки смежности — это стандарт де-факто для большинства алгоритмов, так как они экономят память и позволяют эффективно обходить граф.

В следующих статьях мы научимся обходить эти структуры, используя поиск в глубину (DFS) и поиск в ширину (BFS).

Алгоритмы обхода графа: реализация поиска в глубину (DFS) и поиска в ширину (BFS)

В предыдущей статье мы разобрали, как хранить графы в памяти компьютера, используя списки смежности и матрицы смежности. Но просто хранить данные недостаточно. Чтобы решать задачи — будь то поиск пути в лабиринте, анализ социальных связей или проверка зависимостей пакетов — нам нужно уметь «путешествовать» по графу.

Этот процесс называется обходом графа. Существует два фундаментальных алгоритма обхода: Поиск в глубину (Depth-First Search, DFS) и Поиск в ширину (Breadth-First Search, BFS). Сегодня мы разберем их логику, реализацию на C++ и поймем, когда какой алгоритм применять.

Поиск в глубину (DFS)

Концепция

Поиск в глубину напоминает стратегию прохождения лабиринта по правилу «держись правой руки». Мы идем вперед по выбранному пути до тех пор, пока не упремся в тупик. Как только идти дальше некуда, мы возвращаемся назад (делаем шаг назад) до ближайшей развилки, где есть еще неисследованные пути, и сворачиваем туда.

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

Алгоритм

Для реализации DFS нам понадобится массив (или вектор) visited, чтобы отмечать вершины, в которых мы уже были. Это предотвратит зацикливание алгоритма.

1. Помечаем текущую вершину как посещенную.
2. Для каждой соседней вершины, которая еще не была посещена, рекурсивно запускаем DFS.

Реализация на C++

DFS чаще всего реализуют с помощью рекурсии. Это естественно, так как стек вызовов функций (Call Stack) автоматически запоминает путь, по которому мы пришли, позволяя легко возвращаться назад.

#include <iostream>
#include <vector>

// Используем списки смежности для представления графа
using Graph = std::vector<std::vector<int>>;

// Рекурсивная функция DFS
void dfs(int u, const Graph& adj, std::vector<bool>& visited) {
    // 1. Помечаем вершину как посещенную
    visited[u] = true;
    std::cout << "Посетили вершину: " << u << std::endl;

    // 2. Проходим по всем соседям
    for (int v : adj[u]) {
        // Если сосед еще не посещен, идем в него
        if (!visited[v]) {
            dfs(v, adj, visited);
        }
    }
}

int main() {
    int n = 5; // Количество вершин
    Graph adj(n);
    std::vector<bool> visited(n, false);

    // Строим граф (неориентированный)
    // 0 -- 1 -- 2
    // |    |
    // 4 -- 3
    adj[0] = {1, 4};
    adj[1] = {0, 2, 3};
    adj[2] = {1};
    adj[3] = {1, 4};
    adj[4] = {0, 3};

    std::cout << "Запуск DFS от вершины 0:" << std::endl;
    dfs(0, adj, visited);

    return 0;
}

Анализ сложности

Временная сложность DFS зависит от способа представления графа. Для списков смежности она составляет:

$$O(V + E)$$

Где $V$ — количество вершин, а $E$ — количество ребер в графе. Мы посещаем каждую вершину один раз и просматриваем каждое ребро (дважды для неориентированного графа).

Пространственная сложность (память) в худшем случае составляет $O(V)$ для хранения стека рекурсии (если граф вырожден в линию) и массива visited.

Применение DFS

• Поиск цикла в графе.
• Топологическая сортировка.
• Поиск компонент связности.
• Решение головоломок (например, выход из лабиринта), где нужно найти хоть какой-то путь.

Поиск в ширину (BFS)

Концепция

Поиск в ширину работает иначе. Представьте, что вы бросили камень в центр озера. Волны расходятся кругами во все стороны одновременно. Сначала волна накрывает ближайшие точки, затем те, что чуть дальше, и так далее.

BFS исследует граф послойно. Сначала мы посещаем всех непосредственных соседей стартовой вершины (расстояние 1), затем соседей соседей (расстояние 2) и так далее.

Алгоритм

Так как нам нужно обрабатывать вершины в порядке их обнаружения («первым пришел — первым ушел»), рекурсия здесь не подойдет. Нам нужна структура данных Очередь (Queue).

1. Помещаем стартовую вершину в очередь и помечаем как посещенную.
2. Пока очередь не пуста:
   • Извлекаем вершину из начала очереди.
   • Просматриваем всех её соседей.
   • Если сосед не посещен: помечаем его, добавляем в конец очереди.

Реализация на C++

Для работы с очередью используем стандартный контейнер std::queue.

#include <iostream>
#include <vector>
#include <queue>

using Graph = std::vector<std::vector<int>>;

void bfs(int startNode, const Graph& adj) {
    int n = adj.size();
    std::vector<bool> visited(n, false);
    std::queue<int> q;

    // Начальная инициализация
    visited[startNode] = true;
    q.push(startNode);

    std::cout << "Порядок обхода BFS: ";

    while (!q.empty()) {
        // Извлекаем текущую вершину
        int u = q.front();
        q.pop();

        std::cout << u << " ";

        // Проходим по соседям
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    std::cout << std::endl;
}

int main() {
    // Тот же граф
    int n = 5;
    Graph adj(n);
    adj[0] = {1, 4};
    adj[1] = {0, 2, 3};
    adj[2] = {1};
    adj[3] = {1, 4};
    adj[4] = {0, 3};

    bfs(0, adj);

    return 0;
}

Анализ сложности

Временная сложность BFS аналогична DFS:

$$O(V + E)$$

Где $V$ — число вершин, а $E$ — число ребер. Каждая вершина и каждое ребро обрабатываются константное количество раз.

Пространственная сложность составляет $O(V)$, так как в очереди в худшем случае может оказаться значительная часть вершин графа.

Применение BFS

Самое важное свойство BFS: в невзвешенном графе он находит кратчайший путь (по количеству ребер) от стартовой вершины до любой другой.

• Поиск кратчайшего пути в невзвешенных графах.
• Нахождение всех вершин на расстоянии $K$ от заданной.
• Web-crawlers (поисковые роботы), сканирующие ссылки на страницах.
• Алгоритмы заливки в графических редакторах.

Сравнение DFS и BFS

Выбор алгоритма зависит от задачи. Давайте сведем их различия в таблицу.

Характеристика	DFS (Глубина)	BFS (Ширина)
Структура данных	Стек (часто неявный, через рекурсию)	Очередь (std::queue)
Стратегия	Идти вперед до упора, потом назад	Идти широким фронтом, слой за слоем
Кратчайший путь	Не гарантирует (может найти длинный путь первым)	Гарантирует (в невзвешенном графе)
Потребление памяти	Меньше, если искомая вершина глубоко	Больше, если граф «широкий» (много соседей)

Практический пример: Поиск кратчайшего расстояния

Допустим, нам нужно не просто обойти граф, а найти массив расстояний dist, где dist[i] — это минимальное количество ребер от старта до вершины i. Для этого идеально подходит BFS.

Модифицируем наш код:

void bfsDistances(int startNode, const Graph& adj) {
    int n = adj.size();
    // Инициализируем расстояния -1 (как признак "не посещено")
    std::vector<int> dist(n, -1);
    std::queue<int> q;

    dist[startNode] = 0;
    q.push(startNode);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (dist[v] == -1) { // Если еще не посетили
                dist[v] = dist[u] + 1; // Расстояние на 1 больше, чем у родителя
                q.push(v);
            }
        }
    }

    // Вывод результатов
    for (int i = 0; i < n; ++i) {
        std::cout << "Расстояние до " << i << ": " << dist[i] << std::endl;
    }
}

Обратите внимание: здесь массив visited нам не нужен, так как проверка dist[v] == -1 выполняет ту же роль.

Заключение

Мы изучили два кита алгоритмической теории графов: DFS и BFS. Запомните главное правило:

Если вам нужно найти кратчайший путь в графе без весов или проанализировать граф послойно — используйте BFS. Если вам нужно исследовать весь граф, найти циклы или проверить связность, и вам важна простота реализации (рекурсия) — используйте DFS.

В следующей статье мы усложним задачу и рассмотрим графы, где ребра имеют вес (стоимость). Там простой BFS уже не сработает, и нам понадобится алгоритм Дейкстры.

Поиск кратчайших путей: алгоритмы Дейкстры, Беллмана-Форда и Флойда-Уоршелла

В предыдущих статьях мы научились обходить граф с помощью BFS и DFS. Мы выяснили, что поиск в ширину (BFS) способен найти кратчайший путь в невзвешенном графе. Но что делать, если ребра имеют вес? Представьте, что вы строите маршрут в навигаторе: одна дорога короче, но там пробка (большой вес), а другая длиннее, но скоростная (маленький вес).

В этой статье мы разберем три классических алгоритма для поиска кратчайших путей во взвешенных графах: алгоритм Дейкстры, алгоритм Беллмана-Форда и алгоритм Флойда-Уоршелла. Мы узнаем, как они работают, реализуем их на C++ и поймем, в каких ситуациях применять каждый из них.

Постановка задачи

Пусть дан взвешенный граф $G = (V, E)$, где каждому ребру приписан вес $w$. Наша цель — найти путь между вершинами, сумма весов ребер которого минимальна.

Ключевое понятие здесь — релаксация ребра.

Представьте, что мы знаем какое-то расстояние до вершины $v$, обозначим его $d[v]$. Если мы находим ребро из $u$ в $v$ с весом $w$, мы проверяем: не будет ли путь через $u$ короче текущего известного пути до $v$?

Формально условие релаксации выглядит так:

$$d[v] > d[u] + w(u, v)$$

Где:

• $d[v]$ — текущее известное кратчайшее расстояние от старта до вершины $v$.
• $d[u]$ — кратчайшее расстояние от старта до вершины $u$.
• $w(u, v)$ — вес ребра между $u$ и $v$.

Если неравенство выполняется, мы обновляем $d[v] = d[u] + w(u, v)$.

Алгоритм Дейкстры (Dijkstra's Algorithm)

Это самый популярный алгоритм для поиска кратчайшего пути от одной стартовой вершины до всех остальных. Он работает по «жадному» принципу: на каждом шаге мы выбираем не посещенную вершину с минимальным текущим расстоянием и пытаемся улучшить пути до её соседей.

Важное ограничение: Алгоритм Дейкстры работает корректно только с неотрицательными весами ребер.

Реализация на C++

Для эффективного выбора вершины с минимальным расстоянием мы используем очередь с приоритетом (std::priority_queue).

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

// Структура для хранения ребра: {сосед, вес}
using Graph = vector<vector<pair<int, int>>>;

void dijkstra(int start, int n, const Graph& adj) {
    // Расстояния до всех вершин инициализируем бесконечностью
    vector<int> dist(n, INF);
    dist[start] = 0;

    // Очередь с приоритетом хранит пары {расстояние, вершина}
    // greater обеспечивает сортировку от меньшего к большему (min-heap)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push({0, start});

    while (!pq.empty()) {
        // Извлекаем вершину с минимальным расстоянием
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        // Если текущее расстояние в очереди больше уже найденного, пропускаем
        // Это «ленивое» удаление устаревших записей
        if (d > dist[u]) continue;

        // Проходим по соседям
        for (auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;

            // Шаг релаксации
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }

    // Вывод результатов
    for (int i = 0; i < n; ++i) {
        if (dist[i] == INF) cout << i << ": недостижима" << endl;
        else cout << i << ": " << dist[i] << endl;
    }
}

Сложность

Временная сложность реализации с приоритетной очередью:

$$O(E \log V)$$

Где $E$ — количество ребер, а $V$ — количество вершин. Логарифм появляется из-за операций с очередью.

Алгоритм Беллмана-Форда (Bellman-Ford Algorithm)

Что делать, если в графе есть ребра с отрицательным весом? Например, в финансовых графах это может означать прибыль, а не затраты. Дейкстра здесь сломается, так как «жадный» выбор локального минимума может оказаться ошибочным в глобальной перспективе.

Алгоритм Беллмана-Форда решает эту проблему. Он проще, но медленнее. Идея заключается в том, чтобы просто попытаться релаксировать все ребра графа $V-1$ раз.

Особенность: Отрицательные циклы

Если в графе есть цикл с отрицательной суммой весов, то кратчайшего пути не существует (мы можем бесконечно крутиться в цикле, уменьшая путь). Беллман-Форд умеет детектировать такие циклы.

Реализация на C++

Здесь удобнее хранить граф просто как список ребер.

struct Edge {
    int u, v, w;
};

void bellmanFord(int start, int n, const vector<Edge>& edges) {
    vector<int> dist(n, INF);
    dist[start] = 0;

    // 1. Релаксация всех ребер n-1 раз
    for (int i = 0; i < n - 1; ++i) {
        for (const auto& e : edges) {
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
            }
        }
    }

    // 2. Проверка на наличие отрицательных циклов
    for (const auto& e : edges) {
        if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
            cout << "Граф содержит отрицательный цикл!" << endl;
            return;
        }
    }

    // Вывод расстояний...
}

Сложность

$$O(V \cdot E)$$

Где $V$ — количество вершин, $E$ — количество ребер. Это значительно медленнее Дейкстры для плотных графов.

Алгоритм Флойда-Уоршелла (Floyd-Warshall Algorithm)

Иногда нам нужно знать расстояние не от одной вершины до всех, а от каждой до каждой. Конечно, можно запустить Дейкстру $V$ раз, но алгоритм Флойда-Уоршелла делает это элегантнее, используя метод динамического программирования.

Он работает с матрицей смежности и постепенно улучшает пути, разрешая использовать в качестве промежуточных вершин сначала вершину 0, потом 1, и так далее до $N-1$.

Основная формула перехода:

$$D[i][j] = \min(D[i][j], D[i][k] + D[k][j])$$

Где:

• $D[i][j]$ — кратчайшее расстояние от $i$ до $j$.
• $D[i][k]$ — расстояние от $i$ до промежуточной вершины $k$.
• $D[k][j]$ — расстояние от $k$ до $j$.

Реализация на C++

Код удивительно компактен — всего три вложенных цикла.

void floydWarshall(int n, vector<vector<int>>& dist) {
    // dist изначально содержит веса ребер, INF где ребер нет, и 0 по диагонали

    for (int k = 0; k < n; ++k) {          // Промежуточная вершина
        for (int i = 0; i < n; ++i) {      // Откуда
            for (int j = 0; j < n; ++j) {  // Куда
                // Проверка на INF нужна, чтобы избежать переполнения при сложении
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

Сложность

$$O(V^3)$$

Где $V$ — количество вершин. Из-за кубической сложности алгоритм применим только для небольших графов (обычно до 400-500 вершин).

Сравнительная таблица

Подведем итоги, чтобы вы могли легко выбрать нужный инструмент.

Алгоритм	Задача	Веса ребер	Сложность	Примечание
BFS	От одной ко всем	Только 1 (невзвешенный)	$O(V+E)$	Самый быстрый для простых графов
Дейкстра	От одной ко всем	$\ge 0$ (неотрицательные)	$O(E \log V)$	Стандарт де-факто для навигации
Беллман-Форд	От одной ко всем	Любые	$O(V \cdot E)$	Умеет находить отрицательные циклы
Флойд-Уоршелл	Все ко всем	Любые (без отр. циклов)	$O(V^3)$	Прост в реализации, для малых графов

«Преждевременная оптимизация — корень всех зол». Если граф маленький ($V < 100$) и вам нужны все пути, пишите Флойда-Уоршелла — это 5 строк кода, и вы не ошибетесь.

В следующей статье мы рассмотрим одну из самых интересных структур данных для работы с множествами — систему непересекающихся множеств (DSU) и алгоритм Краскала для построения минимального остовного дерева.

Минимальные остовные деревья (алгоритмы Прима и Краскала) и система непересекающихся множеств (DSU)

В предыдущих статьях мы научились находить кратчайшие пути между двумя точками. Сегодня мы решим другую важную задачу оптимизации. Представьте, что вы — инженер, которому поручено соединить оптоволоконным кабелем $N$ городов. Вы знаете стоимость прокладки кабеля между любыми двумя городами. Ваша цель — соединить все города так, чтобы сеть была единой (из любого города можно было добраться в любой другой), а общая стоимость прокладки была минимальной.

Эта задача называется поиском Минимального Остовного Дерева (Minimum Spanning Tree, MST). Для её решения мы изучим два легендарных алгоритма — Прима и Краскала, а также познакомимся с мощной структурой данных — Системой непересекающихся множеств (Disjoint Set Union, DSU).

Что такое остовное дерево?

Давайте разберем терминологию.

1. Остовное дерево (Spanning Tree) графа $G$ — это подграф, который содержит все вершины исходного графа, является связным и не имеет циклов (то есть является деревом).
2. Минимальное остовное дерево (MST) — это такое остовное дерево, у которого сумма весов всех входящих в него ребер минимальна.

Если в графе $V$ вершин, то любое его остовное дерево будет содержать ровно $V - 1$ ребер.

Система непересекающихся множеств (DSU)

Прежде чем переходить к алгоритму Краскала, нам нужно научиться эффективно отслеживать, какие вершины уже соединены друг с другом, а какие — нет. Для этого используется структура данных DSU (Disjoint Set Union).

DSU позволяет решать две задачи:

1. Find: Определить, к какому множеству принадлежит элемент (проверить, находятся ли две вершины в одной компоненте связности).
2. Union: Объединить два множества в одно (соединить две компоненты связности ребром).

Принцип работы

Представьте, что каждая вершина изначально находится в своем собственном множестве, где она сама себе «лидер». Когда мы соединяем вершины $A$ и $B$, мы берем лидера множества $A$ и подчиняем его лидеру множества $B$.

Чтобы DSU работала быстро (почти за константное время), применяют две эвристики:

• Сжатие путей (Path Compression): Когда мы ищем лидера вершины, мы переподвешиваем её (и всех предков по пути) напрямую к лидеру.
• Объединение по рангу/размеру (Union by Rank/Size): При объединении мы всегда присоединяем меньшее дерево к большему, чтобы высота дерева росла медленнее.

Реализация DSU на C++

#include <vector>
#include <numeric>

struct DSU {
    std::vector<int> parent;
    std::vector<int> rank;

    DSU(int n) {
        parent.resize(n);
        // Изначально каждый элемент - родитель самого себя
        std::iota(parent.begin(), parent.end(), 0);
        rank.assign(n, 0);
    }

    // Найти лидера множества с сжатием путей
    int find_set(int v) {
        if (v == parent[v])
            return v;
        // Рекурсивно ищем лидера и запоминаем его для v
        return parent[v] = find_set(parent[v]);
    }

    // Объединить два множества
    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            // Эвристика рангов: присоединяем меньшее к большему
            if (rank[a] < rank[b])
                std::swap(a, b);
            parent[b] = a;
            if (rank[a] == rank[b])
                rank[a]++;
        }
    }
};

Временная сложность операций в DSU с обеими эвристиками составляет в среднем:

$$O(\alpha(n))$$

Где $\alpha(n)$ — обратная функция Аккермана, которая растет настолько медленно, что для всех разумных значений $n$ она не превышает 4. Можно считать, что операции выполняются за $O(1)$.

Алгоритм Краскала (Kruskal's Algorithm)

Алгоритм Краскала интуитивно понятен и использует «жадный» подход. Идея проста: давайте брать самые дешевые ребра и добавлять их в наш остов, следя за тем, чтобы не образовался цикл.

Шаги алгоритма

1. Создаем список всех ребер графа.
2. Сортируем ребра по возрастанию веса.
3. Инициализируем DSU, где каждая вершина — отдельное множество.
4. Перебираем отсортированные ребра. Пусть текущее ребро соединяет вершины $u$ и $v$ с весом $w$:
   • Проверяем, лежат ли $u$ и $v$ в разных множествах (используя find_set).
   • Если да: добавляем ребро в MST и объединяем множества $u$ и $v$ (используя union_sets).
   • Если нет (они уже в одном множестве): пропускаем ребро, иначе образуется цикл.

Реализация на C++

#include <iostream>
#include <vector>
#include <algorithm>

// Структура для хранения ребра
struct Edge {
    int u, v, weight;

    // Оператор для сортировки
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

// ... (Код структуры DSU из раздела выше) ...

int main() {
    int n = 4; // Количество вершин
    std::vector<Edge> edges;

    // Добавляем ребра: u, v, weight
    edges.push_back({0, 1, 10});
    edges.push_back({0, 2, 6});
    edges.push_back({0, 3, 5});
    edges.push_back({1, 3, 15});
    edges.push_back({2, 3, 4});

    // 1. Сортируем ребра
    std::sort(edges.begin(), edges.end());

    DSU dsu(n);
    int mst_weight = 0;
    std::vector<Edge> mst_edges;

    // 2. Проходим по ребрам
    for (const auto& edge : edges) {
        if (dsu.find_set(edge.u) != dsu.find_set(edge.v)) {
            mst_weight += edge.weight;
            mst_edges.push_back(edge);
            dsu.union_sets(edge.u, edge.v);
        }
    }

    std::cout << "Вес MST: " << mst_weight << std::endl;
    return 0;
}

Сложность алгоритма Краскала

Основное время занимает сортировка ребер.

$$O(E \log E)$$

Где $E$ — количество ребер в графе. Операции с DSU выполняются почти мгновенно. Так как $E \le V^2$, сложность можно также записать как $O(E \log V)$.

Алгоритм Прима (Prim's Algorithm)

Алгоритм Прима больше похож на алгоритм Дейкстры. Мы «выращиваем» дерево из одной стартовой вершины, на каждом шаге добавляя ближайшую к дереву вершину.

Шаги алгоритма

1. Выбираем произвольную стартовую вершину (например, 0) и помещаем её в остов.
2. Поддерживаем для каждой вершины, еще не входящей в остов, минимальный вес ребра, соединяющего её с любой вершиной остова.
3. Пока не все вершины добавлены:
   • Выбираем вершину с минимальным весом ребра, ведущего в остов.
   • Добавляем её в остов.
   • Обновляем расстояния до её соседей.

Для эффективного поиска минимума используем очередь с приоритетом (std::priority_queue).

Реализация на C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int INF = 1e9;

void prim(int n, const vector<vector<pair<int, int>>>& adj) {
    int total_weight = 0;
    vector<int> min_e(n, INF); // Минимальное ребро до остова
    vector<bool> visited(n, false);

    // Очередь хранит пары {вес, вершина}, сортировка по весу (min-heap)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    // Начинаем с вершины 0
    min_e[0] = 0;
    pq.push({0, 0});

    while (!pq.empty()) {
        int weight = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (visited[u]) continue;

        visited[u] = true;
        total_weight += weight;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;

            // Если сосед не в остове и новое ребро дешевле старого
            if (!visited[v] && w < min_e[v]) {
                min_e[v] = w;
                pq.push({min_e[v], v});
            }
        }
    }

    cout << "Вес MST (Прим): " << total_weight << endl;
}

Сложность алгоритма Прима

При использовании очереди с приоритетом сложность аналогична алгоритму Дейкстры:

$$O(E \log V)$$

Где $E$ — количество ребер, а $V$ — количество вершин.

Существует также реализация без очереди с приоритетом за $O(V^2)$, которая выгодна для очень плотных графов (где $E \approx V^2$).

Сравнение и выбор алгоритма

Какой алгоритм выбрать на практике?

Характеристика	Алгоритм Краскала	Алгоритм Прима (с priority_queue)
Идея	Объединение лесов (ребра)	Рост одного дерева (вершины)
Структуры данных	DSU, Сортировка	Priority Queue
Сложность	$O(E \log E)$	$O(E \log V)$
Предпочтение	Разреженные графы (мало ребер)	Плотные графы (много ребер)
Реализация	Проще, если есть готовый DSU	Похожа на Дейкстру

Совет: Если вам дан список ребер — пишите Краскала. Если граф задан матрицей смежности или списками смежности и он плотный — Прим может быть удобнее.

Заключение

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

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

Топологическая сортировка и поиск компонент сильной связности

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

Представьте, что вы собираете сложный механизм. Вы не можете установить крышку, пока не поставили двигатель. Или вы компилируете большую программу: файл A зависит от файла B, поэтому B должен быть скомпилирован раньше. А что, если файл A зависит от B, а B зависит от A? Это называется циклической зависимостью, и это проблема.

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

Топологическая сортировка (Topological Sort)

Что это такое?

Топологическая сортировка — это способ упорядочить вершины ориентированного графа в список так, что для каждого ребра $u \to v$ вершина $u$ стоит в списке раньше вершины $v$.

Простыми словами: это расстановка задач в таком порядке, чтобы все зависимости были соблюдены. Сначала мы делаем то, что ни от чего не зависит, потом то, что зависит только от уже сделанного, и так далее.

Условие существования

Топологическая сортировка возможна только если в графе нет циклов. Такой граф называется DAG (Directed Acyclic Graph — ориентированный ациклический граф).

Если в графе есть цикл (например, $A \to B \to C \to A$), то невозможно сказать, кто должен быть первым: $A$ должно быть перед $B$, $B$ перед $C$, а $C$ перед $A$. Это логическое противоречие.

Алгоритм (на основе DFS)

Существует несколько способов реализации, но самый элегантный использует Поиск в глубину (DFS). Идея основана на времени выхода из вершины.

Когда DFS завершает обработку вершины $u$ (то есть мы посетили всех её детей и возвращаемся назад), это означает, что все вершины, зависящие от $u$ (достижимые из неё), уже обработаны. Следовательно, в топологическом порядке $u$ должна стоять перед ними. Но так как мы выходим из рекурсии «с конца», мы будем добавлять вершины в список по мере выхода, а в конце просто перевернем этот список.

Шаги алгоритма:

1. Запускаем DFS для всех непосещенных вершин.
2. В функции DFS: сначала рекурсивно посещаем всех соседей.
3. Когда возвращаемся из рекурсии (все соседи обработаны), добавляем текущую вершину в специальный список.
4. После обхода всего графа переворачиваем список (или считываем его с конца).

Реализация на C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Глобальные переменные для графа
vector<vector<int>> adj;
vector<bool> visited;
vector<int> ans; // Сюда будем складывать результат

void dfs(int u) {
    visited[u] = true;

    // Проходим по всем соседям
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }

    // Ключевой момент: добавляем вершину ПОСЛЕ посещения всех детей
    ans.push_back(u);
}

void topologicalSort(int n) {
    visited.assign(n, false);
    ans.clear();

    // Запускаем DFS для всех компонент связности
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i);
        }
    }

    // Разворачиваем список, чтобы получить правильный порядок
    reverse(ans.begin(), ans.end());
}

int main() {
    int n = 6;
    adj.resize(n);

    // Пример графа (одежда):
    // 5(носки) -> 2(ботинки)
    // 5(носки) -> 0(брюки)
    // 4(трусы) -> 0(брюки)
    // 0(брюки) -> 2(ботинки)
    // 4(трусы) -> 1(туфли - ошибка в примере, пусть будет просто связь)
    // 3(рубашка) -> 1(пиджак)

    adj[5] = {0, 2};
    adj[4] = {0, 1};
    adj[2] = {3};
    adj[3] = {1};
    adj[0] = {};
    adj[1] = {};

    topologicalSort(n);

    cout << "Топологический порядок: ";
    for (int u : ans) {
        cout << u << " ";
    }
    cout << endl;

    return 0;
}

Анализ сложности

Временная сложность алгоритма такая же, как у обычного DFS:

$$O(V + E)$$

Где $V$ — количество вершин, а $E$ — количество ребер. Мы посещаем каждую вершину и каждое ребро ровно один раз.

Компоненты сильной связности (SCC)

Определение

В ориентированном графе понятие связности сложнее, чем в неориентированном. Если мы можем пройти от $A$ к $B$, это не значит, что мы можем вернуться от $B$ к $A$ (улица с односторонним движением).

Компонента сильной связности (Strongly Connected Component, SCC) — это такое максимальное подмножество вершин, в котором любая вершина достижима из любой другой вершины этого же подмножества.

Если сжать каждую такую компоненту в одну точку, то полученный граф (граф конденсации) всегда будет ациклическим (DAG).

Зачем это нужно?

• Поиск циклов зависимостей (например, в Excel, когда ячейки ссылаются друг на друга).
• Анализ социальных сетей (тесные сообщества).
• Оптимизация программ (выделение неразрывных блоков кода).

Алгоритм Косарайю (Kosaraju's Algorithm)

Существует несколько алгоритмов поиска SCC (например, алгоритм Тарьяна), но алгоритм Косарайю — самый понятный для изучения. Он использует два прохода DFS.

Идея: Если мы находимся в компоненте сильной связности $C$, то мы можем достичь любой вершины внутри $C$. Если мы выйдем из $C$ в другую компоненту $C'$, то вернуться назад в $C$ мы уже не сможем (иначе $C$ и $C'$ были бы одной компонентой).

Алгоритм использует понятие транспонированного графа $G^T$. Это тот же граф, но все стрелки перевернуты в обратную сторону.

Шаги алгоритма:

1. Первый проход (DFS): Запускаем DFS на исходном графе и запоминаем порядок выхода из вершин (как в топологической сортировке). Вершина, из которой мы вышли последней, условно является «корнем» зависимостей.
2. Транспонирование: Строим граф $G^T$, развернув все ребра.
3. Второй проход (DFS): Запускаем DFS на графе $G^T$, но перебираем вершины в порядке, обратном времени выхода (с конца списка, полученного на шаге 1). Каждый успешный запуск DFS на этом шаге соберет одну компоненту сильной связности.

Почему это работает? Во втором проходе мы начинаем с вершины, которая в топологическом смысле была «раньше всех» (или в корне конденсации). В транспонированном графе из неё нельзя уйти в другие компоненты (так как связи развернулись), поэтому DFS соберет только её «родную» компоненту.

Реализация на C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> adj, adj_rev;
vector<bool> visited;
vector<int> order, component;

// Первый DFS: заполняет order
void dfs1(int u) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) dfs1(v);
    }
    order.push_back(u);
}

// Второй DFS: ходит по adj_rev и собирает компоненту
void dfs2(int u) {
    visited[u] = true;
    component.push_back(u);
    for (int v : adj_rev[u]) {
        if (!visited[v]) dfs2(v);
    }
}

int main() {
    int n = 8;
    adj.resize(n);
    adj_rev.resize(n);

    // Ребра графа
    vector<pair<int, int>> edges = {
        {0, 1}, {1, 2}, {2, 0}, // Компонента {0, 1, 2}
        {2, 3},                 // Мост
        {3, 4}, {4, 5}, {5, 3}, // Компонента {3, 4, 5}
        {6, 7}, {6, 5},         // 6 и 7 сами по себе (если нет обратных)
    };

    for (auto e : edges) {
        adj[e.first].push_back(e.second);
        adj_rev[e.second].push_back(e.first); // Строим обратный граф сразу
    }

    // Шаг 1: Заполняем order
    visited.assign(n, false);
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) dfs1(i);
    }

    // Шаг 2: Обрабатываем в обратном порядке
    visited.assign(n, false);
    reverse(order.begin(), order.end()); // Разворачиваем, чтобы идти от последних к первым

    int sccCount = 0;
    for (int u : order) {
        if (!visited[u]) {
            // Нашли новую компоненту
            component.clear();
            dfs2(u);

            sccCount++;
            cout << "Компонента " << sccCount << ": ";
            for (int x : component) cout << x << " ";
            cout << endl;
        }
    }

    return 0;
}

Анализ сложности

Алгоритм Косарайю выполняет два полных обхода DFS и одно транспонирование графа.

$$T = O(V + E)$$

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

Заключение

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

Эти алгоритмы часто используются как подготовительный этап для более сложных задач. Например, многие задачи на графах можно решить проще, если сначала сжать компоненты сильной связности и работать с получившимся ациклическим графом (DAG).

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