Алгоритмы и структуры данных. Семестр 2. Лекция 5. Графы

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

Топологическая сортировка вершин ориентированного графа без циклов.
DAG – Directed Acyclic Graph – ориентированный граф без циклов
Интерпретация: вершины – элементарные работы; дуги – зависимость работ друг от друга.
Задача: выстроить работы в последовательности, в которой никакая следующая
задача не может зависеть от предыдущей (дуги направлены только вперед)

Топологическая сортировка вершин ориентированного графа без циклов.
1
5
9
2
7
3
8
4
6
«Наивный» алгоритм нумерации вершин:
Находим какую-либо вершину, в которую не входят дуги, нумеруем ее.
1
Помечаем дуги, выходящие из помеченной вершины, как «не существующие».
Повторяем шаги (1) и (2), пока не будут занумерованы все вершины.
2
3
4
5
6
7
8
9
Оценка времени работы алгоритма.
Построение очереди с приоритетами из вершин графа
n log n
Выборка вершин из очереди
n log n
Коррекция очереди при пометке дуг
m log n
Итого: (m+2n) log n
Проверка ацикличности графа.
Граф содержит цикл, если на шаге (1) не удается найти вершину, в которую не входят дуги.

Топологическая сортировка вершин ориентированного графа без циклов.
1
5
9
2
7
3
8
4
6
«Эффективный» алгоритм нумерации вершин:
Производим обход графа с помощью рекурсивной процедуры обхода, начиная
с произвольной вершины.
Нумеруем каждую вершину при «прохождении ее назад» максимальным из номеров
(то есть нумерация происходит в порядке убывания номеров).
Повторяем шаги (1) и (2), пока не останется непройденных вершин.
9
8
7
6
5
4
3
2
1
Оценка времени работы алгоритма = время обхода = (m+n).
Проверка ацикличности графа.
Граф содержит цикл, если при проходе по «обратной дуге» попадаем в еще непомеченную
(«синюю») вершину.

Алгоритм Флойда - Уоршелла

Алгоритм Флойда - Уоршелла
Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом
В отличии от алгоритма Дейкстры, который позволяет построить ориентированное дерево кратчайших путей от некоторой вершины, метод Флойда позволяет найти длины всех кратчайших путей в графе.
Конечно эта задача может быть решена и многократным применением алгоритма Дейкстры (каждый раз последовательно выбираем вершину от первой до N-ной, пока не получим кратчайшие пути от всех вершин графа), однако реализация подобной процедуры требует значительных вычислительных затрат.
Роберт Флойд

Обозначения
Перенумеруем вершины графа целыми числами от 1 до N.
Обозначим через di,jm длину кратчайшего пути из вершины i в вершину j, который в качестве промежуточных может содержать только первые m вершин графа (промежуточной вершиной пути является любая принадлежащая ему вершина, не совпадающая с его начальной или конечной вершинами).
Если между вершинами i и j не существует ни одного пути указанного типа, то условно будем считать, что di,jm=∞.
Величина di,j0, представляет длину кратчайшего пути из вершины i в вершину j, не имеющего промежуточных вершин, т. е. длину кратчайшей дуги, соединяющей i с j (если такие дуги присутствуют в графе).

Обозначения
Обозначим через Dm матрицу размера NxN, элемент (i,j) которой совпадает с di,jm.
Если в исходном графе нам известна длина каждой дуги, то мы можем сформировать матрицу D0, которая в алгоритме Флойда выступает в качестве исходной.
Вначале из этой матрицы вычисляется матрица D1. Затем по матрице D1 вычисляется матрица D2 и т. д. по формуле:
di,jm = min{ di,mm-1 + dm,jm-1; di,jm-1}
Процесс повторяется до тех пор, пока по матрице DN-1 не будет вычислена матрица DN.

Суть алгоритма Флойда
заключается в проверке того, не окажется ли путь из вершины i в вершину j короче, если будет проходить через некоторую промежуточную вершину m.
Пусть есть три вершины – i, j,m – и расстояния между ними: dij, dim, dmj.
Если выполняется неравенство dim + dmj < dij, то целесообразно заменить путь i j путём i m + m j
«Треугольный оператор»

