Алгоритмы и структуры данных. Графы. Алгоритмы на графах

1.

ИНФОРМАТИКА
(3 семестр)
Алгоритмы и структуры данных
Графы. Алгоритмы на графах.
Идет подготовка презентации…

2.

Способы представления графов
Основные способы представления графов:
• матрица смежности;
• списки смежности;
• списки инциденции.
Матрица смежности
Столбцы и строки – вершины графа. Если из вершины А в В есть ребро – ставится 1, если нет – 0.
Данный способ удобно использовать, если граф является статическим (кол-во вершин со
временем не меняется) и полным (т.е. у которого число связей сильно больше, чем отсутствие
связей). Однако в случае, если в граф периодически требуется добавлять/удалять из него
вершины, то матрицу придется перестраивать, что будет неэффективно. В связи с этим часто
используются другие подходы – списки смежности или списки инциденции.
Идет показ слайда…
из 15

3.

Способы представления графов
Списки смежности
Массив списков, где каждой ячейке массива соответствует своя вершина, а в самих списках
находятся все соседние вершины.
Если граф взвешенный, то веса и прочую необходимую информацию также можно хранить в
соответствующих ячейках.
Идет показ слайда…
3 из 15

4.

Способы представления графов
Списки инциденции
Массив списков, где каждой ячейке массива соответствует своя вершина, а в самих списках
находятся все исходящие ребра. В ребрах часто хранится начальная вершина, конечная вершина
и дополнительная информация (например, вес ребра, плотность потока и т.д.).
В случаях, когда в ребрах хранится большая часть информации и когда ребра удобно
рассматривать как отдельные объекты независимо от графа, выгодно использовать списки
инциденции. В случаях, когда большая часть информации хранится в вершинах, а в ребрах
хранится только вес и они не рассматриваются как отдельные объекты, удобно использовать
списки смежности.
Идет показ слайда…
4 из 15

5.

BFS (поиск в ширину)
Поиск в ширину – алгоритм для нахождения кратчайшего расстояния между вершинами в
невзвешенном графе (для взвешенных графов используются другие алгоритмы). Сложность –
O(V+E).
Рассмотрим нерекурсивный алгоритм:
• Выбираем начальную вершину, от которой будем искать кратчайший путь, и помещаем ее в
очередь.
• Помещаем все смежные вершины в очередь, удаляем 1-ый элемент из очереди, помечаем его
как checked, увеличиваем счетчик на 1 (count++). Если смежная вершина помечена как checked,
ее нельзя помещать в очередь.
• Выполняем данный алгоритм до тех пор, пока очередь не
будет пуста, либо не будет найдена искомая вершина.
Расстояние между вершинами равно count. Чтобы
восстановить путь – рекурсивно переходим к любой
соседней вершине с расстоянием меньшим на 1, пока не
дойдем до начальной вершины с расстоянием 0.
Идет показ слайда…
5 из 15

6.

BFS (поиск в ширину)
Пример:
1)Помещаем вершину 1 в очередь и помечаем как checked.
Count[1] = 0.
2)Добавляем в очередь все смежные вершины с вершиной 1, после удаляем
вершину 1 из очереди, добавляем вершины 2, 3, 4, 5 в массив обработанных
вершин checked.
Count[2, 3, 4, 5] = Count[1]++.
3)Выбираем первую вершину из очереди (вершина 2), добавляем в очередь
все смежные вершины с вершиной 2, которые не находятся в массиве checked
(как вершина 1 и 3). Из таких вершин нас устраивает только вершина 6.
Вершину 2 удаляем.
Count[6] = Count[2]++.
Аналогично для всех оставшихся вершин.
В итоге, когда очередь будет пуста, мы получим для каждой i вершины свое расстояние Count[i] от вершины 1. Чтобы
получить путь до нее, надо, начиная с i вершины, рекурсивно идти к любой соседней вершине, у которой
Count = Count[i] - 1, пока не дойдем до вершины 1.
Идет показ слайда…
6 из 15

7.

