Сильно связные компоненты; остовные деревья минимальной стоимости

Дисциплина «Алгоритмы и структуры данных» Лекция № 12 Сильно связные компоненты. Остовные деревья минимальной стоимости Филатов Вячеслав Валерьевич к.т.н., доцент кафедры КБ-2 «Прикладные информационные технологии» Основные задачи морфологического анализа графа Основными задачами морфологического анализа ориентированного графа G = (V, Е) являются: • разбиение множества вершин на непересекающиеся классы эквивалентности или сильно связанные компоненты графа (сильно связанные подграфы) • разбиение множества вершин на непересекающиеся классы порядка или построение редуцированного (приведенного) графа Понятие сильно связанной компоненты графа Сильно связной (связанной) компонентой (ССК) ориентированного графа G называется максимальное множество вершин, в котором существуют пути из любой вершины в любую другую вершину. Строгое определение сильной связности. Пусть G = (V, Е) — ориентированный граф. Множество вершин V разбивается на классы эквивалентности Vi, 1 ≤ i ≤ r (r -число ССК), так, что вершины v и w будут эквивалентны тогда и только тогда, когда существуют пути из вершины v в вершину w и из вершины w в вершину v. Пусть Ei, 1 ≤ i ≤ r, — множество дуг, которые начинаются и заканчиваются в множестве вершин Vi. Тогда графы Gi = (Vi, Еi) называются сильно связными компонентами графа G. Ориентированный граф, состоящий только из одной сильно связной компоненты (r=1), называется сильно связным. Понятие редуцированного графа Представим связи между компонентами графа путем создания редуцированного (приведенного) графа для графа G. Вершинами редуцированного (приведенного) графа для графа G = (V, Е) являются его сильно связные компоненты Vi, 1w, то в Gr будет присутствовать дуга w–>v) Выполняется поиск в глубину на графе Gr, начиная с вершины с наибольшим номером, присвоенным на шаге 2. Если проведенный поиск не охватывает всех вершин, то начинается новый поиск с вершины, имеющей наибольший номер среди оставшихся вершин. Каждое дерево в полученном остовном лесу является сильно связной компонентой графа G Остовные деревья минимальной стоимости. Определения. Связный ациклический граф, представляющий собой "дерево без корня", называют свободным деревом. Определения. Связный ациклический граф, представляющий собой "дерево без корня", называют свободным деревом. Примеры свободных деревьев: Свойства? Определения. Связный ациклический граф, представляющий собой "дерево без корня", называют свободным деревом. Примеры свободных деревьев: Свойства свободных деревьев: 1. Каждое свободное дерево с числом вершин п, п > 1, имеет в точности п - 1 ребер. 2. Если в свободное дерево добавить новое ребро, то обязательно получится цикл. Определение ОДМС Пусть G = (V, Е) — связный неориентированный граф, в котором каждое ребро (v, w) помечено числом c(v, w), которое называется стоимостью ребра. Остовным деревом графа G называется свободное дерево, содержащее все вершины V графа G. Стоимость остовного дерева вычисляется как сумма стоимостей всех ребер, входящих в это дерево. Свойство ОДМС. Пусть G = (V, Е) — связный граф с заданной функцией стоимости, определенной на множестве ребер. Обозначим через U подмножество множества вершин V. Если (и, v) – такое ребро наименьшей стоимости, что иU и vV\U, тогда для графа G существует остовное дерево минимальной стоимости, содержащее ребро (и. v). v U u v V\ U Методы построения ОДМС Методы построения ОДМС • Алгоритм Прима В этом алгоритме строится множество вершин U, из которого "вырастает" остовное дерево. 1. Пусть V = {1, 2, ..., n). Сначала U = {1}. 2. На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v) такое, что иU и vV\U, затем вершина v переносится из множества V \ U в множество U. Этот процесс продолжается до тех пор, пока множество U не станет равным множеству V. • Алгоритм Крускала В этом алгоритме строится множество дуг остовного дерева, причем изначально U=V. Тогда На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v) такое, что и  V и v  V, и оно еще не принимало участие в алгоритме. После проверки того, что это ребро не образует цикл на подграфе, содержащем все узлы и отобранные к текущему моменту дуги, данное ребро добавляется к данному подмножеству дуг, образующих решение задачи. Этот процесс продолжается до тех пор, пока число отобранных дуг не станет равным n - 1 (где n – число узлов графа) Методы построения ОДМС: алгоритм Прима Алгоритм Прима На каждом шаге строится множество вершин U, из которого "вырастает" остовное дерево. 1. Пусть V = {1, 2, ..., n). Сначала U = {1}. 2. На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v) такое, что иU и vV\U, затем вершина v переносится из множества V \ U в множество U. Этот процесс продолжается до тех пор, пока множество U не станет равным множеству V. Методы построения ОДМС: алгоритм Прима Алгоритм Прима На каждом шаге строится множество вершин U, из которого "вырастает" остовное дерево. 1. Пусть V = {1, 2, ..., n). Сначала U = {1}. 2. На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v) такое, что иU и vV\U, затем вершина v переносится из множества V \ U в множество U. Этот процесс продолжается до тех пор, пока множество U не станет равным множеству V. Методы построения ОДМС: алгоритм Прима Алгоритм Прима На каждом шаге строится множество вершин U, из которого "вырастает" остовное дерево. 1. Пусть V = {1, 2, ..., n). Сначала U = {1}. 2. На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v) такое, что иU и vV\U, затем вершина v переносится из множества V \ U в множество U. Этот процесс продолжается до тех пор, пока множество U не станет равным множеству V. Методы построения ОДМС: алгоритм Прима Алгоритм Прима На каждом шаге строится множество вершин U, из которого "вырастает" остовное дерево. 1. Пусть V = {1, 2, ..., n). Сначала U = {1}. 2. На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v) такое, что иU и vV\U, затем вершина v переносится из множества V \ U в множество U. Этот процесс продолжается до тех пор, пока множество U не станет равным множеству V. Методы построения ОДМС: алгоритм Прима Алгоритм Прима На каждом шаге строится множество вершин U, из которого "вырастает" остовное дерево. 1. Пусть V = {1, 2, ..., n). Сначала U = {1}. 2. На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v) такое, что иU и vV\U, затем вершина v переносится из множества V \ U в множество U. Этот процесс продолжается до тех пор, пока множество U не станет равным множеству V. Методы построения ОДМС: алгоритм Прима Алгоритм Прима На каждом шаге строится множество вершин U, из которого "вырастает" остовное дерево. 1. Пусть V = {1, 2, ..., n). Сначала U = {1}. 2. На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v) такое, что иU и vV\U, затем вершина v переносится из множества V \ U в множество U. Этот процесс продолжается до тех пор, пока множество U не станет равным множеству V. Методы построения ОДМС: алгоритм Прима Изображение 3 a 2 7 b 10 c 6 Множество выбранных вершин U Ребро (u, v) Множество невыбранных вершин V \ U Описание {a, b, c, d, e} Исходный взвешенный граф. Числа возле ребер показывают их веса, которые можно рассматривать как расстояния между e 6 12 1 {} d 2 вершинами. 3 a 10 2 7 b c 6 2 e 6 12 1 d {a} (a, b)=2 + (a, c)=10 (a, d)=7 (a, e)=3 {b, c, d, e} В качестве начальной выбирается вершина a. Каждая из вершин b, c, d и e соединена с a единственным ребром. Вершина b — ближайшая к a, и выбирается как вторая вершина вместе с ребром ab. Множество выбранных вершин U Изображение 3 a 10 2 7 b c 6 7 12 1 {a, b} d 3 10 b 6 2 a 2 e c 6 2 e 6 12 1 d {a, b, d} Ребро (u, v) (a, c)=10 (a, d)=7 (a, e)=3 (b, c)=6 (b, d)=2 + (a, c)=10 (a, d)=7 цикл (a, e)=3 (b, c)=6 (d, c)=1 + (d, e)=12 Множество невыбранных вершин V \ U {c, d, e} {c, d} Описание Вершина d – расположена ближе остальных, поэтому d выбирается как третья вершина вместе с ребром bd. Вершина c – расположена ближе остальных, поэтому c выбирается как четвертая вершина вместе с ребром dc. Множество выбранных вершин U Изображение 3 a 10 2 7 b c 6 d 3 10 7 b 12 1 2 a 2 e 6 c 6 2 e 6 12 1 d {a, b, c, d} Ребро (u, v) (a, c)=10 цикл (a, d)=7 цикл (a, e)=3 + (b, c)=6 цикл (c, e)=6 (d, e)=12 Множество невыбранных вершин V \ U {e} Описание Вершина e – расположена ближе остальных, поэтому e выбирается как пятая и последняя вершина вместе с ребром ce. Методы построения ОДМС: алгоритм Крускала Алгоритм Крускала (Краскала) Изначально U=V. Тогда на каждом шаге алгоритма находится ребро наименьшей стоимости (и, v) такое, что и  V и v  V, и оно еще не принимало участие в алгоритме. После проверки того, что это ребро не образует цикл на подграфе, содержащем все узлы и отобранные к текущему моменту дуги, данное ребро добавляется к данному подмножеству дуг, образующих решение задачи. Этот процесс продолжается до тех пор, пока число отобранных дуг не станет равным n - 1 (где n – число узлов графа) Реализация алгоритма Прима-Краскала Проблема: как проверить, что 1) ребро не выбрано, и 2) ребро не образует цикла с выбранными ребрами. Решение: присвоить каждой вершине свой цвет и перекрашивать вершины при добавлении ребра. 7 3 2 1 8 4 5 3 6 4 Алгоритм: 1) покрасить все вершины в разные цвета; 2) сделать N-1 раз в цикле:  выбрать ребро (i,j) минимальной длины из всех ребер, соединяющих вершины разного цвета;  перекрасить все вершины, имеющие цвет j, в цвет i. 3) вывести найденные ребра. 43 Реализация алгоритма Прима-Крускала Структура «ребро»: struct rebro { int i, j; // номера вершин }; Основная программа: весовая цвета const N = 5; матрица вершин void main() { int W[N][N], Color[N], i, j, k, min, col_i, col_j; rebro Reb[N-1]; ... // здесь надо ввести матрицу W for ( i = 0; i < N; i ++ ) // раскрасить вершины Color[i] = i; ... // основной алгоритм – заполнение массива Reb ... // вывести найденные ребра (массив Reb) } 44 Реализация алгоритма Прима-Крускала Основной алгоритм: for ( k = 0; k < N-1; k ++ ) { min = 30000; // большое число нужно выбрать N-1 ребро цикл по всем парам вершин for ( i = 0; i < N-1; i ++ ) for ( j = i+1; j < N; j ++ ) if ( Color[i] != Color[j] && учитываем W[i][j] < min ) { только пары с разным цветом min = W[i][j]; вершин Reb[k].i = i; Reb[k].j = j; запоминаем ребро и col_i = Color[i]; цвета вершин col_j = Color[j]; } перекрашиваем вершины цвета col_j for ( i = 0; i < N; i ++ ) if ( Color[i] == col_j ) Color[i] = col_i; } 45 Сложность алгоритма Основной цикл: for ( k = 0; k < N-1; k ++ ) { три вложенных цикла, в каждом число шагов <=N ... for ( i = 0; i < N-1; i ++ ) for ( j = i+1; j < N; j ++ ) ... } Количество операций: O(N3) растет не быстрее, чем N3 Требуемая память: int W[N][N], Color[N]; rebro Reb[N-1]; O(N2) 46 Спасибо за внимание!