Этап 1. Перенумеровать вершины графа от 1 до N, определить матрицу D0, каждый элемент di,j0 которой есть длина кратчайшей дуги между вершинами i и j. Если такой дуги нет, положить значение элемента di,j0 = ∞. Значения диагональных элементов di,i = 0.
Алгоритм Флойда на примере

Матрицу S0, в которой будем запоминать последовательность вершин в кратчайшем пути, заполним так: sij = j
Алгоритм Флойда на примере

Алгоритм Флойда на примере
Задаём строку m и столбец m как ведущую строку и ведущий столбец.
Для всех элементов dij матрицы Dm-1 рассматриваем возможность применения треугольного оператора. Если выполняется неравенство:
dim + dmj < dij (i≠j, j≠m, i≠m),
то делаем следующее:
а) в матрице Dm заменяем элемент dij матрицы Dm-1 суммой dim + dmj;
b) в матрице Sm меняем элемент sij матрицы Sm-1 на m;
c) полагаем m=m+1, повторяем основной этап, пока m < N
Основной этап

Алгоритм Флойда на примере

Алгоритм Флойда на примере

Алгоритм Флойда на примере

Алгоритм Флойда на примере

Алгоритм Флойда на примере

Алгоритм Флойда на примере

Алгоритм Флойда на примере
Последний этап.
После реализации N этапов алгоритма определение по матрицам Dn и Sn кратчайшего пути между узлами i и j выполняется по следующим правилам:
Кратчайшее расстояние между узлами i и j равно элементу dij в матрице Dn.
Промежуточные узлы пути от узла i к узлу j определяем по матрице Sn. Пусть sij = k, тогда имеем путь i -> j-> k.
Если далее sik = k и skj = j, то считаем, что весь путь определён. В противном случае повторяем процедуру для путей от узла i к узлу k и от узла k к узлу j.

d25 = 21
Путь: 2->4 ->5
d51 = 20
Путь: 5->6 ->3 -> 1
Алгоритм Флойда на примере

Объем памяти - ?
О-большое - ?
V * V = V2
О(V) = V3
Алгоритм Дейкстры
О(V) = V3

Волновой алгоритм (Алгоритм Ли)

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

Инициализация
Пометить стартовую ячейку d := 0
Распространение волны
ЦИКЛ
ДЛЯ каждой ячейки X, помеченной числом d
пометить все соседние свободные непомеченные ячейки числом d + 1
КЦ
d := d + 1
ПОКА (финишная ячейка не помечена) И (есть возможность распространения волны)
Восстановление пути
ЕСЛИ финишная ячейка помечена
ТО
перейти в финишную ячейку
ЦИКЛ
выбрать среди соседних ячейку, помеченную числом на 1 меньше числа в текущей ячейке
перейти в выбранную ячейку и добавить её к пути
ПОКА текущая ячейка — не стартовая
ВОЗВРАТ путь найден
ИНАЧЕ
ВОЗВРАТ путь не найден

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

Алгоритм Форда – Фалкерсона

Потоки в сетях.
И
1
2
3
С
4
Сеть – это ориентированный нагруженный граф, в котором нагрузка имеет интерпретацию
«пропускная способность» (разумеется, положительная; можно считать, что отсутствующее
ребро соответствует нулевой нагрузке). Будем обозначать эту нагрузку c (u, v).
16
10
13
4
12
9
14
20
7
4
Мы будем считать, что
a) в сети есть две выделенные вершины – исток (только исходящие дуги) и сток (только входящие дуги);
b) любая вершина лежит на каком-нибудь пути из истока в сток (нет «бесполезных» вершин).
Поток в сети – это задание некоторой дополнительной нагрузки на ребра.
Свойства потока:
a) поток по ребру не может превышать пропускной способности ребра и всегда неотрицателен;
b) в любую вершину (кроме истока и стока) количество втекающей жидкости равно количеству вытекающей.
11/16
12/12
1/4
8/13
4/9
11/14
15/20
7/7
4/4
Величина потока – это сумма исходящего потока из истока. Очевидно, она равна сумме
входящего потока в сток. Основная задача – найти максимальный поток в сети с заданной
пропускной способностью.

