10 Графовых алгоритмов

Графы превратились в невероятно сильное средство моделирования и получения данных из соцсетей, веб-страниц и ссылок, а также определения местоположения и маршрутов в GPS. Любой набор объектов, которые связаны друг с другом, можно сейчас представить с помощью графа.

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

Начнём с того, что приведём определение графа.

Что такое граф? Граф состоит из конечного множества вершин (узлов) и набора рёбер, соединяющих эти вершины. Две вершины считаются смежными, если они соединены друг с другом одним и тем же ребром.

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

• Порядок: число вершин в графе.
• Размер: число рёбер в графе.
• Степень вершины: число рёбер, инцидентных вершине.
• Изолированная вершина: вершина, которая не связана ни с одной другой вершиной графа.
• Петля: ребро, вершины которого совпадают.
• Ориентированный граф: граф, в котором все рёбра имеют направление, определяющее начальную и конечную вершину.
• Неориентированный граф: граф с рёбрами, которые не имеют направления.
• Взвешенный граф: рёбра такого графа имеют определённый вес.
• Невзвешенный граф: рёбра такого графа не имеют никаких весов.

Примеры графов

Поиск в ширину

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

Применяется для:

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

Поиск в глубину

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

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

Кратчайший путь

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

Алгоритмы нахождения кратчайшего пути: Алгоритм Дейкстры. Алгоритм Беллмана-Форда. Применяются в: картографических сервисах типа Google maps или Apple maps для прокладки маршрутов и определения местоположения; сетях для решения проблемы минимальной задержки пути; абстрактных автоматах для определения через переход между различными состояниями возможных вариантов достижения некоторого целевого состояния, например минимально возможного количества ходов, необходимого для победы в игре.

Обнаружение циклов

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

Алгоритмы обнаружения цикла: Алгоритм Флойда. Алгоритм Брента. Применяются: в распределённых алгоритмах, использующих сообщения; для обработки крупных графов с использованием распределённой системы обработки в кластере; для обнаружения взаимоблокировок в системах с параллельным выполнением; в криптографических приложениях для выявления ключей сообщения, которые могут соответствовать одному и тому же зашифрованному значению.

               5. Минимальное остовное дерево

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

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

      6. Сильно связные компоненты

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

Алгоритмы поиска сильных компонент связности: Алгоритм Косараджу. Алгоритм Тарьяна. Применяются: для вычисления декомпозиции Далмейджа-Мендельсона, которая представляет собой разделение вершин двудольного графа на подмножества; в соцсетях для поиска групп сильно связанных между собой людей и выдачи рекомендаций на основе общих интересов.

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

Алгоритмы поиска топологической сортировки: Алгоритм Кана. Алгоритм на основе поиска в глубину. Применяются: при планировании выполнения команд; при сериализации данных; определения порядка выполняемых при компиляции задач в Makefiles; для разрешения зависимостей символов в компоновщиках. 8. Раскраска графов При раскраске графов элементам графа присваиваются цвета с учётом определённых условий. Раскраска вершин  —  наиболее часто используемый метод окраски графов. При этом вершины графа окрашиваются с использованием k цветов, а любым двум соседним вершинам должны соответствовать разные цвета. Другие методы окраски  —  раскраска рёбер и раскраска граней.

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

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

      9. Максимальный поток

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

Алгоритмы нахождения максимального потока: Алгоритм Форда-Фулкерсона. Алгоритм Эдмондса-Карпа. Алгоритм Диница. Применяются: в авиакомпаниях для составления полётного расписания экипажей; при сегментации изображений для определения фона и переднего плана изображения.

                 10. Паросочетания

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

Алгоритмы нахождения паросочетаний: Алгоритм Хопкрофта-Карпа. Венгерский алгоритм. Алгоритм сжатия цветков. Применяются: в подборе пары для жениха или невесты (задача о стабильных браках); для определения вершинного покрытия; в теории транспорта для решения задачи распределения ресурсов и оптимизации перевозок.