Остовные деревья
Выбери формат для чтения
Загружаем конспект в формате pdf
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
Остовные деревья
Лекция 12
1
Постановка задачи
▪ Имеется 𝑛 городов, которые необходимо соединить дорогами, так, чтобы можно было
добраться из любого города в любой другой (напрямую или через другие города)
▪ Известна стоимость строительства дороги между любой парой городов (граф взвешенный)
▪ Между какими городами строить дороги?
Томск
87
Новосибирск
78
94
65
110
43
Кемерово
98
49
140
Бийск
Барнаул
45
2
Постановка задачи
▪ Имеется 𝑛 городов, которые необходимо соединить дорогами, так, чтобы можно было
добраться из любого города в любой другой (напрямую или через другие города)
▪ Известна стоимость строительства дороги между любой парой городов (граф взвешенный)
▪ Между какими городами строить дороги?
Томск
87
Новосибирск
78
94
65
110
43
Стоимость проекта
87 + 65 + 49 + 140 = 341
Кемерово
98
49
140
Бийск
Барнаул
45
3
Постановка задачи
▪ Имеется 𝑛 городов, которые необходимо соединить дорогами, так, чтобы можно было
добраться из любого города в любой другой (напрямую или через другие города)
▪ Известна стоимость строительства дороги между любой парой городов (граф взвешенный)
▪ Между какими городами строить дороги?
Стоимость проекта
65 + 49 + 140 + 43 = 297
Томск
87
Новосибирск
78
94
65
110
43
Кемерово
98
49
140
Бийск
Барнаул
45
4
Остовные деревья
▪ Óстовное дерево связного граф а (spanning tree) – это ациклический связный
подграф (дерево), в который входят все вершины данного графа
▪ Синонимы: остов, покрывающее дерево, скелет граф а
Это не остов –присутствует
цикл
1
1
2
2
5
5
3
3
4
4
5
Остовные деревья минимальной стоимости
▪ Если граф взвешенный, то рассматривается задача о нахождении остовного
дерева с минимальной суммой весов входящих в него рёбер
1
10
2
50
100
30
5
10
60
3
20
1
10
4
Cost = 10 + 50 + 10 + 60 = 130
2
50
100
30
5
10
60
3
20
4
Cost = 100 + 10 + 50 + 20 = 180
6
Применение остовных деревьев
▪ Остовное дерево минимальной стоимости (minimum spanning tree, MST) –
это остовное дерево с минимальной суммой весов его ребер
▪ Практическое применение MST
Формирование дерева для широковещательной рассылки информации в
сети (tree for broadcasting)
прокладка кабеля между домами (вес ребер – стоимость прокладки кабеля
между парой домов)
Spanning Tree Protocol в телекоммуникационных сетях стандарта Ethernet
для предотвращения образования циклов в сети
…
7
Алгоритмы построения MST
Вычислительная сложность
Алгоритм
Матрица
смежности
J. Kruskal, 1956
V. Jarník, 1930;
R. Prim, 1957;
E. Dijkstra, 1959
Списки смежности +
двоичная куча
Списки смежности +
ф ибоначчиева куча
𝑂(|𝐸| log |𝑉|)
𝑂( 𝑉 2 )
𝑂(( 𝑉 + |𝐸|) log |𝑉|)
𝑂( 𝐸 + |𝑉| log |𝑉|)
O. Borůvka, 1926
𝑂(|𝐸| log |𝑉|)
B. Chazelle, 2000
𝑂(|𝐸| ∙ 𝛼( 𝐸 , |𝑉|)),
где 𝛼(𝑚, 𝑛) – обратная функция Аккермана
Система непересекающихся множеств
▪ Система непересекающихся множеств (disjoint-set data structure) – структура
данных для представления непересекающихся множеств
▪ Поддерживает следующие операции:
MakeSet(i) – создает множество из одного элемента i
FindSet(i) – возвращает номер множества, которому принадлежит
элемент i
UnionSets(i,j) – объединяет множества, содержащие элементы i и j
▪ Подробное описание
(Aho, С. 169, MFSET)
(Levitin, С. 381)
(CLRS, С. 597)
9
Система непересекающихся множеств
▪
▪
▪
▪
MakeSet(1)
MakeSet(4)
MakeSet(6)
MakeSet(3)
4 множества: {1}, {4}, {6}, {3}
▪ UnionSets(1, 3)
{1, 3}, {4}, {6}
▪ UnionSets(4, 3)
{1, 3, 4}, {6}
10
Алгоритм Крускала (Kruskal)
1. Создается пустой граф 𝑇 из 𝑛 вершин, не связанных
ребрами
2. Все ребра исходного графа 𝐺 помещают в очередь с
приоритетом
1
6
2
5
3
6
Приоритет – вес ребра 𝑤𝑖𝑗 (ребра упорядочиваются
по не убыванию весов – min heap)
5
1
3
6
1
Prio. Q: (1, 3), (4, 6), (2, 5), (3, 6), (2, 3), …
2
G
5
5
4
4
2
6
T
4
3
В графе 𝑇 6 компонент
связности
5
6
11
Алгоритм Крускала (Kruskal)
3. Цикл из 𝑛 – 1 итерации (по количеству ребер в
MST)
a) Из очереди извлекается ребро (𝑖, 𝑗) с
минимальным весом (HeapDeleteMin)
b) Если ребро (𝑖, 𝑗) связывает вершины из
разных компонент связности графа 𝑇, то
ребро добавляется в граф 𝑇
1
6
2
5
3
6
5
1
3
6
1
2
G
5
5
4
4
2
6
T
4
3
Prio. Q: (1, 3), (4, 6), (2, 5), (3, 6), (2, 3), …
5
6
12
Алгоритм Крускала (Kruskal)
3. Цикл из 𝑛 – 1 итерации (по количеству ребер в
MST)
a) Из очереди извлекается ребро (𝑖, 𝑗) с
минимальным весом (HeapDeleteMin)
b) Если ребро (𝑖, 𝑗) связывает вершины из
разных компонент связности графа 𝑇, то
ребро добавляется в граф 𝑇
1
6
2
5
3
6
5
1
3
6
1
2
G
5
5
4
4
2
6
T
4
3
Prio. Q: (1, 3), (4, 6), (2, 5), (3, 6), (2, 3), …
5
6
13
Алгоритм Крускала (Kruskal)
3. Цикл из 𝑛 – 1 итерации (по количеству ребер в
MST)
a) Из очереди извлекается ребро (𝑖, 𝑗) с
минимальным весом (HeapDeleteMin)
b) Если ребро (𝑖, 𝑗) связывает вершины из
разных компонент связности графа 𝑇, то
ребро добавляется в граф 𝑇
1
6
2
5
3
6
5
1
3
6
1
2
G
5
5
4
4
2
6
T
4
3
Prio. Q: (4, 6), (2, 5), (3, 6), (2, 3), …
5
6
14
Алгоритм Крускала (Kruskal)
3. Цикл из 𝑛 – 1 итерации (по количеству ребер в
MST)
a) Из очереди извлекается ребро (𝑖, 𝑗) с
минимальным весом (HeapDeleteMin)
b) Если ребро (𝑖, 𝑗) связывает вершины из
разных компонент связности графа 𝑇, то
ребро добавляется в граф 𝑇
1
6
2
5
3
6
5
1
3
6
1
2
G
5
5
4
4
2
6
T
4
3
Prio. Q: (2, 5), (3, 6), (2, 3), …
5
6
15
Алгоритм Крускала (Kruskal)
3. Цикл из 𝑛 – 1 итерации (по количеству ребер в
MST)
a) Из очереди извлекается ребро (𝑖, 𝑗) с
минимальным весом (HeapDeleteMin)
b) Если ребро (𝑖, 𝑗) связывает вершины из
разных компонент связности графа 𝑇, то
ребро добавляется в граф 𝑇
1
6
2
5
3
6
5
1
3
6
1
2
G
5
5
4
4
2
6
T
4
3
Prio. Q: (3, 6), (2, 3), …
5
6
16
Алгоритм Крускала (Kruskal)
3. Цикл из 𝑛 – 1 итерации (по количеству ребер в
MST)
a) Из очереди извлекается ребро (𝑖, 𝑗) с
минимальным весом (HeapDeleteMin)
b) Если ребро (𝑖, 𝑗) связывает вершины из
разных компонент связности графа 𝑇, то
ребро добавляется в граф 𝑇
1
6
2
5
3
6
5
1
3
6
1
2
G
5
5
4
4
2
6
T
4
3
Prio. Q: (2, 3), …
5
6
17
Алгоритм Крускала (Kruskal)
3. Цикл из 𝑛 – 1 итерации (по количеству ребер в
MST)
a) Из очереди извлекается ребро (𝑖, 𝑗) с
минимальным весом (HeapDeleteMin)
b) Если ребро (𝑖, 𝑗) связывает вершины из
разных компонент связности графа 𝑇, то
ребро добавляется в граф 𝑇
▪ Построили остовное дерево 𝑇 минимальной
стоимости (MST)
▪ Стоимость 1 + 5 + 3 + 4 + 2 = 15
1
6
2
5
3
6
5
1
3
6
1
2
G
5
5
4
4
2
6
T
4
3
5
6
18
Алгоритм Крускала (Kruskal)
function MST_Kruskal([in] G, [out] T)
// Input: G = (V, E)
// Output: T = (V, E’)
T = CreateGraph(|V|)
// Помещаем вершину i в отдельное множество
// (компоненту связности графа T)
for each i in V do
MakeSet(i)
end for
// Помещаем ребра в очередь с приоритетом
for each (i, j) in E do
PriorityQueueInsert(w[i][j], (i, j))
end for
C = |V|
// Количество компонент связности
19
Алгоритм Крускала (Kruskal)
while C > 1 do
// Извлекаем ребро с минимальным весом
(i, j) = PriorityQueueRemoveMin()
seti = FindSet(i)
setj = FindSet(j)
if seti != setj then
// Концы ребра из разных множеств
GraphAddEdge(T, (i, j))
UnionSets(i, j)
C = C - 1
end if
end for
end function
20
Алгоритм Крускала (Kruskal)
function MST_Kruskal([in] G, [out] T)
// Input: G = (V, E)
// Output: T = (V, E’)
T = CreateGraph(|V|)
// Помещаем вершину i в отдельное множество
// (компоненту связности графа T)
for each i in V do
𝑀𝐹𝑆𝐸𝑇
MakeSet(i)
𝑂(|𝑉|)
end for
// Помещаем ребра в очередь с приоритетом
for each (i, j) in E do
𝐵𝑖𝑛𝑎𝑟𝑦 ℎ𝑒𝑎𝑝
PriorityQueueInsert(w[i][j], (i, j))
𝑂(|𝐸|log |𝐸|)
end for
C = |V|
// Количество компонент связности
21
Алгоритм Крускала (Kruskal)
while C > 1 do
// Извлекаем ребро с минимальным весом
(i, j) = PriorityQueueRemoveMin() O(log|E|)
seti = FindSet(i)
O(1)
setj = FindSet(j)
O(1)
if seti != setj then
// Вершины ребра из разных множеств
GraphAddEdge(T, (i, j))
O(|V|)
UnionSets(i, j)
C = C - 1
end if
end for
end function
▪ В худшем случае цикл выполняется |𝐸| раз
22
Алгоритм Крускала (Binary heap + MFSET)
𝑇𝐾𝑟𝑢𝑠𝑘𝑎𝑙 = 𝑂 𝑉 + 𝑂 𝐸 log 𝐸 + 𝑂 𝐸 log 𝐸 + 𝑂 𝑉
Создание
множеств
Вставка ребер
в очередь
log 𝐸 ≤ log 𝑉
𝑇𝐾𝑟𝑢𝑠𝑘𝑎𝑙 = 𝑂 𝐸 log 𝐸 + 𝑂 𝑉
2
Извлечение
ребер из
очереди
2
Объединение
множеств
= 2 log |𝑉|
2
= 𝑂 𝐸 log 𝑉 + 𝑂 𝑉
2
▪ От чего зависит сложность алгоритма Крускала?
от реализации сортировки ребер по их весу (Sort, Binary heap, …)
от реализации системы непересекающихся множеств
23
MFSET
/* mfset.h: Disjoint set data structure */
struct set {
int size;
int first;
};
struct elem {
int set;
int next;
};
struct mfset {
struct set *sets;
struct elem *elems;
int nelems;
int nsets;
};
sets
elems
24
MFSET
struct mfset *mfset_create(int nelems)
{
struct mfset *p;
int i;
}
p = malloc(sizeof(*p));
p->nelems = nelems;
p->nsets = 0;
p->sets = malloc(sizeof(struct set) * nelems);
p->elems = malloc(sizeof(struct elem) * nelems);
for (i = 0; i < nelems; i++) {
p->sets[i].size = 0;
p->sets[i].first = -1;
p->elems[i].set = -1;
p->elems[i].next = -1;
}
return p;
𝑇
= 𝑂(𝑛𝑒𝑙𝑒𝑚𝑠)
𝐶𝑟𝑒𝑎𝑡𝑒
MFSET
void mfset_free(struct mfset *set)
{
free(set->sets);
free(set->elems);
free(set);
}
void mfset_makeset(struct mfset *set, int elem)
{
set->sets[set->nsets].size = 1;
set->sets[set->nsets].first = elem;
set->elems[elem].set = set->nsets;
set->elems[elem].next = -1;
set->nsets++;
𝑇𝑀𝑎𝑘𝑒𝑆𝑒𝑡 = 𝑂(1)
}
26
MFSET
int mfset_findset(struct mfset *set, int elem)
{
return set->elems[elem].set;
𝑇𝐹𝑖𝑛𝑑𝑆𝑒𝑡 = 𝑂(1)
}
27
MFSET
void mfset_union(struct mfset *set,
int elem1, int elem2)
{
int temp, i, set1, set2;
set1 = mfset_findset(set, elem1);
set2 = mfset_findset(set, elem2);
if (set->sets[set1].size <
set->sets[set2].size)
{
temp = set1;
set1 = set2;
set2 = temp;
}
28
MFSET
/* S1 > S2; Merge elems of S2 to S1 */
i = set->sets[set2].first;
while (set->elems[i].next != -1) {
set->elems[i].set = set1;
i = set->elems[i].next;
}
/* Add elems of S1 to the end of S2 */
set->elems[i].set = set1;
set->elems[i].next = set->sets[set1].first;
set->sets[set1].first = set->sets[set2].first;
set->sets[set1].size += set->sets[set2].size;
}
/* Remove S2 */
set->sets[set2].size = 0;
set->sets[set2].first = -1;
set->nsets--;
𝑇𝑈𝑛𝑖𝑜𝑛 = 𝑂(𝑛)
29
Алгоритм Крускала (Adj. matrix + MFSET + Bin. heap)
int search_mst_kruskal(struct graph *g,
struct graph *mst)
{
struct mfset *set;
struct heap *pq;
struct heapvalue edge;
struct heapitem item`;
int mstlen, i, j, n, w, s1, s2;
n = g->nvertices;
mstlen = 0;
/* Create forest (N sets) */
set = mfset_create(n);
for (i = 0; i < n; i++) {
mfset_makeset(set, i);
}
30
Алгоритм Крускала (Adj. matrix + MFSET + Bin. heap)
/* Insert edges in heap */
pq = heap_create(n * n);
/* For all edges (adj. matrix) */
for (i = 0; i < n; i++) {
for (j = i + 1; j < n; j++) {
w = graph_get_edge(g, i + 1,
j + 1);
if (w > 0) {
edge.i = i;
edge.j = j;
heap_insert(pq, w, edge);
}
}
}
31
Алгоритм Крускала (Adj. matrix + MFSET + Bin. heap)
for (i =
item
s1 =
s2 =
}
}
0; i < n - 1; ) {
= heap_removemin(pq);
mfset_findset(set, item.value.i);
mfset_findset(set, item.value.j);
if (s1 != s2) {
mfset_union(set, item.value.i, item.value.j);
mstlen += item.priority;
graph_set_edge(mst, item.value.i + 1, item.value.j + 1,
item.priority);
i++;
}
heap_free(pq);
mfset_free(set);
return mstlen;
32
Пример
int main()
{
struct graph *g, *mst;
int i, j, mstlen;
g = graph_create(6);
graph_set_edge(g, 1,
graph_set_edge(g, 1,
graph_set_edge(g, 1,
graph_set_edge(g, 2,
graph_set_edge(g, 2,
graph_set_edge(g, 3,
graph_set_edge(g, 3,
graph_set_edge(g, 3,
graph_set_edge(g, 4,
graph_set_edge(g, 5,
2,
3,
4,
3,
5,
4,
5,
6,
6,
6,
1
6
6);
1);
5);
5);
3);
5);
6);
4);
2);
6);
2
5
3
6
5
1
3
6
5
5
4
4
2
6
33
Пример
mst = graph_create(6);
mstlen = search_mst_kruskal(g, mst);
printf("Minimum spanning tree: %d\n", mstlen);
for (i = 0; i < 6; i++) {
for (j = 0; j < 6; j++) {
printf("%4d ", graph_get_edge(mst,
i + 1, j + 1));
}
printf("\n");
}
}
graph_free(mst);
graph_free(g);
return 0;
34
Пример
$ ./kruskal
Minimum spanning tree: 15
1
5
3
1
5
3
4
2
4
2
35
Алгоритм Прима (Prim)
1. Создается пустой граф T.
2. Во множество U помещается
вершина 1, с которой начнется формирование
остова.
1
6
5
3
6
3. Цикл пока U ≠ V
5
a) Найти ребро (i, j ) с наименьшим весом такое,
что i U и j V
b) Добавить ребро (i, j ) в граф T
c) Добавить вершину j
во множество U
5
1
2
3
6
1
2
G
5
4
4
2
6
T
4
3
5
6
36