Потоки в сетях.
И
1
2
3
С
4
Пусть задана сеть и поток в ней. Свяжем с потоком функцию f (u, v), обладающую следующими
свойствами:
10
a) если по ребру (u,v) идет поток величиной c, то положим f (u, v) = c, f (v, u) = -c;
b) если есть два «встречных» потока c1 и c2 по ребрам (u, v) и (v, u) соответственно, то
полагаем f (u, v) = c1-c2. На самом деле всегда можно считать, что на самом деле есть
только один поток величиной |c1-c2|.
На приведенной выше картинке: f (И, 3) = 8; f (3, 2) = -4; f (1, 3) = -1.
Для каждого ребра (при заданном потоке f) определим также его «остаточную пропускную
способность»: cf(u, v) = c (u, v) – f(u, v)
Например, для заданного потока cf(3, 4) = 3, cf(1, 3) = 11.
11/16
12/12
1/4
8/13
4/9
11/14
15/20
7/7
4/4

Метод Форда – Фалкерсона
И
1
2
3
С
4
Будем искать дополняющие пути из истока в сток, по которому можно пропустить
дополнительное количество вещества. Тогда схема алгоритма может быть записана
следующим образом:
10
11/16
12/12
1/4
8/13
4/9
11/14
15/20
7/7
4/4
f = 0;
while (существует дополняющий путь p) {
дополнить f вдоль p;
}
Для поиска дополняющих путей найдем все остаточные пропускные способности ребер сети
и составим остаточную сеть из всех положительных величин:
И
1
2
3
С
4
11
5
12
3
5
4
3
5
7
4
11
15
11
5
8
И
1
2
3
С
4
10
11/16
12/12
1/4
12/13
9
11/14
19/20
7/7
4/4

Пример реализации метода Форда – Фалкерсона
И
1
2
3
С
4
10
16
12
4
13
9
14
20
7
4
И
1
2
3
С
4
10
12/16
12/12
4
7/13
9
7/14
19/20
7/7
4
12/16
12/12
12/20
И
1
2
3
С
4
10
4
12
4
13
9
14
8
7
4
12
12
И
1
2
3
С
4
10
12/16
12/12
4
11/13
9
11/14
19/20
7/7
4/4
И
1
2
3
С
4
10
4
12
4
6
9
7
1
7
4
19
12
7
7
И
1
2
3
С
4
10
4
12
4
4
9
3
1
7
4
19
12
11
11

Выбор дополняющего пути в методе Форда – Фалкерсона
И
1
2
С
1
1 000 000
Если выбор дополняющего пути производится не очень удачно, то процедура поиска
максимального потока может затянуться.
1 000 000
1 000 000
1 000 000
1/1 000 000
1/1 000 000
1/1
И
1
2
С
1
1 000 000
1 000 000
999 999
999 999
1
1
И
1
2
С
1
1/1 000 000
1/1 000 000
1/1 000 000
1/1 000 000
и так далее, всего 2 000 000 шагов…
Можно попробовать искать кратчайший (по числу ребер) дополняющий путь между истоком
и стоком. Например, с помощью поиска в ширину. Получающийся при этом алгоритм
(реализация метода Форда – Фалкерсона) называется алгоритмом Эдмондса – Карпа).
Можно показать, что в алгоритме Эдмондса – Карпа число шагов ограничено сверху числом
2nm, где m – число ребер в сети, а n – число вершин. Поскольку поиск в ширину, изменение
потоков вдоль ребер и построение остаточной сети требуют времени O(m), то общее время
работы алгоритма можно оценить как O(m2n).

