Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему обходЫи каркасы графов

Содержание

План лекцииОбход всех вершин графаМетоды поиска в глубину и в ширинуПостроение каркаса графаАлгоритмы Краскала и Прима-Краскала
обходЫ и каркасы графовЛекциИ 16-17 План лекцииОбход всех вершин графаМетоды поиска в глубину и в ширинуПостроение каркаса графаАлгоритмы Краскала и Прима-Краскала Поиск в глубину (Depth-First Search, DFS)Один из способов нумерации вершин произвольного графаАлгоритмы Поиск в глубину (Depth-First Search, DFS)Поиск в глубину вычисляет для каждой вершины Поиск в глубинуПоиск(u) { color[u] = серый; d[u]=time++; for (u, v) Подграф предшествованияДля каждого белого соседа v вершины uΠ[v] = uПоиск(v)Красим u в Сложность поиска в глубину по времениДля простоты считаем, что время работы пропорционально Свойства поиска в глубинуВремена обнаружения и окончания обработки вершин d[u] и f[u] Теорема о свойствах поиска в глубинуНомера d[u], f[u], d[v], f[v] любых двух ZwS xyu vTКлассификация рёбер графа при поиске в глубинуДревесные рёбравходят в граф Метод поиска в ширину (BFS, Breadth-first search)Один из способов нумерации вершин произвольного Метод поиска в ширину (BFS, Breadth-first search)Пусть дан граф G и выбрана Алгоритм BFS BFS (G, s) { 1 for u  V Свойства поиска в ширину --кратчайшие путиПусть δ(s,v) минимальная длина пути из вершины Теорема о поиске в ширинуДля любого целого k >= 0 найдётся шаг Печать кратчайших путейvoid Print_Path(const int parent[], int s, int v){ if (s Каркасы графаG(V,E) -- связный неориентированный графВеса рёбер w : E --> R+ Алгоритм КрáскалаJosef Bernard Kruskal Jr. 1928-2010Алгоритм Краскала 1956 годJoseph. B. Kruskal: On Алгоритм Краскала – схема Строим остовный лес К = (V, В) для Алгоритм Краскала – псевдо код Вход Неориентированный граф G = (V, Е) с Число операций в алгоритме КраскалаСортировка рёбер = O(|E|*log|E|) Цикл = O(|E| * 13492317Пример Система непересекающихся множеств (СНМ)Разбиение конечного множества носителя на попарно непересекающиеся подмножестваОперации СНМ Реализации СНМ1) Простая реализациядля каждого элемента храним его Реализации СНМ4) Реализация с помощью дерева для каждого элемента храним его предка главным элементом Реализации СНМ – объединение по рангу5) Эвристика объединением по рангу Храним ранг ....Реализации СНМ – объединение по рангу + сжатие путей6) Эвристика сжатия путей: Функция АккерманаОпределение – один из вариантовA [ 0, j ] = j+1A Версия 1#define SNM_MAXstatic int p[SNM_MAX], rank[SNM_MAX];void initset(){ int i; for (i = 0; i Версия 2#define SNM_MAX 1000static int parent[SNM_MAX], rank[SNM_MAX];void init_set(){ int i; for (i = 0; Версия 3#define SNM_MAX 1000static int parent[SNM_MAX], rank[SNM_MAX];// СНМ, состоящее из одноэлементных подмножеств Версия 4#define SNM_MAX 1000static int parent[SNM_MAX], rank[SNM_MAX];// СНМ, состоящее из одноэлементных подмножеств Версия 5#define SNM_MAX 1000struct SNM {int parent[SNM_MAX], rank[SNM_MAX];};// СНМ, состоящее из одноэлементных Версия 6#define SNM_MAX 1000struct SNM {int parent[SNM_MAX], rank[SNM_MAX];};// СНМ, состоящее из одноэлементных Алгоритм Прима-КраскалаRobert Clay Prim 1921Алгоритм Прима (иногда Прима-Краскала)R. C. Prim: Shortest connection Алгоритм Прима-Краскала -- схема Выбираем произвольную вершину s -- корень остовного дерева;До Алгоритм Прима-Краскала -- схема Вход Неориентированный граф G = (V, Е) с весами Число операций в алгоритме ПримаO(|V|* (число операций для поиска min + число Алгоритма Прима-Краскала Сvoid mst(int G[], int N, int parent[]) // N -- Алгоритма Прима-Краскала Сvoid mst(const int G[], int N, int parent[]) // N Доказательство корректности алгоритмов построения каркасаВершины в построенной части каркаса красныеОстальные вершины синиеСрез ЗаключениеОбход всех вершин графаМетоды поиска в глубину и в ширинуПостроение каркаса графаАлгоритмы Краскала и Прима-Краскала 10236185749111222343344555Запускаем алгоритм обхода графа, начиная с произвольной вершины. В качестве контейнера выбираем Реализация за O (M log N + N2)Отсортируем все рёбра в списках Алгоритм Прима (другой алгоритм)На каждом шаге вычеркиваем из графа дугу максимальной стоимости Примерм113492317201536252816 Если в качестве промежуточной структуры хранения при обходе использовать стек, то Использование очередиВ качестве промежуточной структуры хранения при обходе в ширину будем Нахождение кратчайшего пути в лабиринте12222233445566778899101111121213131314141415151516161717171818181919191919202020Пометить числом 1 и поместить Реализация алгоритмаВведем массив меток вершин графа Mark. Начальные значения элементов массива равны Реализации СНМ на Си – объединение по рангу + сжатие путейОписание алгоритма FindSet (X) Будем двигаться от X по предкам, до тех пор пока Union (X, Y) Сначала заменяем элементы X и Y на представителей их void unite (int x, int y) { x = find_set Реализация со случайным выбором родительского узла void unite (int x, int y) Алгоритм Краскала с системой непересекающихся множеств Так же, как и в
Слайды презентации

Слайд 2 План лекции
Обход всех вершин графа
Методы поиска в глубину

План лекцииОбход всех вершин графаМетоды поиска в глубину и в ширинуПостроение каркаса графаАлгоритмы Краскала и Прима-Краскала

и в ширину
Построение каркаса графа
Алгоритмы Краскала и Прима-Краскала

Слайд 3 Поиск в глубину (Depth-First Search, DFS)
Один из способов

Поиск в глубину (Depth-First Search, DFS)Один из способов нумерации вершин произвольного

нумерации вершин произвольного графа
Алгоритмы обработки графов
Топологическая сортировка
Поиск 1-, 2-,

3-связнных компонент
Поиск мостов
Поиск сильно связанных компонент
Проверка планарности
Компиляция программ, комбинаторный поиск, компьютерная алгебра

Слайд 4 Поиск в глубину (Depth-First Search, DFS)
Поиск в глубину

Поиск в глубину (Depth-First Search, DFS)Поиск в глубину вычисляет для каждой

вычисляет для каждой вершины u три номера
П[u] предшественика вершины

u при поиске в глубину
d[u] время обнаружения вершины u
f[u] время окончания обработки вершины u
Схема алгоритма
В начале все вершины непройденные и становятся пройденными в процессе поиска в глубину
Для каждой непройденной вершины u
Для каждой непройденной вершины v, смежной с вершиной u
Поиск в глубину (v)

Слайд 5 Поиск в глубину
Поиск(u) { color[u] = серый; d[u]=time++; for (u,

Поиск в глубинуПоиск(u) { color[u] = серый; d[u]=time++; for (u, v)

v)  E if(color[v] == белый) { Π[v] =

u; Поиск(v); } color[u] = черный; f[u]=time++; }

6

2

3

1

5

4

DFS(G) {
for u  V {
color[u] = белый;
Π[u] = u;
}
time = 0;
for u  V
if(color[u] == белый)
Поиск(u);
}

Как соотносятся цвета на рисунке и в описании?
Какой цвет лишний?

Слайд 6 Подграф предшествования
Для каждого белого соседа v вершины u
Π[v]

Подграф предшествованияДля каждого белого соседа v вершины uΠ[v] = uПоиск(v)Красим u

= u
Поиск(v)
Красим u в черный цвет, возвращаемся в П[u]

и ищем другого белого соседа П[u], и т.д.
Π – представление списком прямых предков дерева (леса) поиска в глубину графа G

Подграф предшествования EΠ графа GΠ = (V, EΠ):
EΠ = { (Π[v], v) | Π[v] ≠ v }

Если G является связным, то GΠ называются каркасом (остовным деревом) графа G

Слайд 7 Сложность поиска в глубину по времени
Для простоты считаем,

Сложность поиска в глубину по времениДля простоты считаем, что время работы

что время работы пропорционально числу операций
присваивания, сравнения, доступ к

элементам массивов занимают единицу времени
Время поиска в глубину = время работы DFS() + ∑ время работы Поиск(u)
для каждой вершины Поиск() исполняется 1 раз – почему?
Время работы DFS() = O(|V|)
Время работы Поиск(u) = O(|E(u)|)
Время поиска в глубину = O(|V|) + ∑ O(|E(u)|) = O(|V|+|E|)

Слайд 8 Свойства поиска в глубину
Времена обнаружения и окончания обработки

Свойства поиска в глубинуВремена обнаружения и окончания обработки вершин d[u] и

вершин d[u] и f[u] образуют правильную скобочную структуру


w
Z
S
x
y
1 2

3 4 5 6 7 8 9 10
(s(z(y(xx)y) (ww)z)s)

Слайд 9 Теорема о свойствах поиска в глубину
Номера d[u], f[u],

Теорема о свойствах поиска в глубинуНомера d[u], f[u], d[v], f[v] любых

d[v], f[v] любых двух вершин u и v графа

G, полученные поиском в глубину, удовлетворяют одному из условий:

Отрезки [d[u],f[u]] и [d[v],f[v]] не пересекаются

Отрезок [d[u],f[u]]  [d[v],f[v]] и u есть потомок v в графе поиска в глубину графа G

Отрезок [d[v],f[v]]  [d[u],f[u]] и v есть потомок u в графе поиска в глубину графа G


Слайд 10 Z
w
S
x
y
u

v
T
Классификация рёбер графа при поиске в

ZwS xyu vTКлассификация рёбер графа при поиске в глубинуДревесные рёбравходят в

глубину
Древесные рёбра
входят в граф предшествования
Прямые рёбра
соединяют вершину с её

потомком, но не входят в граф предшествования
Обратные рёбра
соединяют вершину с её предком в графе предшествования
Перекрёстные рёбра
все остальные

Слайд 11 Метод поиска в ширину (BFS, Breadth-first search)
Один из

Метод поиска в ширину (BFS, Breadth-first search)Один из способов нумерации вершин

способов нумерации вершин произвольного графа
Алгоритмы обработки графов
Поиск кратчайших путей
Вычисление

максимального потока
Проверка связности
Компьютерное моделирование, графические интерфейсы, анализ транспортных, электрических и т.п. цепей и сетей

Слайд 12 Метод поиска в ширину (BFS, Breadth-first search)
Пусть дан

Метод поиска в ширину (BFS, Breadth-first search)Пусть дан граф G и

граф G и выбрана некоторая его вершина s
Поиск в

ширину вычисляет для каждой вершины u два номера
П[u] предшественика вершины u при поиске в ширину
d[u] кратчайшее расстояние от s до u

Схема алгоритма
Шаг 1: d[s] = 0
Шаг n: обрабатываем все вершины на расстоянии n-1 от s
Каждого соседа v вершины u с пометкой d[u] = n-1 нумеруем П[v] = u и d[v] = n

Слайд 13 Алгоритм BFS
BFS (G, s) { 1 for

Алгоритм BFS BFS (G, s) { 1 for u  V

u  V && u != s { 2 П[u]

= u; 3 d[u] = ∞; 4 } 5 d[s] = 0, П[s] = s; 6 put(s, Q); 7 while (! empty(Q)) { 8 u = get(Q); 9 for v  E(u) { 10 if (d[v] > d[u]+1) { 11 Π[v]= u; 12 d[v]= d[u]+1; 13 put(v,Q); 14 }} 15 }
}


Слайд 14 Свойства поиска в ширину --кратчайшие пути
Пусть δ(s,v) минимальная

Свойства поиска в ширину --кратчайшие путиПусть δ(s,v) минимальная длина пути из

длина пути из вершины s в вершину v
Лемма 1.

Пусть s – произвольная вершина графа, (u, v) – ребро.
Тогда δ(s, v) ≤ δ(s, u) + 1.
Доказательство. Если u достижима за k шагов, то и v достижима не более чем за k + 1 шагов.
Лемма 2. Если s != v, то δ(s, v) = δ(s, u) + 1 для некоторого соседа u вершины v
Доказательство. Рассмотрим кратчайший путь из s в v. Его длина δ(s, v). Возьмем вершину u, лежащую на этом пути непосредственно перед v. Убедимся, что до нее расстояние на единицу меньше. У нас есть ведущий в нее путь длины δ(s, v) – 1. Более короткого пути не может быть по лемме 1.


Слайд 15 Теорема о поиске в ширину
Для любого целого k

Теорема о поиске в ширинуДля любого целого k >= 0 найдётся

>= 0 найдётся шаг BFS, когда очередь Q состоит

из вершин, находящихся на расстоянии k от вершины s
Если d[v] != ∞, то δ(s, Π[v]) +1 = δ(s, v) = d[v], и в графе есть ребро (Π[v], v)
Если d[v] == ∞, то Π[v] = v
Доказательство
Если k=0, то все условия выполняются в строке 6
Пусть k > 0.
Дождёмся, когда выполнятся условия для k-1 – это возможно по предположению индукции.
Очередь Q состоит из вершин, находящихся на расстоянии k-1 от вершины s.
Условия выполнятся для k, когда из очереди будет изъята последняя вершина на расстоянии k-1 от вершины s.
Из п. 1 следуют п. 2 и п. 3, т.к. в очередь добавляются соседи вершин, (k-1)-удалённых от s.

Чем ограничены сверху длины кратчайших путей в G?

Когда в очереди находятся вершины, удалённые от s на |V|?

Слайд 16 Печать кратчайших путей
void Print_Path(const int parent[], int s,

Печать кратчайших путейvoid Print_Path(const int parent[], int s, int v){ if

int v)
{
if (s == v) printf("%d ", s);
else

if (parent[v] == v)
printf("No Path");
else {
Print_Path(parent, s, parent[v]);
printf("%d", v);
}
}

Слайд 17 Каркасы графа
G(V,E) -- связный неориентированный граф
Веса рёбер w

Каркасы графаG(V,E) -- связный неориентированный графВеса рёбер w : E -->

: E --> R+ = [0,)

Остовное дерево или каркас

графа – это подграф G, который содержит все вершины графа и является деревом

Минимальным каркасом называется такой каркас, сумма весов ребер которого минимальна







Слайд 18 Алгоритм Крáскала
Josef Bernard Kruskal Jr. 1928-2010

Алгоритм Краскала 1956

Алгоритм КрáскалаJosef Bernard Kruskal Jr. 1928-2010Алгоритм Краскала 1956 годJoseph. B. Kruskal:

год
Joseph. B. Kruskal: On the Shortest Spanning Subtree of

a Graph and the Traveling Salesman Problem. In: Proceedings of the American Mathematical Society, Vol 7, No. 1 (Feb, 1956), pp. 48–50

Поиск минимального остовного дерева графа

Слайд 19 Алгоритм Краскала – схема
Строим остовный лес К

Алгоритм Краскала – схема Строим остовный лес К = (V, В)

= (V, В) для данного графа G = (V,

E) с весами ребер w
Сортируем ребра E по возрастанию w
В = ; // начинаем с пустого множества ребер
В порядке возрастания весов w(e) ребер е графа G выполняем
если добавление е к К не образует цикл в К, то добавляем е в К
если добавление е к К образует цикл в К, то не добавляем е в К

Проверка того, замыкает ли ребро цикл
Делим множество вершин V на компоненты связности Wi --максимальные по включению попарно непересекающиеся подмножества, состоящие из вершин, связанных лесом К
V = W0  W1  …  Wx
Wi  Wj = 
для любых х и у из Wi х и у связаны путём в К
если х и у связаны путём в К, то х и у принадлежат одному Wi

Слайд 20 Алгоритм Краскала – псевдо код
Вход
Неориентированный граф G

Алгоритм Краскала – псевдо код Вход Неориентированный граф G = (V, Е)

= (V, Е) с весами ребер w
Выход
Остовное дерево К

= (V, В) наименьшего веса для графа G

B = ; // начинаем с пустого каркаса
W = { {v} | v V } ; // каждая вершина v в своей компоненте связности
Q = очередь(сортировать по возрастанию весов(Е));
while (! empty(Q)) {
(x, y) = get(Q); // ребро наименьшей стоимости
Wx = find(x, W); // найти компоненты связности содержашие х и у
Wy = find(y, W);
if (Wx != Wy) { // (x, y) не замыкает цикл в К
W = W - Wx - Wy + (Wx  Wy);
K = K + (x, y);
}
}

Слайд 21 Число операций в алгоритме Краскала
Сортировка рёбер = O(|E|*log|E|)

Число операций в алгоритме КраскалаСортировка рёбер = O(|E|*log|E|) Цикл = O(|E|


Цикл = O(|E| * число операций в find и

)
Зависит от реализации операций find и 
Для системы непересекающихся множеств find и  занимают практически О(1) действий



Слайд 22 1
3
4
9
23
17
Пример

13492317Пример

Слайд 23 Система непересекающихся множеств (СНМ)
Разбиение конечного множества носителя на

Система непересекающихся множеств (СНМ)Разбиение конечного множества носителя на попарно непересекающиеся подмножестваОперации

попарно непересекающиеся подмножества
Операции СНМ (носитель фиксирован)
InitSet(S)
Создает СНМ, состоящее из

одноэлементных подмножеств носителя
FindSet(S, X)
Возвращает главный элемент множества, которому принадлежит X в СНМ S
Join(S, X, Y)
Объединяет множества, которым принадлежат элементы X и Y в СНМ S, и возвращает главный элемент нового множества

Слайд 24 Реализации СНМ
1) Простая реализация
для каждого элемента храним его

Реализации СНМ1) Простая реализациядля каждого элемента храним его

"цвет"
FindSet (S, X) – O(1); Join (S, X, Y)

– O(n)

2) Реализация списком
FindSet (S, X) - O(n); Join (S, X, Y) - O(1)

3) Весовая эвристика (улучшение простой реализации)
для каждого элемента храним число элементов этого цвета
перекрашиваем элементы из множества меньшей мощности
FindSet (S, X) - O(1);
суммарное число операций в Join (S, X, Y) до тех пор, пока все множества не объединятся в одно - O(n log n)

Почему n log(n)?

Слайд 25 Реализации СНМ
4) Реализация с помощью дерева
для каждого элемента

