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

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

В этой статье мы вкратце опишем десять широко применяемых алгоритмов на графах и их приложения. Для начала давайте освежим свои знания о графах.

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

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

Рис. 1. Визуализация терминологии графов

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

• Путь – последовательность вершин, в которой каждая вершина соединена со следующей вершиной ребром. На Рис. 1 красными стрелками показан путь от вершины 1 к верешине 3 через вершину 4.
• Порядок – количество вершин графа.
• Размер – количество ребер графа.
• Связность (степень связности) вершины – количество ребер, исходящих из этой вершины.
• Изолированная вершина – вершина, не связанная с другими вершинами графа.
• Петля – ребро от вершины к этой же вершине.
• Ориентированный граф – граф, в котором все ребра имеют направление, указывающее, какая из вершин ребра является начальной, а какая – конечной.
• Неориентированный граф – граф, в котором у ребер нет направлений.
• Взвешенный граф – все ребра графа имеют веса.
• Невзвешенный граф – ребра графа не имеют весов.

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

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

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

Рис. 2. Анимация поиска в ширину

Этот рисунок изображает поиск в ширину на примере графа. Обратите внимание, как вершины обнаруживаются (желтый цвет) и посещаются (красный).

Приложения. Поиск в ширину используется:

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

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

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

Рис. 3. Анимация поиска в глубину

Рис. 3 изображает поиск в глубину на примере того же графа. Обратите внимание, как он доходит до конца и возвращается назад.

Приложения. Поиск в глубину используется:

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

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

Кратчайший путь от одной вершины графа до другой – это путь, имеющий минимальный суммарный вес входящих в него ребер. Следующий рисунок показывает минимальный путь от вершины 1 к вершине 6.

Рис. 4. Анимация процесса нахождения минимального пути

Алгоритмы:

1. Алгоритм Дейкстры поиска минимального пути.
2. Алгоритм Беллмана-Форда.

Приложения. Поиск кратчайшего пути используется:

• для построения маршрута в приложениях вроде Google Maps;
• при создании компьютерных сетей – чтобы обеспечить минимальную задержку;
• в абстрактных автоматах для определения оптимальной стратегии достижения некоторой цели через несколько промежуточных состояний (например, для подсчета, сколько нужно ходов для победы в игре).

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

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

Рис. 5. Цикл

Алгоритмы:

1. Алгоритм Флойда для обнаружения циклов.
2. Алгоритм Брента.

Приложения. Обнаружение циклов используется:

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

5. Минимальное покрывающее дерево

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

Рис. 6. Анимация процесса нахождения минимального покрывающего дерева

Алгоритмы:

1. Алгоритм Прима.
2. Алгоритм Краскала.

Приложения. Минимальные покрывающие деревья используются:

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

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

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

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

Алгоритмы:

1. Алгоритм Косараджу.
2. Алгоритм Тарьяна поиска сильно связанных компонентов.

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

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

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

Топологическая сортировка графа – это линейное упорядочение вершин графа таким образом, чтобы для каждого направленного ребра графа (u, v) вершина u в списке сортировки стояла перед v. На Рис. 8 изображен пример топологической сортировки вершин (1, 2, 3, 5, 4, 6, 7, 8). Показано, что вершина 5 должна следовать после вершин 2 и 3, а вершина 6 – после вершин 4 и 5.

Рис. 8. Топологическая сортировка вершин графа

Алгоритмы:

1. Алгоритм Кана.
2. Алгоритм, основанный на поиске в глубину.

Приложения. Топологическая сортировка используется:

• для выработки расписания инструкций;
• при сериализации данных;
• для определения порядка выполнения задач компиляции;
• для разрешения зависимостей символов при сборке (linking).

8. Раскраска графа

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

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

Рис. 9. Раскраска вершин графа

Алгоритмы:

1. Алгоритмы, использующие поиск в ширину или в глубину.
2. «Жадная» раскраска.

Приложения. Раскраска графов используется:

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

9. Задача о максимальном потоке

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

На рисунке показан пример определения максимального потока сети и нахождения итогового значения потока.

Рис. 10. Нахождение максимального потока

Алгоритмы:

1. Алгоритм Форда-Фалкерсона.
2. Алгоритм Эдмондса-Карпа.
3. Алгоритм Диница.

Приложения. Задача о максимальном потоке используется:

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

10. Соответствия

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

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

Рис. 11. Поиск соответствия в двухчастном графе

Алгоритмы:

1. Алгоритм Хопкрофта-Карпа.
2. Венгерский алгоритм.
3. Алгоритм сжатия цветков.

Приложения. Поиск соответствий используется:

• для определения соответствий вершин;
• в логистике для решения задач распределения ресурсов и оптимизации в пути.

Заключение

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

Если вы знакомы с Python, вы можете посмотреть, как алгоритмы на графах реализованы в модулях networkx и igraph.