Сеть с несколькими истоками и стоками
И1
1
2
С1
10
3
Если в графе есть несколько истоков и/или несколько стоков, то задача нахождения
максимального потока в такой сети сводится к задаче с одним истоком и одним стоком.
12
21
8
И2
И3
3
4
4
С2
5
6
11
7
12
9
15
12
13
18
22
15
13
17
27
17
18
17
20
И
С
∞
∞
∞
∞
∞

Пропустим итерацию 4 и 5

Минимальное остовное дерево (МОД)

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

Цикломатическое число γ показывает, сколько ребер нужно удалить из графа, чтобы в нем не осталось циклов
γ = m – n + 1,
m - количество ребер
n - количество вершин

Задача 1
В некотором районе было решено провести газопровод между пятью деревнями. От Кошкино до Мышкино идти 10 км, от Мышкино до Ступино – 3 км, от Кошкино до Малаховки – 6 км, от Малаховки до Черняевки – 12 км, от Кошкино до Ступино – 11 км, от Мышкино до Чернеевки – 5 км, от Кошкино до Чернеевки – 7 км. Как необходимо провести трубу, чтобы она соединяла все пять деревень, и затраты при этом были минимальными?

Задача 1
Построим граф, моделирующий дороги, соединяющие деревни.

Задача 1
Задача сводится к построению остовного связного дерева минимального веса.
Рассчитаем цикломатическое число.
m (количество ребер) равно 7
n (количество вершин) рано 5
γ = 7 – 5 + 1 = 3
Т.е. три деревни напрямую соединены газовой трубой не будут.

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

Алгоритм Прима
Пусть дан взвешенный неориентированный граф.
Для построения минимального остовного дерева необходимо:
1. Представить граф в виде матрицы смежности
2. Найти в матрице наименьший элемент, соответству-ющий ребру, соединяющему i-ю и j-ю вершины графа
3. Вычеркнуть элементы i-й и j-й строки матрицы
4. Пометить i-й и j-й столбцы матрицы
5. В помеченных столбцах i и j найти
наименьший элемент, отличный от уже найденного
6. Повторять пункты 3-5 до тех пор, пока не будут задействованы все вершины графа
(переходы по щелчку)

Задача 1
Решим задачу по алгоритму Прима.
Переопределим вершины графа.

Задача 1
Представим граф в виде матрицы смежности.
Найдем минимальный элемент.
Он равен 3
3
3

Задача 1
Вычеркнем 2-ю и 3-ю строки таблицы. А столбцы 2 и 3 выделим.
Найдем минимальный элемент в выделенных столбцах.
Он равен 5
5

Задача 1
Вычеркнем 5-ю строку таблицы. А столбец 5 выделим.
Найдем минимальный элемент в выделенных столбцах.
Он равен 7
5
7

Задача 1
Вычеркнем 1-ю строку таблицы. А столбец 1 выделим.
Найдем минимальный элемент в выделенных столбцах.
Он равен 6
5

Задача 1
Вычеркнем 4-ю строку таблицы. А столбец 4 выделим.

Задача 1
Получаем связное остовное дерево минимальное веса.
12
7
10
11
3
6
5
5
1
2
3
4

Задача 1
Ответ: газопровод с минимальными затратами необходимо прокладывать так:
Протяженность газопровода – 21 км.

Алгоритм Прима шаг 0
Суммарная длина дерева = 0
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 1
Суммарная длина дерева = 0
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 2
Суммарная длина дерева = 4
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 3
Суммарная длина дерева = 12
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 4
Суммарная длина дерева = 14
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 5
Суммарная длина дерева = 18
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 6
Суммарная длина дерева = 20
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 7
Суммарная длина дерева = 21
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 8
Суммарная длина дерева = 28
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 9
Суммарная длина дерева = 37
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 10
Суммарная длина дерева = 37
A
H
G
I
B
F
C
D
E
4
2
1
2
4
7
8
9

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

Задача 3
Задача сводится к построению остовного связного дерева минимального веса.
Рассчитаем цикломатическое число.
m (количество ребер) равно 9
n (количество вершин) рано 6
γ = 9 – 6 + 1 = 4
Т.е. четыре дороги, соединяющие города, не будут включены в туристический маршрут.