Реализации СНМ4) Реализация с помощью дерева для каждого элемента храним его предка главным

храним его предка
главным элементом множества является корень дерева
FindSet (S,

X) - O(n); Join (S, X, Y) - O(1)
Худший случай, когда дерево вытягивается в список


Глубина дерева может расти слишком быстро

Слайд 26 Реализации СНМ – объединение по рангу
5) Эвристика объединением

Реализации СНМ – объединение по рангу5) Эвристика объединением по рангу Храним

по рангу
Храним ранг каждого главного элемента – высоту

его поддерева
Ранг СНМ – max рангов главных элементов
Объединяем деревья рангов < ранг СНМ -> ранг СНМ не меняется
Объединяем деревья одинакового ранга == ранг СНМ -> ранг СНМ увеличивается на единицу.
FindSet (S, X) - O(log n); Union (S, X, Y) - O(1)

Слайд 27 ....
Реализации СНМ – объединение по рангу + сжатие

....Реализации СНМ – объединение по рангу + сжатие путей6) Эвристика сжатия

путей
6) Эвристика сжатия путей:
FindSet (S, X) делает все

элементы на пути от Х до главного элемента для Х непосредственными потомками этого главного элемента – см. рисунок ниже
FindSet (S, X) - O(обратная функция Аккермана)
для 64-битных целых чисел обратная функция Аккермана ≤ 4
определение на следующем слайде
Union (S, X, Y) - O(1)


