Что такое 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
  • Количество просмотров: 110
  • Количество скачиваний: 0
- Предыдущая The brain
Следующая - Физика Радиоактивность

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

Родительское собрание Готовимся к ВПР консультация (4 класс) Родительское собрание Готовимся к ВПР консультация (4 класс) 203
Линии на плоскости Линии на плоскости 79
Презентация к мероприятию Неделя гуманитарных наук Презентация к мероприятию Неделя гуманитарных наук 200
Ryanair’s business model Ryanair’s business model 114
13 причин читать книжки. консультация (2 класс) 13 причин читать книжки. консультация (2 класс) 105
Шаблон для создания презентаций Тетрадь на спирали презентация к уроку (1, 2, 3, 4 класс) Шаблон для создания презентаций Тетрадь на спирали презентация к уроку (1, 2, 3, 4 класс) 92
Проект Наши любимые игрушки ранний возраст проект (младшая группа) Проект Наши любимые игрушки ранний возраст проект (младшая группа) 155
Интегрированное занятие Жили-были мама коза с козлятами план-конспект занятия (младшая группа) Интегрированное занятие Жили-были мама коза с козлятами план-конспект занятия (младшая группа) 118
Умственное воспитание Умственное воспитание 100
Презентация Мастер-класс по сказкотерапии для родителей Презентация Мастер-класс по сказкотерапии для родителей 164
Лекция № 1 на тему: Сущность аудита, его цель и задачи Лекция № 1 на тему: Сущность аудита, его цель и задачи 106
The theatre The theatre 148
Сварочное производство Сварочное производство 136
Путешествие разноцветного паровозика презентация к занятию по конструированию, ручному труду (старшая группа) Путешествие разноцветного паровозика презентация к занятию по конструированию, ручному труду (старшая группа) 105
Производственный менеджмент(тема 2) Производственный менеджмент(тема 2) 110
Презентация: Виртуальный праздник молока со звуковым файлом презентация к уроку (средняя группа) Презентация: Виртуальный праздник молока со звуковым файлом презентация к уроку (средняя группа) 106
Материал к родительскому собранию Не хочу делать уроки! материал (1, 2, 3, 4 класс) Материал к родительскому собранию Не хочу делать уроки! материал (1, 2, 3, 4 класс) 92
Родительское собрание в подготовительной группе презентация к уроку (подготовительная группа) Родительское собрание в подготовительной группе презентация к уроку (подготовительная группа) 99
Памятники культуры первобытности Памятники культуры первобытности 110
Электромашиналық цехтың тағайындалуы Электромашиналық цехтың тағайындалуы 118
стимул персонала стимул персонала 115
Признаки готовности ребенка к поступлению в детский сад презентация Признаки готовности ребенка к поступлению в детский сад презентация 41
Примеры наружной рекламы в Ижевске Примеры наружной рекламы в Ижевске 98
Способы осуществления власти менеджером. Способы осуществления власти менеджером. 102
Конспект педагогического мероприятия по теме Космос с использованием технологии индивидуализации (подготовительная группа) + презентация план-конспект занятия по окружающему миру (подготовительная группа) по теме Конспект педагогического мероприятия по теме Космос с использованием технологии индивидуализации (подготовительная группа) + презентация план-конспект занятия по окружающему миру (подготовительная группа) по теме 95
Развитие воли у человека. Волевые качества личности и их становления. Развитие воли у человека. Волевые качества личности и их становления. 125
Презентация Правила поведения на воде презентация к уроку (младшая группа) Презентация Правила поведения на воде презентация к уроку (младшая группа) 121
Удостоверение Удостоверение 93
Заболеванияноворожденных Заболеванияноворожденных 89
Презентация по психологии на тему Структура личности и ее составляющие Презентация по психологии на тему Структура личности и ее составляющие 178