DFS (поиск в глубину)
Поиск в глубину – алгоритм для нахождения конкретной вершины в графе. Сложность – O(V+E).
Рассмотрим нерекурсивный алгоритм:
• Выбираем любую вершину, помещаем ее в стек и помечаем как checked.
• Выбираем любую смежную вершину, если она не является checked – помещаем ее в стек. Если среди
соседних вершин нет ни одной без пометки checked – вынимаем вершину из стека.
• Выполняем 2-ой шаг до тех пор, пока в графе все вершины не будут checked, либо пока не будет
найдена искомая вершина.
Помимо прочего, в DFS бывает полезно помечать время входа/выхода из
вершины. Для этого заводится счетчик count, который увеличивается на 1
при каждой операции добавления/удаления над стеком. При этом для
каждой вершины фиксируется ее время добавления/удаления из стека в
переменных in и out.
Для ориентированного графа алгоритм работает аналогично.
Идет показ слайда…
7 из 15

8.

DFS (поиск в глубину)
Пример:
1)Помещаем вершину 1 в стек и помечаем как checked. In[1]=Count=0
2)Выбираем любую вершину, смежную с 1, не являющуюся checked –
вершину 4. In[4]=Count++=1
3)Также для вершины 2 выбираем любую смежную, не являющуюся
checked (как вершина 1) – вершину 6. In[6]=2
4)Аналогично для всех вершин по пути, пока не остановимся на вершине 7.
In[7]=5.
5)Т.к. у вершины 7 больше нет смежных вершин, не являющихся checked
(как вершина 3), мы выходим из этой вершины, убирая ее из стека.
Out[7]=6.
6)Аналогично идем обратно по предыдущим вершинам, выходя из них,
пока не вернемся в вершину 1.
7)У вершины 1 еще есть смежная вершина, не являющаяся checked –
вершина 5. Помещаем вершину 5 в стек, помечаем как checked. In[5]=11.
Идет показ слайда…
8 из 15

9.

DFS (поиск в глубину)
Пример:
8)Т.к. у вершины 5 больше нет смежных вершин, не являющихся
checked (как вершина 1 и 4), мы выходим из этой вершины,
убирая ее из стека. Out[5]=12.
9)У вершины 1 больше нет смежных вершин, не являющихся
checked, поэтому вы мы выходим из нее, убирая из стека.
Out[1]=13
Т.к. в графе больше нет вершин без пометки checked, алгоритм
окончен. Важно! Если бы в графе были обособленные подграфы,
мы бы также для них продолжили процедуру поиска в глубину,
т.е. алгоритм бы не закончился, если бы стек оказался пуст. При
этом глобальный счетчик Count бы продолжал бы увеличиваться
(в топологической сортировке будет разобран подобный
пример).
Идет показ слайда…
9 из 15

10.

Топологическая сортировка
Пусть у нас есть ациклический ориентированный граф. Тогда если мы сможем
пронумеровать (расположить по порядку) все его вершины так, что из вершины с меньшим
номером вершины можно попасть только в вершину с большим номером, но не наоборот,
то такая процедура называется топологической сортировкой. Результат топологической
сортировки – последовательность вершин.
Пример:
Результат алгоритма для примера выше: {1, 2, 3, 4, 5, 6, 7, 8}
Понятно, что порядок может быть не единственным, это зависит от выбора вершин
(например, вершины 1, 2 и 3 можно переставлять в произвольном порядке), но стрелки
всегда должны идти только в одном направлении. Граф, содержащий циклы, топологически
отсортировать нельзя.
Идет показ слайда…
10
из 15

11.

Топологическая сортировка
Сделаем процедуру DFS начиная с вершины А.
Первое число рядом с вершиной соответствует переменной in (время входа в вершину) а
второе – out (время выхода из вершины). Добавим все вершины в список в порядке
завершения обработки вершины: чем позднее была обработана вершина, тем ближе она
находится к началу списка.
Результат алгоритма – топологически отсортированная пос-ность:
Идет показ слайда…
11 из 15

12.

Топологическая сортировка
Граф будем представлять как вектор списков: каждому элементу вектора соответствует свой
номер вершины, в каждой ячейке хранится список смежных вершин.
Далее приведем ф-ии реализации рекурсивного обхода в глубину dfs и топологической
сортировки topSort. Не стоит забывать, что при наличии циклов в графе, вершины в графе
отсортировать невозможно, поэтому необходимо делать проверку на наличие циклов.
Как определить, что в графе есть цикл? Если мы ранее уже вошли в вершину, но при этом
еще не покинули ее, т.е. countIn != 0, а countOut = 0, значит мы замкнулись в цикле.
Идет показ слайда…
12 из 15

13.

Топологическая сортировка
Идет показ слайда…
13 из 15

14.

