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

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

Топологическая сортировка вершин ориентированного графа без циклов.
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