Структуры и алгоритмы обработки данных

1.

Структуры и алгоритмы
обработки данных
ФИО преподавателя: Туманова М.Б.
e-mail: [email protected]
Online-edu.mirea.ru

2.

Центр дистанционного обучения
Графы
2
mirea.ru

3.

Центр дистанционного обучения
Нелинейные структуры данных
• Нелинейные структуры
позволяют выражать
более сложные
отношения между
элементами
• Множество предметных
областей описываются
нелинейно. Примеры →
• Теоретико-графовые:
• Деревья и лес
• Граф (сеть);
• Теоретико-
3
mirea.ru

4.

Центр дистанционного обучения
Примеры графовых структур:
• Оглавление книги
• Организационная
структура предприятия
• Файловая система
• Пространство имён DNS
• Сеть автодорог
• Логистические схемы
• Компьютерная сеть
(топология)
• Топология микросхем
4
mirea.ru

5.

Центр дистанционного обучения
Граф G [R,A] –
• Это совокупность двух
множеств – вершин R и рёбер
(в неориентир.) или дуг (в
ориентир.) A
• Граф моделирует отношения
(связи) между вершинами
• Граф – средство
моделирования в реальных
задачах
• Конечный – если множества R
и A конечны
5
• Взвешенный – если
рёбрамmirea.ru

6.

Центр дистанционного обучения
Ориентированный
(направленный) граф (орграф)
• Пусть вершины pi,pj –
концевые точки ребра а
• Тогда если порядок обхода
концевых точек
существенен (есть
начальная вершина и
конечная), то ребро а
ориентированное (дуга)
• Иначе ребро а
неориентированное
• Граф ориентированный,
6
mirea.ru
если ориентированы
все

7.

Центр дистанционного обучения
Понятия
• Помеченный граф, если
вершины имеют метки
(числовые или текстовые)
• 2 вершины смежные, если
соединены одним ребром
• Соседи – это вершины,
смежные с некоторой
вершиной
• Путь – последовательность
вершин от одной вершины к
другой
7
mirea.ru

8.

Центр дистанционного обучения
Важные задачи теории графов
• Семь мостов Кёнигсберга
(1736, Л. Эйлер)
• Задача коммивояжёра – поиск
самого выгодного маршрута,
проходящего через указанные
вершины
• Проблема четырёх красок
(1976, К. Аппель, В. Хакен)
• Задача о клике (клика – полный
подграф) – существует ли в графе
клика размера k; найти в заданном
графе клику максимального размера
8
mirea.ru
• Нахождение минимального

9.

Центр дистанционного обучения
Сеть
(транспортная сеть, flow
network) –
• Это ориентированный граф
G = (V,E), в котором каждое
ребро (u,v) ∈ E имеет
неотрицательную
пропускную способность
c(u,v) ≥ 0 и поток f (u,v)
• Если (u,v) ∉ E, то c(u,v)=0
• Выделяются две вершины:
исток (источник) s и сток t
такие, что любая другая
вершина сети лежит на пути
из s в t
9
mirea.ru

10.

Центр дистанционного обучения
Поток в сети
• Потоком (англ. flow) f в сети G
является действительная
функция f:V×V→R,
удовлетворяющая условиям:
1) f(u,v)=−f(v,u)
(антисимметричность или
кососимметричность);
2) |f(u,v)|⩽c(u,v) (ограничение
пропускной способности), если
ребра нет, то f(u,v)=0;
3) =0 для всех вершин u, кроме
истока s и стока t (закон
сохранения потока)10
mirea.ru

11.

Центр дистанционного обучения
Представление графа в
программе
• Вершины в графе –
экземпляры сущностей,
описываемых набором полей
с данными (аналогично
деревьям) → выбирают тип
структура или класс
• Рёбра в графе – может быть >2
(нежёсткая структура)
• Способы представления:
1.Матрица смежности
→
2.Матрица инцидентности
3.Список смежности
4.Список рёбер. 11
mirea.ru

12.