Слайд 28 Функция Аккермана
Определение – один из вариантов
A [ 0,

Функция АккерманаОпределение – один из вариантовA [ 0, j ] =

j ] = j+1
A [ i, 0 ] =

A[ i-1, 1 ] , если i > 0
A [ i, j ] = A[ i-1, A[ i, j -1] ], если i, j > 0
Обратная функция Аккермана
f-1[x] = min { k >= 1 | A[ k, k ] >= x }
Wikipedia
сложность A(1,n) O(n)
сложность A(2,n) O(n^2)
сложность A(3,n) O(4^n)
A[ 4, 4 ] ~= 2^(2^(10^19729))

Слайд 29 Версия 1
#define SNM_MAX
static int p[SNM_MAX], rank[SNM_MAX];

void initset()
{ int i;
for

Версия 1#define SNM_MAXstatic int p[SNM_MAX], rank[SNM_MAX];void initset(){ int i; for (i = 0;

(i = 0; i < SNM_MAX; ++i) p[i] =

i, rank[i] = 0;
}
int find_set(int x)
{ if (x == p[x]) return x;
return p[x] = find_set(p[x]);
}
void join(int x, int y)
{ x = find_set(x);
y = find_set(y);
if (rank[x] > rank[y]) p[y] = x;
else { p[x] = y;
if (rank[x] == rank[y])
++rank[y];
}
}

