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

1. Введение в графы: терминология и способы представления (матрица смежности, списки смежности)

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

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

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

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

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

* Вершины (Vertices/Nodes) — это те самые «точки» или объекты. Например, города на карте или пользователи в социальной сети. * Рёбра (Edges) — это связи между вершинами. Например, дороги между городами или дружба между пользователями.

!Схематичное изображение графа с вершинами и рёбрами.

Формальное определение

С точки зрения математики, граф определяется как пара множеств:

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

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

Основные виды графов

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

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

* Неориентированный граф: Связь работает в обе стороны. Если существует ребро между вершиной и вершиной , то можно пройти как от к , так и от к . Пример:* Рукопожатие или дружба в Facebook (если я у тебя в друзьях, то и ты у меня). * Ориентированный граф (орграф): Рёбра имеют направление (стрелки). Ребро позволяет пройти от к , но не обязательно обратно. Пример:* Подписка в Instagram (я подписан на Илона Маска, но он на меня — нет) или одностороннее движение на дороге.

2. Взвешенные и невзвешенные графы

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

3. Связность

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

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

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

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

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

Пусть у нас есть вершины, пронумерованные от до . Элемент матрицы matrix[i][j] хранит информацию о ребре между вершиной и вершиной .

* Для невзвешенного графа: matrix[i][j] = 1, если ребро есть, и 0, если его нет. * Для взвешенного графа: matrix[i][j] = weight, где weight — вес ребра.

!Иллюстрация соответствия графа и его матрицы смежности.

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

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

* Память: Где — количество вершин. Мы всегда выделяем память под полный квадрат, даже если рёбер почти нет. * Проверка связи: Мы можем мгновенно узнать, есть ли ребро между и , просто обратившись к ячейке массива. * Перебор соседей: Чтобы найти всех соседей вершины, нужно пройтись по всей строке матрицы.

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

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

В C++ это обычно реализуется как массив (или вектор) векторов: vector<vector<int>>.

* adj[0] содержит список соседей вершины 0. * adj[1] содержит список соседей вершины 1. * И так далее.

!Визуализация списков смежности: массив, где каждый элемент ссылается на список соседей.

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

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

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

Сравнение: что выбрать?

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

> «Если у вас 10 000 городов и всего 20 000 дорог, матрица смежности займет 100 000 000 ячеек (около 400 МБ int-ов), большинство из которых будут нулями. Списки смежности займут лишь память под 20 000 связей. Разница колоссальна.»

Итог

Мы познакомились с базовой терминологией теории графов и двумя основными способами их реализации в C++.

Граф — это множество вершин и рёбер .

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

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

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

2. Базовые алгоритмы обхода: поиск в ширину (BFS) и поиск в глубину (DFS)

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

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

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

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

Концепция: круги на воде

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

Именно так работает BFS. Мы начинаем с одной стартовой вершины и сначала посещаем всех её непосредственных соседей. Только после того, как мы посетили всех соседей на расстоянии 1 шага, мы переходим к соседям соседей (расстояние 2 шага).

!Визуализация поиска в ширину: вершины посещаются слоями, удаляясь от старта.

Структура данных: Очередь (Queue)

Чтобы реализовать этот принцип «сначала близкие, потом дальние», нам нужна структура данных, работающая по принципу FIFO (First In, First Out — «первым вошёл, первым вышел»). Это очередь.

Алгоритм работает следующим образом:

Помещаем стартовую вершину в очередь и помечаем её как посещённую.

Пока очередь не пуста:

* Извлекаем вершину из начала очереди (назовём её current). * Смотрим всех соседей current. * Если сосед ещё не был посещён, добавляем его в конец очереди и помечаем как посещённого.

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

Для реализации мы будем использовать std::queue и списки смежности (adjList), которые мы разобрали в прошлой лекции.

Ключевое свойство BFS

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

Это происходит именно из-за слоистой структуры обхода. Мы не начнем рассматривать пути длиной 3, пока не проверим все пути длиной 2.

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

Концепция: лабиринт и нить Ариадны

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

Стратегия DFS: «Иди вглубь, пока можешь».

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

Структура данных: Стек (Stack) или Рекурсия

Для DFS используется принцип LIFO (Last In, First Out — «последним вошёл, первым вышел»). Последняя найденная вершина обрабатывается первой, чтобы углубиться дальше.

Это можно реализовать двумя способами:

Явно используя структуру std::stack.

Используя рекурсию (системный стек вызовов).

Второй способ (рекурсия) используется чаще из-за краткости кода.

Реализация DFS на C++ (Рекурсия)

Применение DFS

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

Анализ сложности алгоритмов

И BFS, и DFS посещают каждую вершину и просматривают каждое ребро ровно один раз (в случае списков смежности).

Временная сложность для обоих алгоритмов выражается формулой:

Где: * — количество вершин (Vertices) в графе. * — количество рёбер (Edges) в графе.

Почему так?