Центр дистанционного обучения
1. Матрица смежности –
• Это двумерный массив –
квадратная матрица
• Для неориентированных
графов
• В ячейке 0 (false) – отсутствие
ребра
• Нули на главной диагонали,
если нет петель
• Треугольная часть матрицы над
диагональю – зеркальное
отражение части под ней →
12
mirea.ru
избыточность → при

13.

Центр дистанционного обучения
2. Матрица инцидентности
(инциденции)
• Инцидентность – отношение
между парой вершин и
ребром
• Инциденция – тройка вида (a,
u, b), указывающая, какую пару
(a, b) элементов множества
вершин графа соединяет тот
или иной элемент u множества
рёбер
• Количество строк в матрице
равно числу вершин,
13
mirea.ru
количество столбцов
– числу

14.

Центр дистанционного обучения
3. Список смежности –
• Набор списков, i-й из которых
содержит номера вершин, в которые
идут рёбра из вершины i
• Не является таблицей («список
списков»)
Преимущества:
• Наиболее удобный способ для
представления разреженных графов,
при реализации алгоритмов обхода
графа
• Рациональное использование памяти
O(|V|+|E|)
14
mirea.ru
• Позволяет проверять наличие ребра и

15.

Центр дистанционного обучения
4. Список рёбер
• В каждой строке
записываются две смежные
вершины, инцидентные
ребру (для взвешенного
графа и вес ребра)
• Количество строк в списке
ребер равно результату
сложения ориентированных
рёбер с удвоенным
количеством
неориентированных рёбер
• Размер занимаемой памяти:
15
mirea.ru
O(|E|)

16.

Центр дистанционного обучения
Обход графа
• Обход – это процесс
систематического просмотра
всех рёбер или вершин графа
с целью отыскания рёбер или
вершин, удовлетворяющих
некоторому условию
Способы обхода:
В ширину →
В глубину;
Алгоритмы обхода лежат в
основе решения различных
задач обработки графов –
16
mirea.ru
построения остовного
дерева,

17.

Центр дистанционного обучения
1. Поиск в ширину
(breadth-first search, BFS)
• Подразумевает поуровневое исследование
графа:
• Сначала посещается узел-источник – произвольно
выбранный узел,
• Затем – все его потомки,
• После этого потомки потомков и т.д.
• Вершины просматриваются в порядке
возрастания их расстояния от корня
• Алгоритм прекращает свою работу после обхода
всех вершин графа, либо в случае выполнения
требуемого условия (нахождения целевого
узла).
17
mirea.ru

18.

Центр дистанционного обучения
Особенности алгоритма поиска
в ширину:
• При обнаружении
заданной вершины
(целевого узла)
построенный путь является
кратчайшим
• Для реализации алгоритма
удобно использовать
очередь
• Сложность поиска при
списочном (нематричном)
представлении графа
18
mirea.ru
O(n+m), т.к. рассматриваются

19.

Центр дистанционного обучения
Применения алгоритма поиска
в ширину:
Поиск кратчайшего пути в
невзвешенном графе
(ориентированном или
неориентированном)
Поиск компонент связности
Нахождения решения
какой-либо задачи (игры) с
наименьшим числом ходов
Найти все рёбра, лежащие
на каком-либо кратчайшем
пути между заданной парой
19
mirea.ru
вершин

20.

Центр дистанционного обучения
Реализация на C++
(с использованием
очереди STL)
20
mirea.ru

21.

Центр дистанционного обучения
2. Поиск в глубину
(Depth-first search, DFS)
• Предполагает
продвижение вглубь до
тех пор, пока это
возможно – до
попадания в тупик
• Тупик – вершина графа, у
которой все смежные
вершины посещены
• Из тупика возвращаемся
вдоль пройденного пути
до вершины, у которой
есть ещё не посещенный
21
mirea.ru
сосед

22.

Центр дистанционного обучения
Особенности алгоритма поиска
в глубину:
• Алгоритм работает как на
ориентированных, так и на
неориентированных графах
• Применимость алгоритма зависит
от конкретной задачи
• Для реализации алгоритма удобно
использовать стек (нерекурсивный
алгоритм) или рекурсию
• Временная сложность зависит от
представления графа:
22
2
mirea.ru