Слайд 30 Версия 2
#define SNM_MAX 1000
static int parent[SNM_MAX], rank[SNM_MAX];

void init_set()
{ int

Версия 2#define SNM_MAX 1000static int parent[SNM_MAX], rank[SNM_MAX];void init_set(){ int i; for (i =

i;
for (i = 0; i < SNM_MAX; ++i) parent[i]

= i, rank[i] = 0;
}

int find_set(int x)
{ if (x == parent[x]) return x;
return parent[x] = find_set(parent[x]);
}

void join(int x, int y)
{ x = find_set(x);
y = find_set(y);
if (rank[x] > rank[y]) parent[y] = x;
else { parent[x] = y;
if (rank[x] == rank[y])
++rank[y];
}
}

Слайд 31 Версия 3
#define SNM_MAX 1000
static int parent[SNM_MAX], rank[SNM_MAX];
// СНМ,

Версия 3#define SNM_MAX 1000static int parent[SNM_MAX], rank[SNM_MAX];// СНМ, состоящее из одноэлементных

состоящее из одноэлементных подмножеств носителя
void init_set()
{ int i;
for (i =

0; i < SNM_MAX; ++i) parent[i] = i, rank[i] = 0;
}
// Главный элемент множества, которому принадлежит X
int find_set(int x)
{ if (x == parent[x]) return x;
return parent[x] = find_set(parent[x]); // сжатие
}
// Объединяет множества, которым принадлежат элементы X и Y
// Возвращает главный элемент нового множества
void join(int x, int y)
{ x = find_set(x);
y = find_set(y);
if (rank[x] > rank[y]) parent[y] = x;
else { parent[x] = y;
if (rank[x] == rank[y])
++rank[y];
}
}