Каждая вершина добавляется в очередь (BFS) или стек (DFS) и удаляется оттуда ровно один раз. Это дает вклад .

Для каждой вершины мы пробегаем по списку её соседей. Сумма длин всех списков смежности в ориентированном графе равна , а в неориентированном — . Это дает вклад .

Суммарно получаем линейную зависимость от размера графа: .

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

Итог

Мы изучили два «двигателя», которые позволяют перемещаться по графам:

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

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

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

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

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

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

Представьте, что вы строите маршрут в навигаторе. Дорога через центр города короче по расстоянию, но из-за пробок она займет час. Объездная дорога длиннее, но по ней можно промчаться за 20 минут. В терминах графов это означает, что у рёбер есть вес (стоимость, время, расстояние).

Сегодня мы разберем «большую тройку» алгоритмов для поиска кратчайших путей во взвешенных графах: Дейкстры, Беллмана-Форда и Флойда-Уоршелла. Каждый из них имеет свою нишу и свои ограничения.

Постановка задачи и понятие релаксации

Наша цель — найти путь от стартовой вершины до всех остальных вершин (или конкретной вершины ), чтобы сумма весов рёбер в этом пути была минимальной.

Ключевым понятием для всех сегодняшних алгоритмов является релаксация ребра.

Пусть — это текущее известное кратчайшее расстояние от старта до вершины . Изначально расстояние до старта равно 0, а до всех остальных вершин — бесконечность ().

Релаксация ребра с весом — это попытка улучшить путь до вершины , пройдя через вершину . Условие релаксации выглядит так:

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

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

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

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

Ограничение: Веса рёбер должны быть неотрицательными ().

Как это работает?

Создаем массив расстояний dist, заполненный бесконечностью. dist[start] = 0.

Используем очередь с приоритетом (Priority Queue), чтобы всегда быстро извлекать вершину с минимальным текущим расстоянием.

Пока очередь не пуста:

* Достаем вершину с наименьшим dist[u]. * Проходим по всем соседям вершины . * Пытаемся релаксировать ребро . Если путь улучшился, обновляем dist[v] и добавляем пару в очередь.

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

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

Для эффективной работы нам понадобится std::priority_queue. Обратите внимание: стандартная очередь в C++ является max-heap (хранит максимум на вершине), а нам нужен минимум. Поэтому мы используем компаратор greater.

Сложность

При использовании очереди с приоритетом сложность составляет:

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

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

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

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

Как это работает?

Идея проста, но брутальна: мы просто пытаемся релаксировать все рёбра графа много раз.

Инициализируем dist бесконечностью, dist[start] = 0.

Повторяем цикл раз:

* Проходим по каждому ребру в графе. * Пытаемся его релаксировать.

После итераций запускаем еще одну проверку. Если какое-то ребро все еще можно релаксировать, значит, в графе есть отрицательный цикл.

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

Здесь удобнее хранить граф просто как список всех рёбер, а не списки смежности.

Сложность

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

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

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

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

Как это работает?

Мы используем матрицу смежности d[V][V]. Изначально d[i][j] равно весу ребра между и (или бесконечности, если ребра нет).

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

Формула перехода:

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

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

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

Это, пожалуй, самый короткий в реализации алгоритм на графах — всего три вложенных цикла.

Сложность

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

Сводная таблица: что выбрать?

> «Не стреляйте из пушки по воробьям: если граф невзвешенный — берите BFS. Если веса положительные — Дейкстру. И только если всё плохо — доставайте тяжелую артиллерию в виде Беллмана-Форда.»

В следующей статье мы рассмотрим Минимальные остовные деревья (MST) и алгоритмы Прима и Краскала, которые помогут нам соединить все города дорогами с минимальными затратами.

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

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

В прошлой статье мы научились находить кратчайшие пути между двумя конкретными точками (или от одной точки ко всем остальным). Мы использовали алгоритмы Дейкстры и Беллмана-Форда, чтобы навигатор мог проложить оптимальный маршрут из дома на работу.

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

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

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

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

Дерево — это связный граф без циклов. В дереве из вершин всегда ровно рёбер.

Остовное дерево (Spanning Tree) графа — это подграф, который является деревом и содержит все вершины исходного графа.

Минимальное остовное дерево (MST) — это такое остовное дерево, у которого сумма весов всех рёбер минимальна среди всех возможных остовных деревьев этого графа.

!Иллюстрация графа и выделенного в нем минимального остовного дерева (MST).

Формально, если у нас есть граф , мы ищем такое подмножество рёбер , чтобы граф был связным и сумма весов была минимальной:

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

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

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

Логика работы

Выбираем произвольную стартовую вершину и добавляем её в наше «растущее дерево».

Рассматриваем все рёбра, которые соединяют вершины внутри дерева с вершинами снаружи.

Из этих рёбер выбираем то, у которого минимальный вес.

Добавляем это ребро и новую вершину в дерево.

