Остовные деревья

Остовные деревья Лекция 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