Алгоритм Крускала
Удалить все ребра и получить остовной подграф с изолированными вершинами.
Отсортировать ребра по возрастанию.
Ребра последовательно, по возрастанию их весов, включаются в остовное дерево. Возможны случаи:
а) обе вершины включаемого ребра принадлежат одноэлементным подмножествам, тогда они объединяются в новое, связное подмножество;
б) одна из вершин принадлежит связному под-множеству, другая нет, тогда включаем вторую в подмножество, которому принадлежит первая;
в) обе вершины принадлежат разным связным подмножествам, тогда объединяем подмножества;
г) обе вершины принадлежат одному связному подмножеству, тогда исключаем данное ребро.
Алгоритм завершается, когда все вершины будут объединены в одно множество.

Задача 3
Для определения туристического маршрута минимальной длины воспользуемся алгоритмом Крускала.

Задача 3
Построим остовной подграф, содержащий только изолированные вершины.
1
6
5
2
3
4
25
18
15
12
20
23
21
19
26
Шаг 1
Получаем шесть одноэлементных подмножеств.

Задача 3
Найдем ребро минимального веса и добавим его в остовной подграф.
1
6
5
2
3
4
25
18
15
12
20
23
21
19
26
Шаг 2
Образуется связное подмножество вершин {V5, V6}.

Задача 3
Среди оставшихся ребер найдем ребро минимального веса и добавим его в остовной подграф.
1
6
5
2
3
4
25
18
15
12
20
23
21
19
26
Шаг 3
Добавляем в подмножество вершин еще одну {V5,V6,V1}.

Задача 3
Среди оставшихся ребер найдем ребро минимального веса и добавим его в остовной подграф.
1
6
5
2
3
4
25
18
15
12
20
23
21
19
26
Шаг 4
Добавляем в подмножество вершин еще одну {V5,V6,V1,V2}.

Задача 3
Среди оставшихся ребер найдем ребро минимального веса и добавим его в остовной подграф.
1
6
5
2
3
4
25
18
15
12
20
23
21
19
26
Шаг 5
Образуется два подмножества {V5,V6,V1,V2} и {V3,V4} .

Но обе вершины принадлежат одному подмножеству {V5,V6,V1,V2}. Значит это ребро исключаем.
Задача 3
Среди оставшихся ребер найдем ребро минимального веса и добавим его в остовной подграф.
1
6
5
2
3
4
25
18
15
12
20
23
21
19
26
Шаг 6
Подмножества объединяются в единое связное множество {V1,V2,V6,V5,V3,V4} .

Задача 3
Остальные ребра включать в граф не надо, т.к. все их вершины уже принадлежат одному связному множеству.
1
6
5
2
3
4
25
18
15
12
20
23
21
19
26
Итог
Получили остовное связное дерево минимального веса, равного 85.

Пример 4

Алгоритм Краскала шаг 0
Суммарная длина деревьев = 0
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Краскала шаг 1
Суммарная длина деревьев = 1
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Краскала шаг 2
Суммарная длина деревьев = 3
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Краскала шаг 3
Суммарная длина деревьев = 5
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Краскала шаг 4
Суммарная длина деревьев = 9
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Краскала шаг 5
Суммарная длина деревьев = 13
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Краскала шаг 6
Суммарная длина деревьев = 20
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Краскала шаг 7
Суммарная длина деревьев = 28
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Краскала шаг 8
Суммарная длина деревьев = 37
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Краскала шаг 9
Суммарная длина деревьев = 37
A
H
G
I
B
F
C
D
E
4
8
2
1
2
4
7
9

Задача 5
На строительном участке необходимо создать телефонную сеть, соединяющую все бытовки. Для того, чтобы телефонные линии не мешали строительству, их решили проводить вдоль дорог. Схема участка изображена на рисунке.
Каким образом провести телефонные линии, чтобы их общая длина была минимальной?
Ответ
Общая длина телефонной линии равна 930 метров