|
|
| (не показаны 6 промежуточных версий 2 участников) |
| Строка 1: |
Строка 1: |
| | | | |
| − | 10 Графовых алгоритмов | + | [[10 Графовых алгоритмов]] |
| − | | + | |
| − | Графы превратились в невероятно сильное средство моделирования и получения данных из соцсетей, веб-страниц и ссылок, а также определения местоположения и маршрутов в GPS. Любой набор объектов, которые связаны друг с другом, можно сейчас представить с помощью графа.
| + | |
| − | | + | |
| − | В статье опишем 10 основных графовых алгоритмов, которые становятся очень полезными для анализа, а также области их применения.
| + | |
| − | | + | |
| − | Начнём с того, что приведём определение графа.
| + | |
| − | | + | |
| − | Что такое граф?
| + | |
| − | Граф состоит из конечного множества вершин (узлов) и набора рёбер, соединяющих эти вершины. Две вершины считаются смежными, если они соединены друг с другом одним и тем же ребром.
| + | |
| − | | + | |
| − | Порядок: число вершин в графе.
| + | |
| − | Размер: число рёбер в графе.
| + | |
| − | Степень вершины: число рёбер, инцидентных вершине.
| + | |
| − | Изолированная вершина: вершина, которая не связана ни с одной другой вершиной графа.
| + | |
| − | Петля: ребро, вершины которого совпадают.
| + | |
| − | Ориентированный граф: граф, в котором все рёбра имеют направление, определяющее начальную и конечную вершину.
| + | |
| − | Неориентированный граф: граф с рёбрами, которые не имеют направления.
| + | |
| − | Взвешенный граф: рёбра такого графа имеют определённый вес.
| + | |
| − | Невзвешенный граф: рёбра такого графа не имеют никаких весов.
| + | |
| − | | + | |
| − | 1. Поиск в ширину
| + | |
| − | | + | |
| − | Обход или поиск — это одна из фундаментальных операций, выполняемых на графах. Поиск в ширину начинается с определённой вершины, затем исследуются все её соседи на данной глубине и происходит переход к вершинам следующего уровня. В графах, в отличие от деревьев, могут быть циклы — пути, в которых первая и последняя вершины совпадают. Поэтому необходимо отслеживать посещённые алгоритмом вершины. При реализации алгоритма поиска в ширину используется структура данных «очередь».
| + | |
| − | | + | |
| − | .
| + | |
| − | | + | |
| − | Применяется для:
| + | |
| − | определения кратчайших путей и минимальных остовных деревьев;
| + | |
| − | индексации веб-страниц поисковыми ботами;
| + | |
| − | поиска в соцсетях;
| + | |
| − | нахождения доступных соседних узлов в одноуровневых сетях, таких как BitTorrent.
| + | |
| − | | + | |
| − | Поиск в глубину начинается с определённой вершины, затем уходит как можно дальше вдоль каждой ветви и возвращается обратно. Здесь тоже необходимо отслеживать посещённые алгоритмом вершины. Для того, чтобы стало возможным возвращение обратно, при реализации алгоритма поиска в глубину используется структура данных «стек».
| + | |
| − | | + | |
| − | Применяется:
| + | |
| − | для нахождения пути между двумя вершинами;
| + | |
| − | для обнаружения циклов на графе;
| + | |
| − | в топологической сортировке;
| + | |
| − | в головоломках с единственным решением (например, лабиринтах).
| + | |
| − | | + | |
| − | 3. Кратчайший путь
| + | |
| − | Кратчайший путь от одной вершины графа к другой — это путь, при котором сумма весов рёбер, его составляющих, должна быть минимальна.
| + | |
| − | | + | |
| − | На рисунке 4 показан кратчайший путь на графе от вершины 1 до вершины 6.
| + | |
| − | | + | |
| − | Алгоритмы нахождения кратчайшего пути:
| + | |
| − | Алгоритм Дейкстры.
| + | |
| − | Алгоритм Беллмана-Форда.
| + | |
| − | Применяются в:
| + | |
| − | картографических сервисах типа Google maps или Apple maps для прокладки маршрутов и определения местоположения;
| + | |
| − | сетях для решения проблемы минимальной задержки пути;
| + | |
| − | абстрактных автоматах для определения через переход между различными состояниями возможных вариантов достижения некоторого целевого состояния, например минимально возможного количества ходов, необходимого для победы в игре.
| + | |
| − | | + | |
| − | 4. Обнаружение циклов
| + | |
| − | | + | |
| − | Цикл — это путь, в котором первая и последняя вершины графа совпадают. То есть путь, начинающийся и завершающийся в одной и той же вершине, называется циклом. Обнаружение циклов — это процесс выявления таких циклов.
| + | |
| − | | + | |
| − | Алгоритмы обнаружения цикла:
| + | |
| − | Алгоритм Флойда.
| + | |
| − | Алгоритм Брента.
| + | |
| − | Применяются:
| + | |
| − | в распределённых алгоритмах, использующих сообщения;
| + | |
| − | для обработки крупных графов с использованием распределённой системы обработки в кластере;
| + | |
| − | для обнаружения взаимоблокировок в системах с параллельным выполнением;
| + | |
| − | в криптографических приложениях для выявления ключей сообщения, которые могут соответствовать одному и тому же зашифрованному значению.
| + | |
| − | | + | |
| − | 5. Минимальное остовное дерево
| + | |
| − | | + | |
| − | Минимальное остовное дерево — это подмножество рёбер графа, которое соединяет все вершины, имеющие минимальную сумму весов рёбер, и без циклов.
| + | |
| − | | + | |
| − | Алгоритмы поиска минимального остовного дерева:
| + | |
| − | Алгоритм Прима.
| + | |
| − | Алгоритм Крускала.
| + | |
| − | Применяются:
| + | |
| − | для создания деревьев для распределения данных в компьютерных сетях;
| + | |
| − | в кластерном анализе с использованием графов;
| + | |
| − | при сегментации изображений;
| + | |
| − | при социально-географическом районировании, когда смежные регионы объединяются.
| + | |
| − | | + | |
| − | 6. Сильно связные компоненты
| + | |
| − | | + | |
| − | Граф считается сильно связным, если все вершины в графе достижимы из всех остальных вершин.
| + | |
| − | | + | |
| − | Алгоритмы поиска сильных компонент связности:
| + | |
| − | Алгоритм Косараджу.
| + | |
| − | Алгоритм Тарьяна.
| + | |
| − | Применяются:
| + | |
| − | для вычисления декомпозиции Далмейджа-Мендельсона, которая представляет собой разделение вершин двудольного графа на подмножества;
| + | |
| − | в соцсетях для поиска групп сильно связанных между собой людей и выдачи рекомендаций на основе общих интересов.
| + | |
| − | | + | |
| − | 7. Топологическая сортировка
| + | |
| − | | + | |
| − | Топологическая сортировка графа — это такое линейное упорядочение его вершин, в котором для каждого направленного ребра, например (u, v), вершина u предшествует вершине v.
| + | |
| − | | + | |
| − | Алгоритмы поиска топологической сортировки:
| + | |
| − | Алгоритм Кана.
| + | |
| − | Алгоритм на основе поиска в глубину.
| + | |
| − | Применяются:
| + | |
| − | при планировании выполнения команд;
| + | |
| − | при сериализации данных;
| + | |
| − | определения порядка выполняемых при компиляции задач в Makefiles;
| + | |
| − | для разрешения зависимостей символов в компоновщиках.
| + | |
| − | | + | |
| − | 8. Раскраска графов
| + | |
| − | | + | |
| − | При раскраске графов элементам графа присваиваются цвета с учётом определённых условий. Раскраска вершин — наиболее часто используемый метод окраски графов. При этом вершины графа окрашиваются с использованием k цветов, а любым двум соседним вершинам должны соответствовать разные цвета. Другие методы окраски — раскраска рёбер и раскраска граней.
| + | |
| − | | + | |
| − | Хроматическое число графа — это наименьшее количество цветов, необходимых для окрашивания графа.
| + | |
| − | Алгоритмы с раскраской графов:
| + | |
| − | Алгоритмы, использующие поиск в ширину или поиск в глубину.
| + | |
| − | Жадная раскраска.
| + | |
| − | Применяются для:
| + | |
| − | составления расписаний;
| + | |
| − | назначения радиочастот мобильных сетей;
| + | |
| − | моделирования и решения головоломок типа судоку;
| + | |
| − | проверки того, является ли граф двудольным;
| + | |
| − | раскрашивания географических карт стран или штатов, на которых соседние страны или штаты имеют разные цвета.
| + | |
| − | | + | |
| − | 9. Максимальный поток
| + | |
| − | Можно смоделировать граф в виде сети потоков с весами рёбер в качестве пропускной способности этих потоков. В задаче максимального потока требуется найти такой путь потока, который может обеспечить максимально интенсивность потока.
| + | |
| − | | + | |
| − | Алгоритмы нахождения максимального потока:
| + | |
| − | Алгоритм Форда-Фулкерсона.
| + | |
| − | Алгоритм Эдмондса-Карпа.
| + | |
| − | Алгоритм Диница.
| + | |
| − | Применяются:
| + | |
| − | в авиакомпаниях для составления полётного расписания экипажей;
| + | |
| − | при сегментации изображений для определения фона и переднего плана изображения.
| + | |
| − | | + | |
| − | 10. Паросочетания
| + | |
| − | | + | |
| − | Паросочетание на графе — это набор рёбер, которые не имеют общих вершин (т.е. хотя бы двух рёбер, не имеющих общей вершины). Паросочетание называется максимальным, если оно содержит максимально возможное число рёбер, сочетающихся с как можно большим количеством вершин.
| + | |
| − | | + | |
| − | Алгоритмы нахождения паросочетаний:
| + | |
| − | Алгоритм Хопкрофта-Карпа.
| + | |
| − | Венгерский алгоритм.
| + | |
| − | Алгоритм сжатия цветков.
| + | |
| − | Применяются:
| + | |
| − | в подборе пары для жениха или невесты (задача о стабильных браках);
| + | |
| − | для определения вершинного покрытия;
| + | |
| − | в теории транспорта для решения задачи распределения ресурсов и оптимизации перевозок.
| + | |
| − | | + | |
| − | Примеры графов
| + | |
| − | <graphviz>
| + | |
| − | digraph G {
| + | |
| − | | + | |
| − | // rankdir = LR ;
| + | |
| − | rankdir = TB ;
| + | |
| − | | + | |
| − | "Это работает?" -> да ;
| + | |
| − | да -> "оно должно двигаться?" ;
| + | |
| − | да -> "оно не двигается?" ;
| + | |
| − | да -> "оно двигается?" ;
| + | |
| − | }
| + | |
| − | </graphviz>
| + | |
| − | | + | |
| | | | |
| | | | |
| | [[Категория:1419М1УП1]] | | [[Категория:1419М1УП1]] |