23.

Центр дистанционного обучения
Применения алгоритма поиска
в глубину:
23
Поиск любого пути в графе
Поиск лексикографически
первого пути в графе
(см. лексикографический
порядок)
Проверка, является ли одна
вершина графа предком другой
Поиск наименьшего общего
предка
Топологическая сортировка
23
Поиск компонент связности.
mirea.ru

24.

Центр дистанционного обучения
Реализация на C++
(с использованием
очереди STL)
стеком
24
mirea.ru

25.

Центр дистанционного обучения
Реализация на C++
(с использованием
очереди STL)
рекурсией
25
mirea.ru

26.

Центр дистанционного обучения
Обход в глубину при
программировании игр
• В типичной игре существует постоянно
расширяющийся граф вариантов
(например, «крестики-нолики»)
• Последовательность ходов хорошо
представляется в виде дерева (узлы –
отдельные ходы) – дерево игры
• Выбор хода – на основе анализа всех
путей до конца игры (в примере 9!=
362 880 путей)
• В более сложных играх проходят путь
до определённой глубины – даже
26
mirea.ru
суперЭВМ не способна видеть
позиции

27.

Центр дистанционного обучения
Транзитивное замыкание
• Бинарное отношение R на множестве X
называется транзитивным, если для любых трёх
элементов a, b, c этого множества выполнение
отношений aRb и bRc влечёт выполнение
отношения aRc
• Связь вершин в графе транзитивна – т.е. если есть
ориентированный путь из А в В и из В в С, то это
значит, что есть путь из А в С
• Транзитивное замыкание бинарного отношения –
это пополнение отношения минимальным
количеством новых пар так, чтобы отношение
стало транзитивным.
27
mirea.ru

28.

Центр дистанционного обучения
Транзитивное замыкание
орграфа
• Транзитивное замыкание в
орграфе – добавление дуг
между парами вершин, если в
исходном орграфе между ними
существуют пути
• Т.е. рёбра в транзитивном
замыкании соединяют каждую
вершину со всеми вершинами,
достижимыми из этой
вершины в исходном орграфе
• Транзитивное замыкание
отражает структурные
свойства
28
mirea.ru

29.

Центр дистанционного обучения
Алгоритм Уоршелла построения
транзитивного замыкания
орграфа
• Матрица смежности
содержит все допустимые
одношаговые пути – основа
алгоритма
• Идея алгоритма:
Если есть ориентированный
путь из s в i и из i в t, то есть
путь и из s в t (за 2 шага)
• На основании найденных
ранее путей можно строить
пути произвольной длины.
29
mirea.ru

30.

Центр дистанционного обучения
Первая строка A:
• В ячейке С – единица, т.е.
существует путь от A к C
• Если бы существовал путь от
другой вершины X к A, то
существовал бы и путь от X к C
• Какие рёбра графа
заканчиваются в вершине A (и
есть ли они?)? – см. столбец A –
есть одна единица в строке B, т.е.
существует ребро
от B к A
• Значит, существуют 30пути от B кmirea.ru
A

31.

Центр дистанционного обучения
Строки В, С, D:
• Столбец A содержит 1,
указывая на существование
ребра от B к A
• Но существуют ли другие
рёбра, заканчивающиеся в
B?
• Столбец B пуст (ни одно
ребро не заканчивается в B),
значит ни одна из единиц в
строке B не приведет к
обнаружению более
mirea.ru
длинного пути 31

32.

Центр дистанционного обучения
Строка Е:
• В строке Е есть ребро от Е к
C
• В столбце Е есть ребро от B
к Е, т.е. существует путь от
BкC
• Однако этот путь уже был
обнаружен ранее (есть 1 в
соотв.ячейке таблицы)
• Пути от D к Е и от Е к C
образуют путь от D к C, в
эту ячейку ставится 1.
32
mirea.ru

33.