Слайд 32 Версия 4
#define SNM_MAX 1000
static int parent[SNM_MAX], rank[SNM_MAX];
// СНМ,

Версия 4#define SNM_MAX 1000static int parent[SNM_MAX], rank[SNM_MAX];// СНМ, состоящее из одноэлементных

состоящее из одноэлементных подмножеств носителя
void init_set()
{ int i;
for (i =

0; i < SNM_MAX; ++i) parent[i] = i, rank[i] = 0;
}
// Главный элемент множества, которому принадлежит X
int find_set(int x)
{ if (x == parent[x]) return x;
return parent[x] = find_set(parent[x]); // сжатие
}
// Объединяет множества, которым принадлежат элементы X и Y
// Возвращает главный элемент нового множества
int join(int x, int y)
{ x = find_set(x);
y = find_set(y);
if (rank[x] > rank[y]) return parent[y] = x;
else { parent[x] = y;
if (rank[x] == rank[y]) ++rank[y];
return y;
}
}

Слайд 33 Версия 5
#define SNM_MAX 1000
struct SNM {int parent[SNM_MAX], rank[SNM_MAX];};
//

Версия 5#define SNM_MAX 1000struct SNM {int parent[SNM_MAX], rank[SNM_MAX];};// СНМ, состоящее из

СНМ, состоящее из одноэлементных подмножеств носителя
void init_set(struct SNM *S)
{ int

i;
for (i = 0; i < SNM_MAX; ++i) S->parent[i] = i, S->rank[i] = 0;
}
// Главный элемент множества, которому принадлежит X
int find_set(struct SNM *S, int x)
{ if (x == S->parent[x]) return x;
return S->parent[x] = find_set(S->parent[x]); // сжатие
}
// Объединяет множества, которым принадлежат элементы X и Y
// Возвращает главный элемент нового множества
int join(struct SNM *S, int x, int y)
{ x = find_set(x);
y = find_set(y);
if (S->rank[x] > S->rank[y]) return S->parent[y] = x;
else { S->parent[x] = y;
if (S->rank[x] == S->rank[y]) ++ (S->rank[y]);
return y;
}
}

Слайд 34 Версия 6
#define SNM_MAX 1000
struct SNM {int parent[SNM_MAX], rank[SNM_MAX];};
//

Версия 6#define SNM_MAX 1000struct SNM {int parent[SNM_MAX], rank[SNM_MAX];};// СНМ, состоящее из

СНМ, состоящее из одноэлементных подмножеств носителя
void init_set(struct SNM *S)
{ int

i;
for (i = 0; i < SNM_MAX; ++i) S->parent[i] = i, S->rank[i] = 0;
}
// Главный элемент множества, которому принадлежит X
int find_set(struct SNM *S, int x)
{ if (x == S->parent[x]) return x;
return S->parent[x] = find_set(S, S->parent[x]); // сжатие
}
// Объединяет множества, которым принадлежат элементы X и Y
// Возвращает главный элемент нового множества
int join(struct SNM *S, int x, int y)
{ x = find_set(S, x);
y = find_set(S, y);
if (S->rank[x] > S->rank[y]) return S->parent[y] = x;
else { S->parent[x] = y;
if (S->rank[x] == S->rank[y]) ++ (S->rank[y]);
return y;
}
}

Слайд 35 Алгоритм Прима-Краскала
Robert Clay Prim 1921

Алгоритм Прима (иногда Прима-Краскала)
R.

Алгоритм Прима-КраскалаRobert Clay Prim 1921Алгоритм Прима (иногда Прима-Краскала)R. C. Prim: Shortest