Повторяем шаги 2-4, пока все вершины не окажутся в дереве.

!Визуализация процесса роста MST в алгоритме Прима.

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

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

Сложность

Сложность алгоритма Прима с использованием бинарной кучи (priority queue) составляет:

Где: * — количество рёбер. * — количество вершин. * — логарифм.

Это делает его отличным выбором для плотных графов (где много рёбер).

---

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

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

Представьте, что у нас есть отдельных элементов. Нам нужно уметь делать две вещи:

Union: Объединять два множества в одно.

Find: Проверять, находятся ли два элемента в одном и том же множестве.

В алгоритме Краскала мы будем использовать DSU, чтобы проверять, образует ли добавление ребра цикл. Если концы ребра уже лежат в одном множестве — значит, путь между ними уже есть, и добавление ребра создаст цикл.

Оптимизации DSU

Наивная реализация медленная. Мы применим две эвристики:

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

Объединение по рангу (Union by Rank): При объединении двух деревьев мы всегда подвешиваем меньшее дерево к большему, чтобы высота общей структуры росла медленно.

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

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

---

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

Алгоритм Краскала использует другой подход. Если Прим растит одно дерево, то Краскал строит «лес», постепенно объединяя деревья друг с другом.

Логика работы

Создаем список всех рёбер графа.

Сортируем все рёбра по возрастанию веса.

Изначально каждая вершина — это отдельное дерево (используем DSU).

Перебираем рёбра от самых дешевых к дорогим:

* Пусть текущее ребро соединяет вершины и . * Проверяем с помощью DSU: лежат ли и в разных множествах? * Если да (они в разных компонентах), то добавляем ребро в MST и объединяем множества (). * Если нет (они уже связаны), пропускаем ребро, чтобы не создать цикл.

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

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

Сложность

Основное время занимает сортировка рёбер. Операции DSU выполняются почти мгновенно.

Где: * — количество рёбер. * — логарифм от количества рёбер (сложность сортировки).

Так как , то , поэтому сложность часто записывают как .

Прим или Краскал: что выбрать?

Оба алгоритма решают одну и ту же задачу и имеют схожую асимптотику. Однако есть нюансы:

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

Итог

Сегодня мы решили задачу минимизации затрат на соединение всех вершин графа.

MST — это скелет графа с минимальным весом.

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

Алгоритм Краскала сортирует все рёбра и добавляет их, если они не создают циклов, используя DSU.

DSU — гениальная структура для быстрого отслеживания связности элементов.

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

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

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

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

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

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

Топологическая сортировка

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

Простыми словами: это выстраивание всех задач в линейку так, чтобы все зависимости шли слева направо. Ни одна стрелка не должна указывать назад.

!Пример графа зависимостей одежды и его топологическая сортировка.

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

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

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

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

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

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

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

Запускаем DFS для всех непосещенных вершин.

В самом конце функции dfs (когда обработали всех соседей) добавляем текущую вершину в специальный список.

После завершения обхода всего графа переворачиваем (reverse) полученный список.

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

Сложность

Алгоритм является обычной модификацией DFS, поэтому его временная сложность такая же:

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

Поиск циклов в ориентированном графе

Как мы уже сказали, топологическая сортировка не работает, если есть цикл. Но как узнать, есть ли он? Обычный массив visited (был/не был) здесь не поможет так эффективно, как в неориентированных графах.

Нам понадобится раскраска вершин в три цвета:

Белый (0): Вершина еще не посещена.

Серый (1): Мы вошли в вершину, но еще не вышли из неё (она сейчас в стеке рекурсии).

Черный (2): Мы полностью обработали вершину и вышли из неё.

Логика обнаружения цикла

Цикл существует тогда и только тогда, когда в процессе DFS мы пытаемся пойти в вершину, которая сейчас Серая. Это означает, что мы нашли «обратное ребро» (back edge) — путь, ведущий к предку в дереве обхода.

Если мы встречаем Черную вершину — это не цикл, это просто уже изученная ветка.

!Иллюстрация поиска цикла с помощью трех цветов.

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

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

В неориентированных графах все просто: если есть путь от к , то есть и от к . Это называется связностью.

В ориентированных графах это не так. Вы можете доехать на машине от дома до магазина, но вернуться тем же путем не сможете из-за одностороннего движения.

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

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

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

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

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

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

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

Транспонирование: Создаем обратный граф , где все ребра заменены на .

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

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

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

Сложность

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

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

Итог

Сегодня мы разобрали важные свойства ориентированных графов:

Топологическая сортировка позволяет упорядочить задачи с зависимостями. Она работает только для ациклических графов (DAG).

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

Компоненты сильной связности — это «острова» внутри графа, где можно добраться от любой точки до любой. Алгоритм Косарайю находит их за два прохода DFS.

Эти алгоритмы часто встречаются в задачах на построение систем сборки, анализ ссылок в интернете (PageRank) и оптимизацию кода.

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