Кратчайшее расстояние во взвешенных графах.
Алгоритм Дейкстры
Пусть у нас есть взвешенный граф. Рассмотрим алгоритмы, которые позволяют найти кратчайший путь
между вершинами.
Алгоритм Дейкстры
Суть алгоритма состоит в том, что мы находим минимальный путь от заданной вершины до всех
остальных вершин, а не до какой-то конкретной. При этом важно, чтобы веса в графе были
неотрицательны!
Изначальное минимальное расстояние S до всех вершин i неизвестно, отметим его как бесконечно
большое число INF. При этом, чтобы в дальнейшем восстановить путь до какой-либо вершины, будем
записывать в массив родителей p[i] вершину, из которой в вершину i быстрее всего добраться.
Идет показ слайда…
14 из 15

15.

Кратчайшее расстояние во взвешенных графах.
Алгоритм Дейкстры
Введем метод релаксации ребра. Каждый раз при рассмотрении новых вершин будем уточнять
минимальное расстояние до смежных вершин и одновременно помечать путь до них.
Пример:
Пусть у нас есть вершина a со смежными вершинами u и v, w – вес ребра, соединяющего их, S[u] и S[v] –
расстояния от вершины a до вершин u и v. Тогда для того, чтобы уточнить минимальное расстояние от a
до v, надо выбрать минимальное значение из S[v] и S[u] + w(u, v).
Идет показ слайда…
15 из 15

16.

Кратчайшее расстояние во взвешенных графах.
Алгоритм Дейкстры
Рассмотрим пример нахождения кратчайшего пути от вершины 1 до всех остальных вершин. На каждом
шаге алгоритма мы будем последовательно выбирать какую-либо вершину и обновлять путь до всех
смежных вершин методом релаксации ребер. После этого мы будем переходить к следующей вершине,
до которой расстояние от текущей вершины будет минимально по сравнению со всеми смежными
вершинами, т.к. это фактически будет кратчайшее расстояние до данной вершины.
В примере мы начинаем с вершины 1 и методом релаксации пересчитываем расстояния до всех
смежных ребер 2, 3 и 6. После этого мы считаем вершину 1 обработанной и переходим к следующей
вершине – 2, т.к. до нее наименьшее расстояние (7 < 9 и 7 < 14). Несложно догадаться, что кратчайшее
расстояние от вершины 1 до вершины 2 будет вес их общего ребра. Однако то же самое нельзя сказать
про ребра 3 и 6, т.к. в теории до них можно добраться быстрее через вершину 2, но не наоборот.
Идет показ слайда…
16 из 15

17.

Кратчайшее расстояние во взвешенных графах.
Алгоритм Дейкстры
Далее мы переходим к вершине 2 и рассматриваем смежные для нее вершины и аналогично
предыдущему шагу пересчитываем расстояния до них. Рассмотрим на этом шаге подробнее метод
релаксации для вершины 3. Расстояние 1->3=9, расстояние 1->2->3=7+10=17.Таким образом, мы
получаем, что минимальное расстояние до вершины 3 от вершины 1 равно 9.
Для всех остальных вершин шаги
алгоритма идентичны. Алгоритм
работает до тех пор, пока в графе не
будут обработаны все вершины.
Идет показ слайда…
17 из 15

18.

Кратчайшее расстояние во взвешенных графах.
Алгоритм Дейкстры
Идет показ слайда…
18 из 15

19.

Кратчайшее расстояние во взвешенных графах.
Алгоритм Флойда-Уоршелла
Алгоритм Флойда-Уоршелла также служит для нахождения кратчайшего пути между вершинами, однако
в отличие от алгоритма Дейкстры, он работает и для ребер с отрицательными весами, и ищет все
кратчайшие расстояние между любыми вершинами в графе.
Данный алгоритм является частным случаем ДП.
Составим для нашего графа матрицы D0
(матрица минимальных расстояний между
вершинами) и S0 (матрица минимальных
путей, в ячейках хранятся вершины, через
которые проходят траектории кратчайшего
пути).
Если у вершин нет общего ребра, начальное
расстояние между ними задается как
бесконечно большое значение (т.к. мы еще
его не вычислили).
Идет показ слайда…
19 из 15

20.