Центр дистанционного обучения
Результат:
• В матрицу смежности были
добавлены две единицы
• Измененная матрица
показывает, к каким узлам
можно перейти от другого узла
за любое количество шагов
• Граф на основе новой матрицы
– это и есть транзитивное
замыкание исходного графа
• Программная реализация. →
33
mirea.ru

34.

Центр дистанционного обучения
Дизъюнктивное объединение
строк
• Аналогичный результат
можно получить с
помощью
дизъюнктивного
объединения строк
• В текущей строке:
• Игнорируются
диагональные и нулевые
ячейки
• Второй индекс
ненулевой ячейки – это
номер строки, с которой
34
mirea.ru
нужно осуществить

35.

Центр дистанционного обучения
Реализация алгоритма
Уоршелла
• Внешним циклом
перебираем вершины,
которые могут быть
промежуточными
(транзитными)
• Средним циклом
перебираем вершины,
которые могут быть
начальными в 2шагового пути
• Внутренним циклом
перебираем вершины,
35
которые могут быть mirea.ru

36.

Центр дистанционного обучения
Задача поиска кратчайшего пути
на графе
• Наиболее распространённая
задача на взвешенных графах
• Задача находит практическое
применение во множестве
предметных областей
• Пример – железная дорога:
какой маршрут будет самым
экономичным для заданных
начальной и конечной станций
(например, из А в Е)?
• «Кратчайший» - самый
оптимальный по какой-либо
36
mirea.ru
характеристике маршрут

37.

Центр дистанционного обучения
Алгоритм Дейкстры
Эдсгер Вибе Дейкстра (1930-2002) –
нидерландский ученый в области
информатики, разработчик
концепции структурного
программирования, исследователь
формальной верификации и
распределенных вычислений
• Предложен в 1959 г.
• Предназначен для поиска
кратчайшего пути в
ориентированном взвешенном
графе, при условии, что все ребра
в графе имеют неотрицательные
веса
• Позволяет находить кратчайший
путь не только от одной заданной
вершины к другой, но и ко всем
остальным вершинам
• Широко применяется в
программировании и технологиях,
например, в протоколах
маршрутизации.
37
37
mirea.ru

38.

Центр дистанционного обучения
Постановка задачи
• Варианты:
• Найти кратчайшие пути из
текущего города до других
городов
• Найти маршрут минимальной
стоимости
• Граф представлен в виде
небинарной матрицы
смежности
• Формальное определение:
• Дан взвешенный
ориентированный граф G(V,E)
38
без дуг отрицательного
весаmirea.ru

39.

Центр дистанционного обучения
Инициализация
• Каждой вершине из V сопоставим
временную метку —
минимальное известное
расстояние от этой вершины до a
• Метка самой вершины a (вершина
1) полагается равной 0 (источник),
метки остальных вершин —
бесконечности (т.е. расстояния от
a до других вершин пока
неизвестны)
• Все вершины графа помечаются
как непосещённые 39
mirea.ru

40.

Центр дистанционного обучения
Шаг 1.
• Выберем вершину W, которая
имеет минимальную метку
(сейчас это вершина 1)
• Рассмотрим все вершины, в
которые из W есть путь без
посредников (2, 3, 4, 5)
• Каждой из них назначим метку,
равную сумме метки W и длины
пути из W в рассматриваемую
вершину,
• Но только в том случае, если
mirea.ru
полученная сумма 40
будет

41.

Центр дистанционного обучения
Шаг 2.
• Перебрав все вершины, в
которые есть прямой путь из W,
саму W отмечаем как
посещённую
• Выбираем из ещё не
посещенных такую, которая
имеет минимальное значение
метки – она будет следующей
вершиной W (вершины 2 или 5)
• Если есть несколько вершин с
одинаковыми метками, то не
имеет значения, какую из них
41
mirea.ru
выбрать как W – выберем

42.

Центр дистанционного обучения
Шаг 3.
• Рассмотрим все непосещённые
вершины, в которые есть прямые
пути из 5
• Снова находим сумму метки
вершины W и веса ребра из W в
текущую вершину, и если эта
сумма будет меньше предыдущей
метки, то заменяем значение
метки на полученную сумму
• Метки 3 и 4-ой вершин стали
меньше, т.е. был найден более
короткий маршрут в них из
42
mirea.ru
источника