C. Prim: Shortest connection networks and some generalizations. In:

Bell System Technical Journal, 36 (1957), pp. 1389–1401
Похожие алгоритмы предложены Войцехом Ярником (1930) и Дейкстрой (1959)

Построение минимального каркаса связного взвешенного графа


Слайд 36 Алгоритм Прима-Краскала -- схема
Выбираем произвольную вершину s --

Алгоритм Прима-Краскала -- схема Выбираем произвольную вершину s -- корень остовного

корень остовного дерева;
До тех пор пока в дерево не

добавлены все вершины /* Находим минимальное расстояние от дерева до вершин, которые не включены в дерево */
найти вершину u, расстояние от дерева до которой минимально
добавить u к дереву (красим в синий цвет)
если расстояние до какой-либо вершины от u меньше текущего расстояния s от дерева, то в s записывается новое расстояние

Слайд 37 Алгоритм Прима-Краскала -- схема
Вход
Неориентированный граф G = (V,

Алгоритм Прима-Краскала -- схема Вход Неориентированный граф G = (V, Е) с

Е) с весами ребер w
Выход
Остовное дерево К = (V,

В) наименьшего веса для графа G

красные = {s}; // начинаем с одной вершины s без ребер
d[x] = w[s][x]; // расстояние от х до ближайшей вершины в каркасе
while не все вершины красные {
x* = min { d[x] | x  красные }; // самое короткое ребро
красные = красные U {x*}; // красим...
d[y] = min (d[y], w[x*][y]) для y  красные
}



Слайд 38 Число операций в алгоритме Прима
O(|V|* (число операций для

Число операций в алгоритме ПримаO(|V|* (число операций для поиска min +

поиска min + число операций для обновления d) )

В

худшем случае O(|V|*|V|)
Зависит от реализации поиска min и обновления d

Слайд 39 Алгоритма Прима-Краскала С
void mst(int G[], int N, int

Алгоритма Прима-Краскала Сvoid mst(int G[], int N, int parent[]) // N

parent[]) // N -- число вершин в графе { int *d

= calloc(sizeof(*d), 2*N), *red = d+N, i, j; for (i = 0; i < N; ++i) parent[i] = i, d[i] = G[0*N+i]; d[0] = 0; red[0] = 1; // Вершина 0 -- корень каркаса for (i = 0; i < N; ++i) { int jmin = -1; for (j = 0; j < N; ++j) if (!red[j] && (jmin == -1 || d[j] <= d[jmin])) jmin = j; if (jmin == -1) break; // Нет достижимых вершины вне дерева red[jmin] = 1; // Включаем в дерево for (j = 0; j < N; ++j) // Обновляем расстояния до соседей jmin if (!red[j] && d[jmin]+G[j*N+jmin] < d[j]) { d[j] = d[jmin]+G[j*N+jmin]; parent[j] = jmin; }}
}

Слайд 40 Алгоритма Прима-Краскала С
void mst(const int G[], int N,

Алгоритма Прима-Краскала Сvoid mst(const int G[], int N, int parent[]) //

int parent[]) // N -- число вершин в графе { int

*d = calloc(sizeof(*d), 2*N), *red = d+N, i; if (d == 0) return; for (i = 0; i < N; ++i) parent[i] = i, d[i] = G[0*N+i]; d[0] = 0; red[0] = 1; // Вершина 0 -- корень каркаса for (i = 0; i < N; ++i) { int jmin = -1, j; for (j = 0; j < N; ++j) if (!red[j] && (jmin == -1 || d[j] <= d[jmin])) jmin = j; if (jmin == -1) break; // Нет достижимых вершин вне дерева red[jmin] = 1; // Включаем в дерево for (j = 0; j < N; ++j) // Обновляем расстояния до соседей jmin if (!red[j] && d[jmin]+G[j*N+jmin] < d[j]) { d[j] = d[jmin]+G[j*N+jmin]; parent[j] = jmin; }} free(d); }

Как использовать mst для проверки связности графа?

Слайд 41 Доказательство корректности алгоритмов построения каркаса
Вершины в построенной части

Доказательство корректности алгоритмов построения каркасаВершины в построенной части каркаса красныеОстальные вершины

каркаса красные
Остальные вершины синие
Срез – множество ребер, соединяющих красные

и синие вершины
На каждом шаге в каркас обязательно включается одно ребро из текущего среза
иначе получится несвязный граф, а не дерево
Если на одном из шагов включить ребро e != emin, то получится каркас, вес которого можно уменьшить
удалим e и добавим emin

Слайд 42 Заключение
Обход всех вершин графа
Методы поиска в глубину и

ЗаключениеОбход всех вершин графаМетоды поиска в глубину и в ширинуПостроение каркаса графаАлгоритмы Краскала и Прима-Краскала

в ширину
Построение каркаса графа
Алгоритмы Краскала и Прима-Краскала

Слайд 43 10
2
3
6
1
8
5
7
4
9
1
1
1
2
2
2
3
4
3
3
4
4
5
5
5
Запускаем алгоритм обхода графа, начиная с произвольной вершины.

10236185749111222343344555Запускаем алгоритм обхода графа, начиная с произвольной вершины. В качестве контейнера


В качестве контейнера выбираем очередь с приоритетами. Приоритет –

текущая
величина найденного расстояния до уже построенной части остовного дерева.
Релаксации подвергаются прямые и обратные ребра.

1

3

1

1

2

2

2

2

2

2

5

4

4

5

3

10

1

3

4

6

3

4

1

9

2

8

В результате работы получаем список ребер остовного дерева вместе с весами

Слайд 44 Реализация за O (M log N + N2)
Отсортируем

Реализация за O (M log N + N2)Отсортируем все рёбра в

все рёбра в списках смежности каждой вершины по увеличению
веса

– O (M log N)).
Для каждой вершины заведем указатель, указывающий на первое доступное
ребро в её списке смежности. Изначально все указатели указывают на начала
списков.
На i-ой итерации перебираем все вершины, и выбираем наименьшее по весу
ребро среди доступных. Поскольку всё рёбра уже отсортированы по весу, а
указатели указывают на первые доступные рёбра, то выбор наименьшего
ребра осуществится за O (N).
После этого обновляем указатели (сдвигаем вправо), т.к. некоторые из них
указывают на ставшие недоступными рёбра (оба конца которых оказались
внутри дерева).
На поддержание работы указателей требуется O (M) действий.

