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

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

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

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

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

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

!Пример простого неориентированного графа с 5 вершинами.

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

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

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

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

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

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

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

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

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

!Сравнение неориентированного и ориентированного графов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

!Визуализация структуры списков смежности.

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

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

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

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

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

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

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

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

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

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

Где — максимальное число ребер, а — число вершин.

| Характеристика | Матрица смежности | Списки смежности | | :--- | :--- | :--- | | Память | | | | Проверка смежности | | | | Перебор всех соседей | | | | Добавление вершины | Сложно ( при пересоздании) | Легко ( амортизировано) | | Удаление ребра | | |

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

Заключение

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

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

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

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

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

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

Концепция

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

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

!Визуализация порядка посещения вершин при поиске в глубину.

Алгоритм

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

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

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

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

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

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

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

Применение DFS

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

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

Концепция

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

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

!Распространение поиска в ширину по уровням удаленности от старта.

Алгоритм

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

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

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

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

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

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

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

Применение BFS

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

Где: * — текущее известное кратчайшее расстояние от старта до вершины . * — кратчайшее расстояние от старта до вершины . * — вес ребра между и .

Если неравенство выполняется, мы обновляем .

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

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

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

!Визуализация распространения алгоритма Дейкстры от стартовой вершины.

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

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

Сложность

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

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

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

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

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

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

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

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

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

Сложность

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

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

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

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

!Иллюстрация обновления матрицы расстояний через промежуточную вершину k.

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

Где: * — кратчайшее расстояние от до . * — расстояние от до промежуточной вершины . * — расстояние от до .

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

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

Сложность

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

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

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

| Алгоритм | Задача | Веса ребер | Сложность | Примечание | | :--- | :--- | :--- | :--- | :--- | | BFS | От одной ко всем | Только 1 (невзвешенный) | | Самый быстрый для простых графов | | Дейкстра | От одной ко всем | (неотрицательные) | | Стандарт де-факто для навигации | | Беллман-Форд | От одной ко всем | Любые | | Умеет находить отрицательные циклы | | Флойд-Уоршелл | Все ко всем | Любые (без отр. циклов) | | Прост в реализации, для малых графов |

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

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

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

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

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

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

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

!Исходный граф и выделенное в нем минимальное остовное дерево.

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

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

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

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

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

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

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

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

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

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

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

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

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

!Процесс добавления ребер в алгоритме Краскала.

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

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

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

Где — количество ребер в графе. Операции с DSU выполняются почти мгновенно. Так как , сложность можно также записать как .

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

!Иллюстрация топологической сортировки на примере порядка надевания одежды.

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

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

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

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

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

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

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

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

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

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

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

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

Определение

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

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

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

!Визуализация компонент сильной связности и графа конденсации.

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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