43.

Центр дистанционного обучения
Результат
• Повторяем все
перечисленные действия,
пока есть непосещённые
вершины
• В результате метки будут
равны минимальному
расстоянию от источника
• Время работы алгоритма
зависит от используемого
типа данных (простая
очередь с приоритетом,
43
mirea.ru
бинарная или фибоначчиева

44.

Центр дистанционного обучения
Пример
реализации
на С++
44
mirea.ru

45.

Центр дистанционного обучения
Алгоритм Флойда-Уоршелла
• Динамический алгоритм
для нахождения
кратчайших расстояний
между всеми
вершинами взвешенного
ориентированного графа
без циклов
• Возможны
отрицательные веса
• Р. Флойд, С. Уоршелл
(1962), Б. Рой (1959)
mirea.ru
• Представляет 45
собой

46.

Центр дистанционного обучения
Постановка задачи
• Дан взвешенный
ориентированный граф G(V,E),
в котором вершины
пронумерованы от 1 до n
• Требуется найти матрицу
кратчайших расстояний d, в
которой элемент dij либо
равен длине кратчайшего пути
из i в j, либо равен +∞, если
вершина j не достижима из i
• diuv – длина кратчайшего пути
46 u и v,
mirea.ru
между вершинами

47.

Центр дистанционного обучения
Описание алгоритма
• Перед началом алгоритма матрица d заполняется
длинами рёбер графа (или признаками их
отсутствия):
• d0uv = ωuv – длина ребра, если оно существует
• На каждом шаге алгоритма берётся очередная i-я
вершина, для которой справедливо:
• Кратчайший путь между u, v не проходит через вершину
i, тогда
diuv = di-1uv,
• Существует более короткий путь между u, v, проходящий
через i, тогда он сначала идёт от u до i, потом от i до v:
diuv = di-1ui + di-1iv,
• Тогда кратчайший путь между u, v – это минимум
из двух значений:
47
mirea.ru
i
i-1
i-1
i-1

48.

Центр дистанционного обучения
Псевдокод
d0uv = w;
for i∈V
for u∈V
for v∈V
diuv =min(di-1uv, di-1ui + di-1iv)
• В итоге матрица dn является искомой матрицей
кратчайших путей, поскольку содержит в себе
длины кратчайших путей между всеми парами
вершин, имеющих в качестве промежуточных
вершины из множества {1..n}, т.е. все48вершины mirea.ru
графа

49.

Центр дистанционного обучения
Пример
реализации
на С++
49
mirea.ru

50.

Центр дистанционного обучения
Остовное (стягивающее,
покрывающее) дерево в графе –
• Можно получить из него
удалением некоторых рёбер
• Может существовать
несколько остовных
деревьев
• Во взвешенном графе вес
остовного дерева – это
сумма весов всех его ребёр
• Минимальное остовное
дерево – с минимальным
возможным весом
50
mirea.ru

51.

Центр дистанционного обучения
Пример:
• Есть n городов, их необходимо
соединить дорогами, так, чтобы был
путь из любого города в любой другой
(напрямую или через другие города)
• Разрешается строить дороги между
заданными парами городов и известна
стоимость строительства каждой такой
дороги
• Требуется решить, какие именно
дороги нужно строить, чтобы
минимизировать общую стоимость
строительства.
• В терминах теории графов это
задача о нахождении 51
mirea.ru
минимального остовного дерева в

52.

Центр дистанционного обучения
Решения:
• Алгоритм Прима →
• Алгоритм Краскала
• Алгоритм Борувки
• Алгоритм обратного
удаления.
52
mirea.ru

53.

Центр дистанционного обучения
Алгоритм Прима
• Алгоритм построения
минимального остовного
дерева (МОД) взвешенного
связного неориентированного
графа
• Войцех Ярник (1930), Роберт
Прим (1957), Э. Дейкстра (1959)
• В своей идее похож на алгоритм
Дейкстры
• Сложность зависит от способа
поиска очередного
53 – разные
mirea.ru
минимального ребра

54.

Центр дистанционного обучения
Идея алгоритма Прима
• Дан связный
неориентированный граф
• Если разделить вершины
графа на два множества
(обработанные и
необработанные), первое из
которых составляет связную
часть МОД, то ребро
минимальной длины,
связывающее эти два
множества гарантированно
будет входить в МОД
54
• Тогда для нахождения
МОДmirea.ru

55.

Центр дистанционного обучения
Реализация
алгоритма
Прима
55
mirea.ru

56.

Центр дистанционного обучения
Алгоритм Краскала (Крускала)
• Эффективный алгоритм
построения МОД
взвешенного связного
неориентированного
графа
• Предполагает сортировку
всех рёбер в порядке
возрастания длины и
поочередное добавление
их в МОД, если они
соединяют различные
компоненты связности
56
mirea.ru

57.

Центр дистанционного обучения
Идея алгоритма Краскала
• Пусть есть некоторые рёбра,
входящие в МОД
• Тогда среди всех рёбер,
соединяющих различные
компоненты связности, в МОД
будет входить ребро с
минимальной длиной
• Для реализации алгоритма
необходимо сортировать рёбра
по возрастанию длины и
проверять, соединяет ли ребро
две различных компоненты
57
mirea.ru

58.

Центр дистанционного обучения
Иллюстрация работы алгоритма
58
mirea.ru

59.

Центр дистанционного обучения
Шаги алгоритма Краскала
• Сортировать все
рёбра от малого веса
до высокого
• Взять ребро с
наименьшим весом и
добавить его в МОД
• Если добавление
ребра создало цикл,
то отклонить это
ребро
• Добавлять рёбра, пока
59
mirea.ru
не будут достигнуты

60.

Центр дистанционного обучения
Реализация
алгоритма
60
mirea.ru

61.

Центр дистанционного обучения
Топологическая сортировка
• Это графовый метод,
используемый для
перестановки
(расстановки,
нумерации)
элементов (вершин) в
определённом
порядке, задаваемом
всеми рёбрами
(топологический
порядок)
• Например,61
mirea.ru

62.

Центр дистанционного обучения
Задача
ABEDGCFH
• Условная структура
курсов, необходимых для
получения некой учёной
степени
• Здесь для некоторых
курсов обязательно
прохождение других
курсов
• Представить такую
структуру можно
направленным графом
• Нужно вывести порядок
прохождения курсов для
получения учёной
степени
62
mirea.ru
• Список курсов должен

63.

Центр дистанционного обучения
Топологический порядок –
• Это перестановка вершин
в соответствии с
порядком, задаваемым
всеми рёбрами графа
• Перестановка – требуется
перенумеровать вершины
графа так, чтобы каждое
ребро вело из вершины с
меньшим номером в
вершину с большим
• В примере с учебным
планом – порядок
63
mirea.ru
прохождения курсов

64.

Центр дистанционного обучения
Алгоритмы топологической
сортировки:
• Алгоритм Кана
• Алгоритм Тарьяна
• Алгоритм на основе
поиска в глубину (DFS). →
64
mirea.ru

65.

Центр дистанционного обучения
Алгоритм топологической
сортировки ациклического
графа
• Будем присваивать
номера в убывающем
порядке: от самого
большого к самому
малому, используя
обход в глубину (DFS)
• Начнём с вершины v
• Сначала присвоим
номера всем дочерним
вершинам (рекурсивно),
которые их ещё не
имеют (некоторые уже
Присвоим следующий
номер текущей вершине
v : он будет меньше всех
номеров вершин
поддерева по
определению
Применяем этот алгоритм
для всех вершин, ещё не
посещённых ранее, по
очереди
Вместо явного
65
mirea.ru
присваивания

66.

Центр дистанционного обучения
Реализация
алгоритма
66
mirea.ru

67.

Центр дистанционного обучения
СПАСИБО ЗА ВНИМАНИЕ!
67
mirea.ru