Слайд 45 Алгоритм Прима (другой алгоритм)
На каждом шаге вычеркиваем из

Алгоритм Прима (другой алгоритм)На каждом шаге вычеркиваем из графа дугу максимальной

графа дугу максимальной стоимости с тем условием, что она

не разрывает граф на две или более компоненты связности, т.е. после удаления дуги граф должен оставаться связным.

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

Условие окончания алгоритма?
Например, пока количество ребер больше либо равно количеству вершин, нужно продолжать,
иначе – остановиться.

Слайд 46 Пример
м1
1
3
4
9
23
17
20
15
36
25
28
16

Примерм113492317201536252816

Слайд 47 Если в качестве промежуточной структуры хранения при обходе

Если в качестве промежуточной структуры хранения при обходе использовать стек, то

использовать стек, то получим обход в глубину.
1
2
3
4
6
7
5
8
Граф:
1
5
8
7
6
4
3
2
Можно также получить дерево

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

1

2

3

4

5

6

7

8

1

1

1

5

5

7

6

4

4

3

1

2

3

4

5

6

7

8

Использование стека для обхода графа

Слайд 48 Использование очереди
В качестве промежуточной структуры хранения при обходе

Использование очередиВ качестве промежуточной структуры хранения при обходе в ширину будем

в ширину будем
использовать очередь.
1
2
3
4
6
7
5
8
Граф:
1
Можно также получить дерево обхода

в ширину, если отмечать каждую прямую дугу.

1

1

2

1

1

4

5

5

2

3

4

5

6

7

8

4

2

3

5

7

6

8

Слайд 49 Нахождение кратчайшего пути в лабиринте
1
2
2
2
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
11
11
12
12
13
13
13
14
14
14
15
15
15
16
16
17
17
17
18
18
18
19
19
19
19
19
20
20
20
Пометить числом 1 и

Нахождение кратчайшего пути в лабиринте12222233445566778899101111121213131314141415151516161717171818181919191919202020Пометить числом 1 и поместить


поместить входную клетку в

очередь.
Взять из очереди клетку.
Если это выходная клетка, то
перейти на шаг 4, иначе
пометить все непомеченные
соседние клетки числом ,
на 1 большим, чем данная,
и поместить их в очередь.
Если очередь пуста, то выдать
«Выхода нет» и выйти, иначе
перейти на шаг 2.
Обратный ход:
начиная с выходной клетки,
каждый раз смещаться на
клетку, помеченную на 1
меньше, чем текущая, пока не
дойдем до входной клетки.
При проходе выделять
пройденные клетки.

Слайд 50
Реализация алгоритма

Введем массив меток вершин графа Mark.
Начальные

Реализация алгоритмаВведем массив меток вершин графа Mark. Начальные значения элементов массива

значения элементов массива равны номерам
соответствующих вершин (Mark[i] = i;

i  1.. N).

Ребро выбирается в каркас в том случае, если вершины,
соединяемые им, имеют разные значения меток.

Пример приведен на следующем слайде,
изменения Mark показаны в таблице.

Слайд 51

Слайд 52 Реализации СНМ на Си – объединение по рангу

Реализации СНМ на Си – объединение по рангу + сжатие путейОписание

+ сжатие путей
Описание алгоритма 6.
Пусть элементы X - это

некоторые числа. Вся структура данных
хранится в виде двух массивов: P и Rank.

Массив P содержит предков, т.е. P[x] - это предок элемента x.
Т.о., мы имеем древовидную структуру данных: двигаясь по
предкам от любого элемента х, придём к представителю
множества, к которому принадлежит х.
Если P[X] = X, то это означает, что x является представителем
множества, к которому он принадлежит, и корнем дерева.

Массив Rank хранит ранги представителей, его значения имеют
cмысл только для элементов-представителей.
Ранг некоторого элемента-представителя x - это верхняя
граница его высоты в его дереве. Ранги используются в
операции Union.

Слайд 53 FindSet (X) Будем двигаться от X по предкам, до

FindSet (X) Будем двигаться от X по предкам, до тех пор

тех пор пока не найдём представителя. У каждого элемента,

который мы проходим, мы также исправляем P, указывая его сразу на найденного представителя.
Т.е. фактически операция FindSet двухпроходная: на первом проходе мы ищем представителя, а на втором исправляем значения P.

int find_set (int x) {
if (x == p[x]) return x;
return p[x] = find_set (p[x]);
}

Слайд 54 Union (X, Y)
Сначала заменяем элементы X и Y