Кратчайшее расстояние во взвешенных графах.
Алгоритм Флойда-Уоршелла
Принцип работы алгоритма: мы проходим по всем вершинам 1..N и ищем, через какие из них есть пути
между вершинами. Далее методом ДП мы на каждом шаге будем уточнять кратчайшее расстояние между
вершинами (аналогично методу релаксации в алг-тме Дейкстры).
Пример:
Через вершину 4 между вершинами 3 и 5 существует путь только тогда, когда
существует путь 3->4 и 4->5. D[3][4]=6, D[4][5]=4.
Отсюда следует, что из вершины 3 в вершину 5 можно попасть через вершину 4, т.к. это их
общая смежная вершина. Как в этом случае определить кратчайший путь между этими
вершинами? Возможно 2 варианта:
1)Попасть напрямую через общее ребро весом 15, тогда в этом случае расстояние
D[3][5]=15;
2) Попасть через общую смежную вершину 4, тогда в этом случае расстояние
D[3][4]+D[4][5]=6+4=10.
Второй путь короче, откуда следует, что кратчайшее расстояние между вершинами 3 и 5
D[3][5]=10.
Для вершин 1, 2, 4 аналогично (см. рисунок).
Идет показ слайда…
20 из 15

21.

Кратчайшее расстояние во взвешенных графах.
Алгоритм Флойда-Уоршелла
По аналогии для любых случайных двух вершин мы можем составить рекуррентное соотношение. Зная
это соотношением, методом ДП мы сможем найти кратчайшее расстояние между любыми двумя
вершинами в графе. При этом при каждом новом найденном кратчайшем пути в матрицу S мы будем
записывать вершину, через которую проходит этот путь. При этом в дальнейшем нам не составит труда
восстановить траекторию по этой матрице.
Рекуррентное соотношение и ф-ия для нахождения минимального расстояния:
Начальное условие: матрицы D0 и S0 .
Решение: DN и SN (N – последняя рассматриваемая вершина).
Идет показ слайда…
21 из 15

22.

Кратчайшее расстояние во взвешенных графах.
Алгоритм Флойда-Уоршелла. Пример
Идет показ слайда…
22 из 15

23.

Кратчайшее расстояние во взвешенных графах.
Алгоритм Флойда-Уоршелла. Пример
Таким образом, мы прошлись по всем вершинам и наши матрицы D и S полностью сформированы,
теперь по ним мы можем определить кратчайший путь и траекторию между любыми вершинами в
графе.
Идет показ слайда…
23 из 15

24.

Кратчайшее расстояние во взвешенных графах. Алгоритм
Флойда-Уоршелла. Траектория кратчайшего пути
По матрице S нетрудно найти траекторию кратчайшего пути, т.к. в ней хранятся вершины, через которые
эти траектории проходят. Данная процедура является рекурсивной. Приведем пару примеров:
1)Между вершинами 1 и 5 кратчайший путь равен 12, кратчайшая траектория – 1->2->4->5. Проверим это
по матрице S. S[1][5] = 2, т.е. кратчайший путь из 1 в 5 проходит через 2. S[2][5] = 4, т.е. кратчайший путь
из 2 в 5 проходит через 4. S[4][5] = 5, т.е. между вершинами 4 и 5 больше нет других вершин, значит
кратчайшая траектория - 1->2->4->5.
2) Между вершинами 5 и 3 кратчайший путь равен 10, кратчайшая траектория – 5->4->3. Проверим это
по матрице S. S[5][3] = 4, т.е. кратчайший путь из 5 в 3 проходит через 4. S[4][3] = 3, т.е. между
вершинами 5 и 4 больше нет других вершин, значит кратчайшая траектория - 5->4->3.
Ниже приведена ф-ия, которая возвращает траекторию кратчайшего пути в виде списка:
Идет показ слайда…
24 из 15

25.

Кратчайшее расстояние во взвешенных графах.
Сравнение алгоритмов
Минимальное расстояние из вершины V до всех остальных вершин:
• Дейкстры (w >= 0):
n – кол-во вершин
2
o Наивный - O(n )
m – кол-во ребер
o оптимальный - O(nlogn + mlogn) (*)
• Форда (для любых w) - O(nm) (используется редко, т.к. зачастую mn > n2 , а отрицательные ребра в
графах встречаются нечасто)
(*) В оптимальном алгоритме Дейкстры для необработанных вершин при поиске минимального
расстояния используются двоичные либо Фибоначчиевы кучи (т.к. в них быстро выполняется операция
извлечения минимального/максимального элемента).
Минимальное расстояние для всех вершин V до всех вершин в графе:
• Флойда-Уоршелла - O(n3 ) (эффективен для плотных графов, для разреженных эффективнее
оптимальный алгоритм Дейкстры для всех вершин, т.к. условие разреженности графа - m ≪ n2
вытекает из соотношения, что в плотном графе m =
Идет показ слайда…