Графы. Разные виды представления графов. Пути в лабиринте. Выход из лабиринта (поиск в глубину). Кратчайший путь (поиск в ширину). Алгоритмы на графах. Алгоритмы Дейкстры и Флойда. Примеры задач. Алгоритмы на графах: Флойда, Дейкстры, Краскала
Метод обхода графа при котором в первую очередь переход делается из последней посещённой вершины (вершины хранятся в стеке). Обход в глубину получается естественным образом при рекурсивном обходе графа.
Порядок обхода вершин при поиске в глубину
Поиск в ширину — ПВШ (Breadth First Search — BFS)
Метод обхода графа при котором в первую очередь переход делается из первой вершины, из которой мы ещё не ходили (вершины хранятся в очереди). Обход в глубину получается естественным образов при рекурсивном обходе графа.
Порядок обхода вершин при поиске в ширину
Поиск кратчайших путей в графах (объединение разделов по Дейкстре и Флойду)
Алгоритм Дейкстры
Алгоритм Дейкстры (Dijkstra’s algorithm) — алгоритм на графах, находящий кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса (без рёбер с отрицательной "длиной").
Примеры формулировки задачи
Вариант 1. Дана сеть автомобильных дорог, соединяющих города. Некоторые дороги односторонние. Найти кратчайшие пути от заданного города до каждого другого города (если двигаться можно только по дорогам).
Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.
Идея алгоритма Дейкстры
Алгоритм состоит и 2 повторяющихся шагов:
- Добавление новой вершины ("Расти" — GROW)
- "Релаксация", т.е. пересчёт расстояний до других вершин с учётом добавленной вершины (RELAX).
Более подробное описание:
Обозначения:
Граф $G = (V,E)$, где $V$ — вершины, $E$ — рёбра.
$v_0$ — начальная вершина (от которой мы ищем кратчайшее растояние до всех остальных)
$R_i$ — известное нам расстояние от вершиеы $v_0$ до вершины $i$-ой.
$D$ — множество вершин до которых мы знаем кратчайшее расстояние от $v_0$.
Граф $G=(V,E)$, где $V$ — вершины, $E$ — рёбра.
$v_0$ — начальная вершина
$R_i$ — кратчайщее расстояние от $v_0$ до $i$-ой вершины
Инициализация алгоритма:
$D = \<\>$ — пустое множество.
$R_
$v = v_0$ — расти будем от вершины $v$.
Повторять (общий шаг алгоритма)
$GROW(V/D,v)$ — Добавляем вершину $v$ из множества $V/D$ в множество $D$.
$RELAX(V/D,v)$ — пробегаем достижимые из $v$ вершины до которых мы ещё не знаем кратчайшее расстояние и обновляем расстояния $R_i$ от вершины $v$.
$v$ — вершина с минимальным $R$ из множества $V/D$.
Алгоритм
Каждой вершине v из V сопоставим значение a[v] — минимальное известное расстояние от этой вершины до начальной s. Алгоритм работает пошагово — на каждом шаге он рассматривает одну вершину и пытается улучшить текущее расстояние до этой вершины. Работа алгоритма завершается, когда все вершины посещены, либо когда вычислены расстояния до всех вершин, достижимых из начальной.
Инициализация. Значение a[s] самой начальной вершины полагается равным 0, значение остальных вершин — бесконечности (в программировании это реализуется присваиванием большого, к примеру, максимально возможного для данного типа, значения). Это отражает то, что расстояния от s до других вершин пока неизвестны.
Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина v, имеющая минимальное расстояние от начальной вершины s и добавляется в список посещенных. Эта вершина находится, используя перебор всех непосещенных вершин. При этом суммируется расстояние от старта до одной из посещенных вершин u до непосещенной v. Для первого шага s — единственная посещенная вершина с расстоянием от старта (то есть от себя самой), равным 0.
Алгоритм Флойда
Алгоритм Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом.
Пусть вершины графа пронумерованы от 1 до $n$ и введено обозначение $d_
Существует два варианта значения $d_^
- Кратчайший путь между $i,\;j$ не проходит через вершину $k$, тогда $d_^
=d_^ $ - Существует более короткий путь между $i,\;j$, проходящий через $k$, тогда он сначала идёт от $i$ до $k$, а потом от $k$ до $j$. В этом случае, очевидно, $d_^
=d_^ + d_ ^ $
Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений.
Тогда рекуррентная формула для $d_^k$ имеет вид:
$d_^0$ — длина ребра $(i,\;j)$
Алгоритм Флойда — Уоршелла последовательно вычисляет все значения $d_^
Алгоритм Прима
Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году.
Построение начинается с дерева, включающего в себя одну (произвольную) вершину. В течение работы алгоритма дерево разрастается, пока не охватит все вершины исходного графа. На каждом шаге алгоритма к текущему дереву присоединяется самое лёгкое из рёбер, соединяющих вершину из построенного дерева, и вершину не из дерева.
Вход: Связный неориентированный граф $G(V,E)$
Выход: Множество $T$ рёбер минимального остовного дерева
Задача №15. Графы. Поиск количества путей.
В этой задаче требуется подсчитать количество путей, ведущих из одной вершины графа в другую. Обычно задачу решают преобразованием графа в дерево. Однако, при сложной структуре графа такое решение становится очень трудоемким. Велика вероятность ошибки.
Рассмотрим простой и эффективный способ решения.
В этой задаче мы имеем дело с ориентированным графом (графом, у которого ребра имеют направление). Т.е. ребра имеют вид стрелок. Две вершины, соединенные напрямую стрелкой, называются смежными. Вершина, из которой выходит стрелка, называется предком, а вершина, в которую входит стрелка – потомком.
Несложно понять, что количество путей, которыми можно попасть в некоторую вершину, равно сумме количеств путей предков этой вершины.
Пример:
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
Решение:
Каждой вершине, начиная с начальной (A), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один – вершина A).
У вершины Д предками являются А и Б, значит индекс вершины Д равен 1+1=2.
Очевидно, что мы можем посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Например, мы не можем посчитать индекс Г, пока не посчитан индекс В. Двигаясь последовательно, мы рассчитаем индексы всех вершин.
Индекс вершины Ж и будет ответом задачи.
Ответ: 11
Благодарим за то, что пользуйтесь нашими статьями. Информация на странице «Задача №15. Графы. Поиск количества путей.» подготовлена нашими редакторами специально, чтобы помочь вам в освоении предмета и подготовке к экзаменам. Чтобы успешно сдать необходимые и поступить в высшее учебное заведение или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий. Также вы можете воспользоваться другими материалами из разделов нашего сайта.
10 Графовых алгоритмов
Графы превратились в невероятно сильное средство моделирования и получения данных из соцсетей, веб-страниц и ссылок, а также определения местоположения и маршрутов в GPS. Любой набор объектов, которые связаны друг с другом, можно сейчас представить с помощью графа.
В статье опишем 10 основных графовых алгоритмов, которые становятся очень полезными для анализа, а также области их применения.
Начнём с того, что приведём определение графа.
Что такое граф?
Граф состоит из конечного множества вершин (узлов) и набора рёбер, соединяющих эти вершины. Две вершины считаются смежными, если они соединены друг с другом одним и тем же ребром.
Ниже приведён ряд базовых понятий, относящихся к графам. Они проиллюстрированы примерами на рисунке 1.
- Порядок: число вершин в графе.
- Размер: число рёбер в графе.
- Степень вершины: число рёбер, инцидентных вершине.
- Изолированная вершина: вершина, которая не связана ни с одной другой вершиной графа.
- Петля: ребро, вершины которого совпадают.
- Ориентированный граф: граф, в котором все рёбра имеют направление, определяющее начальную и конечную вершину.
- Неориентированный граф: граф с рёбрами, которые не имеют направления.
- Взвешенный граф: рёбра такого графа имеют определённый вес.
- Невзвешенный граф: рёбра такого графа не имеют никаких весов.
1. Поиск в ширину
Обход или поиск — это одна из фундаментальных операций, выполняемых на графах. Поиск в ширину начинается с определённой вершины, затем исследуются все её соседи на данной глубине и происходит переход к вершинам следующего уровня. В графах, в отличие от деревьев, могут быть циклы — пути, в которых первая и последняя вершины совпадают. Поэтому необходимо отслеживать посещённые алгоритмом вершины. При реализации алгоритма поиска в ширину используется структура данных «очередь».
На рисунке 2 показан пример того, как выглядит поиск в ширину на графе. Жёлтым цветом помечаются обнаруженные вершины, красным — посещённые.
Применяется для:
- определения кратчайших путей и минимальных остовных деревьев;
- индексации веб-страниц поисковыми ботами;
- поиска в соцсетях;
- нахождения доступных соседних узлов в одноуровневых сетях, таких как BitTorrent.
2. Поиск в глубину
Поиск в глубину начинается с определённой вершины, затем уходит как можно дальше вдоль каждой ветви и возвращается обратно. Здесь тоже необходимо отслеживать посещённые алгоритмом вершины. Для того, чтобы стало возможным возвращение обратно, при реализации алгоритма поиска в глубину используется структура данных «стек».
На рисунке 3 показан пример того, как выглядит поиск в глубину на том же графе, который использован на рисунке 2. Граф обходится на всю глубину каждой ветви с возвращением обратно.
Применяется:
- для нахождения пути между двумя вершинами;
- для обнаружения циклов на графе;
- в топологической сортировке;
- в головоломках с единственным решением (например, лабиринтах).
3. Кратчайший путь
Кратчайший путь от одной вершины графа к другой — это путь, при котором сумма весов рёбер, его составляющих, должна быть минимальна.
На рисунке 4 показан кратчайший путь на графе от вершины 1 до вершины 6.
Алгоритмы нахождения кратчайшего пути:
- Алгоритм Дейкстры.
- Алгоритм Беллмана-Форда.
Применяются в:
- картографических сервисах типа Google maps или Apple maps для прокладки маршрутов и определения местоположения;
- сетях для решения проблемы минимальной задержки пути;
- абстрактных автоматах для определения через переход между различными состояниями возможных вариантов достижения некоторого целевого состояния, например минимально возможного количества ходов, необходимого для победы в игре.
4. Обнаружение циклов
Цикл — это путь, в котором первая и последняя вершины графа совпадают. То есть путь, начинающийся и завершающийся в одной и той же вершине, называется циклом. Обнаружение циклов — это процесс выявления таких циклов. На рисунке 5 показано, как происходит обнаружение цикла.
Алгоритмы обнаружения цикла:
- Алгоритм Флойда.
- Алгоритм Брента.
Применяются:
- в распределённых алгоритмах, использующих сообщения;
- для обработки крупных графов с использованием распределённой системы обработки в кластере;
- для обнаружения взаимоблокировок в системах с параллельным выполнением;
- в криптографических приложениях для выявления ключей сообщения, которые могут соответствовать одному и тому же зашифрованному значению.
5. Минимальное остовное дерево
Минимальное остовное дерево — это подмножество рёбер графа, которое соединяет все вершины, имеющие минимальную сумму весов рёбер, и без циклов.
На рисунке 6 показан процесс получения минимального остовного дерева.
Алгоритмы поиска минимального остовного дерева:
- Алгоритм Прима.
- Алгоритм Крускала.
Применяются:
- для создания деревьев для распределения данных в компьютерных сетях;
- в кластерном анализе с использованием графов;
- при сегментации изображений;
- при социально-географическом районировании, когда смежные регионы объединяются.
6. Сильно связные компоненты
Граф считается сильно связным, если все вершины в графе достижимы из всех остальных вершин.
На рисунке 7 показан пример того, как выглядит граф с тремя сильно связными компонентами, вершины которых окрашены в красный, зелёный и жёлтый цвета.
Алгоритмы поиска сильных компонент связности:
- Алгоритм Косараджу.
- Алгоритм Тарьяна.
Применяются:
- для вычисления декомпозиции Далмейджа-Мендельсона, которая представляет собой разделение вершин двудольного графа на подмножества;
- в соцсетях для поиска групп сильно связанных между собой людей и выдачи рекомендаций на основе общих интересов.
7. Топологическая сортировка
Топологическая сортировка графа — это такое линейное упорядочение его вершин, в котором для каждого направленного ребра, например (u, v), вершина u предшествует вершине v.
На рисунке 8 показан пример топологического упорядочения вершин, согласно которому вершина 5 должна следовать за вершинами 2 и 3, а вершина 6 — за вершинами 4 и 5.
Алгоритмы поиска топологической сортировки:
- Алгоритм Кана.
- Алгоритм на основе поиска в глубину.
Применяются:
- при планировании выполнения команд;
- при сериализации данных;
- определения порядка выполняемых при компиляции задач в Makefiles;
- для разрешения зависимостей символов в компоновщиках.
8. Раскраска графов
При раскраске графов элементам графа присваиваются цвета с учётом определённых условий. Раскраска вершин — наиболее часто используемый метод окраски графов. При этом вершины графа окрашиваются с использованием k цветов, а любым двум соседним вершинам должны соответствовать разные цвета. Другие методы окраски — раскраска рёбер и раскраска граней.
Хроматическое число графа — это наименьшее количество цветов, необходимых для окрашивания графа.
На рисунке 9 показан пример того, как выглядит раскраска вершин графа с использованием 4-х цветов.
Алгоритмы с раскраской графов:
- Алгоритмы, использующие поиск в ширину или поиск в глубину.
- Жадная раскраска.
Применяются для:
- составления расписаний;
- назначения радиочастот мобильных сетей;
- моделирования и решения головоломок типа судоку;
- проверки того, является ли граф двудольным;
- раскрашивания географических карт стран или штатов, на которых соседние страны или штаты имеют разные цвета.
9. Максимальный поток
Можно смоделировать граф в виде сети потоков с весами рёбер в качестве пропускной способности этих потоков. В задаче максимального потока требуется найти такой путь потока, который может обеспечить максимально интенсивность потока.
На рисунке 10 показан пример того, как выглядит нахождение максимального потока сети и определение конечного значения потока.
Алгоритмы нахождения максимального потока:
- Алгоритм Форда-Фулкерсона.
- Алгоритм Эдмондса-Карпа.
- Алгоритм Диница.
Применяются:
- в авиакомпаниях для составления полётного расписания экипажей;
- при сегментации изображений для определения фона и переднего плана изображения.
10. Паросочетания
Паросочетание на графе — это набор рёбер, которые не имеют общих вершин (т.е. хотя бы двух рёбер, не имеющих общей вершины). Паросочетание называется максимальным, если оно содержит максимально возможное число рёбер, сочетающихся с как можно большим количеством вершин.
На рисунке 11 показано получение полного паросочетания в двудольном графе с двумя наборами вершин, обозначенных оранжевым и синим цветами.
Алгоритмы нахождения паросочетаний:
- Алгоритм Хопкрофта-Карпа.
- Венгерский алгоритм.
- Алгоритм сжатия цветков.
Применяются:
- в подборе пары для жениха или невесты (задача о стабильных браках);
- для определения вершинного покрытия;
- в теории транспорта для решения задачи распределения ресурсов и оптимизации перевозок.
Заключение
Надеюсь, статья была полезной и в простой и краткой форме познакомила вас с графовыми алгоритмами. ��
А с реализациями графовых алгоритмов можно ознакомиться в модулях на Python networkx и igraph.
9 задание ОГЭ информатика
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К, проходящих через город В?
-
✎ 1 способ (дерево):
Ответ: 10
Решение задания 9.4:
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К, проходящих через город Ж? 
-
✎ 1 способ (с конца):
Ответ: 22
Тренировочные
Решение задания 9.1:
На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город H?
- Решим задание с конца. Т.е. так как траектория поиска путей от А до Н, то мы будем рассматривать сначала город Н.
- В город Н можно попасть из трех городов — C, D и G; запишем это так:
- Теперь аналогично рассмотрим города C, D и G:
Далее, рассмотрим каждый город, дойдя до первого — города А. Для него существует только одни путь. Также, для городов, выходящих только из города А, тоже существует только 1 путь. Таким образом имеем:
Ответ: 13
Решение задания 9.2:
На карту нанесены 4 города (A, B, C и D).
Известно, что:
между городами A и C — три дороги,
между городами C и B — две дороги,
между городами A и B — две дороги,
между городами C и D — две дороги,
между городами B и D — четыре дороги.
По каждой из этих дорог можно ехать в обе стороны.
Сколькими различными способами можно проехать из A в D, посещая каждый город не более одного раза?