Union (X, Y) Сначала заменяем элементы X и Y на представителей

на представителей
их множеств, вызывая функцию FindSet.
Объединяем два

множества, присваивая P[X] = Y или P[Y] = X:

- если ранги элементов X и Y отличны, то мы делаем корень с
бо'льшим рангом родительским по отношению к корню с
меньшим рангом.

- если же ранги обоих элементов совпадают, родитель выбирается
произвольным образом, его ранг увеличивается на 1.

Слайд 55 void unite (int x, int y) {

void unite (int x, int y) { x = find_set

x = find_set (x);
y =

find_set (y);
if (rank[x] > rank[y]) p[y] = x;
else {
p[x] = y;
if (rank[x] == rank[y])
++rank[y];
}
}

Слайд 56 Реализация со случайным выбором родительского узла

void unite

Реализация со случайным выбором родительского узла void unite (int x, int

(int x, int y) {
x = find_set (x);


y = find_set (y);
if (rand() & 1) p[y] = x;
else p[x] = y;
}
  • Имя файла: obhodyi-karkasy-grafov.pptx
  • Количество просмотров: 107
  • Количество скачиваний: 0
- Предыдущая The brain
Следующая - Физика Радиоактивность

Похожие презентации

Игра-презентация угадай что спрятано тренажёр (средняя, старшая, подготовительная группа) Игра-презентация угадай что спрятано тренажёр (средняя, старшая, подготовительная группа) 129
Анна Ахматова Анна Ахматова 101
После бала После бала 90
Оценка персонала: Анкеты и сравнительные оценки Оценка персонала: Анкеты и сравнительные оценки 95
Джамалдинова М.Д., к.э.н., доцент ОЦЕНКА БИЗНЕСА И УПРАВЛЕНИЕ СТОИОМСТЬЮ КОМПАНИИ  Джамалдинова М.Д., к.э.н., доцент ОЦЕНКА БИЗНЕСА И УПРАВЛЕНИЕ СТОИОМСТЬЮ КОМПАНИИ  96
ПК 4.5. Методические разработки исследовательской деятельности учебно-методический материал по теме ПК 4.5. Методические разработки исследовательской деятельности учебно-методический материал по теме 98
Мастер - класс по технологии Французские мастерские презентация к уроку (подготовительная группа) по теме Мастер - класс по технологии Французские мастерские презентация к уроку (подготовительная группа) по теме 132
Проект на тему:Классификация и характеристика услуг питания ресторана, бара, кафе, столовой и закусочной Проект на тему:Классификация и характеристика услуг питания ресторана, бара, кафе, столовой и закусочной 111
Значение математики древней и средневековой Индии. Значение математики древней и средневековой Индии. 98
Выступление на 9 Конференции Лидеров образования презентация к уроку Выступление на 9 Конференции Лидеров образования презентация к уроку 87
Готовность ребёнка к школе презентация к уроку (1 класс) по теме Готовность ребёнка к школе презентация к уроку (1 класс) по теме 46
Проект Нарядная клумба презентация к уроку (2 класс) по теме Проект Нарядная клумба презентация к уроку (2 класс) по теме 110
Мастер-класс по теме Создание классной газеты в программе Microsoft Office Publisher 2007–2003 презентация к уроку по теме Мастер-класс по теме Создание классной газеты в программе Microsoft Office Publisher 2007–2003 презентация к уроку по теме 114
Презентация по правилам дорожного движения на тему: Автобус Презентация по правилам дорожного движения на тему: Автобус 104
Презентация Птицы нашего края презентация к уроку Презентация Птицы нашего края презентация к уроку 105
Презентация по организации снабжения и управление запасами на тему Организация тарного хозяйства Презентация по организации снабжения и управление запасами на тему Организация тарного хозяйства 135
Фотоотчет 3 часть Фотоотчет 3 часть 97
Корпоративная, деловая, функциональная, операционная стратегии (уровни стратегий) Корпоративная, деловая, функциональная, операционная стратегии (уровни стратегий) 143
Активные операции коммерческих банков Активные операции коммерческих банков 111
Маркетинг в строительстве Маркетинг в строительстве 165
Построение функций в open office. calc Построение функций в open office. calc 125
Презентация изготовления куклы для настольного театра презентация Презентация изготовления куклы для настольного театра презентация 110
Мини- музей Чтобы помнили... презентация к уроку (подготовительная группа) Мини- музей Чтобы помнили... презентация к уроку (подготовительная группа) 42
Презентация к уроку Двунадесятые праздники 3 Презентация к уроку Двунадесятые праздники 3 107
Образные языковые средства Образные языковые средства 139
Взаимодействие с родителями для популяризации детского экспериментирования презентация Взаимодействие с родителями для популяризации детского экспериментирования презентация 134
Родители и дети. Осенние поделки. 2017 год. презентация к уроку по конструированию, ручному труду (подготовительная группа) Родители и дети. Осенние поделки. 2017 год. презентация к уроку по конструированию, ручному труду (подготовительная группа) 94
Нормативное правовое и методическое обеспечение организации дорожного движения и в городах Российской Федерации Нормативное правовое и методическое обеспечение организации дорожного движения и в городах Российской Федерации 104
Нестандартные приемы формирования самостоятельности и инициативности презентация Нестандартные приемы формирования самостоятельности и инициативности презентация 117
Путешествие в мир задач на разностное сравнение Путешествие в мир задач на разностное сравнение 89