Способы обхода графов, каркасы графа Лекция 12. Поиск в глубину (Depth-first search, DFS) Пусть задан граф G = (V, E). Алгоритм поиска описывается следующим. - презентация

1 Способы обхода графов, каркасы графа Лекция 12

2 Поиск в глубину (Depth-first search, DFS) Пусть задан граф G = (V, E). Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все непройденные смежные вершины и повторить поиск для них. Пусть в начальный момент времени все вершины окрашены в белый цвет. 1) Из множества всех белых вершин выберем любую вершину: v1. 2) Выполним для нее процедуру DFS(v1). 3) Перекрасим ее в черный цвет. Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.

3 Метод поиска в глубину G = (V, E) Поиск(u){ color u серый; d[u]=time++; for (для v Adj(u)) if(color v == белый){ Π[v] u; Поиск(v); } color u черный; f[u] time++; }

4 G = (V, E) Поиск_в_глубину(){ for ( u V ){ color u белый; Π[u] NULL; time 0; } for ( u V ) if(color [u] == белый) Поиск(u); }

5 Идти вглубь, пока есть непройденные инцидентные ребра, ведущие в белые вершины, и возвращаться и искать другой путь, когда таких ребер нет. Обнаружив впервые вершину v, смежную с u, помещаем в Π[v] значение (номер, адрес) u. В результате получаем дерево или несколько деревьев. Подграф предшествования G Π = (V, E Π ): E Π = { (Π[v], v) : v V и Π[v] NULL } Подграф предшествования представляет собой лес поиска в глубину, состоящий из деревьев поиска в глубину. Каркас графа Остовное дерево

6 Анализ Общее число операций при выполнении Поиск_в_глубину: O(|V|) Общее число операций при выполнении Поиск(u): Цикл выполняется |Adj[v]| раз. |Adj[v]| = O(|E|) Общее число операций: O(|V|+|E|)

7 Свойства поиска в глубину Времена обнаружения и окончания обработки вершин образуют правильную скобочную структуру. Z w S x y (s(z(y(xx)y)(ww)z)s)

8 Теорема При поиске в глубину в графе G = (V, E) для любых двух вершин u и v выполняется одно из следующих утверждений: 1)Отрезки [d[u],f[u]] и [d[v],f[v]] не пересекаются; 2)Отрезок [d[u],f[u]] целиком содержится внутри отрезка [d[v],f[v]] и u есть потомок v в дереве поиска в глубину; 3)Отрезок [d[v],f[v]] целиком содержится внутри отрезка [d[u],f[u]] и v есть потомок u в дереве поиска в глубину.

9 Z w S x y u u t v Синие – древесные ребра Красные – прямые ребра (соединяют вершину с ее потомком, но не входят в дерево поиска в глубину) Голубые – обратные ребра (соединяют вершину с ее предком в дереве поиска в глубину) Остальные (черные) – перекрестные ребра

10 Использование стека для обхода графа Если в качестве промежуточной структуры хранения при обходе использовать стек, то получим обход в глубину Граф: Можно также получить дерево обхода в глубину, если отмечать каждую прямую или обратную дугу Стек:

11 Метод поиска в ширину ( BFS, Breadth-first search) Пусть задан граф G = (V, E) и некоторая начальная вершина s. Алгоритм поиска в ширину перечисляет все достижимые из s вершины в порядке возрастания растояния от s. Расстоянием считается число ребер кратчайшего пути. Время работы алгоритма - O(|V|+ |E|). В процессе поиска из графа выделяется часть, называемая деревом поиска в ширину с корнем s. Она содержит все достижимые из s вершины. Для каждой из них путь из корня в дереве поиска будет одним из кратчайших путей в графе. Пусть в начальный момент времени все вершины окрашены в белый цвет. 1.Вершину s окрасим в серый цвет и припишем расстояние 0. Смежные с ней вершины окрасим в серый цвет, припишем им расстояние 1, их предок - s. Окрасим вершину s в черный цвет. 2.На шаге n поочередно рассматриваем белые вершины, смежные с вершинами с пометками n-1, и каждую из них раскрашиваем в серый цвет, приписываем им предка и расстояние n. После этого вершины с расстоянием n-1 окрашиваются в черный цвет.

12 Использование очереди В качестве промежуточной структуры хранения при обходе в ширину будем использовать очередь Граф: 1 Можно также получить дерево обхода в ширину, если отмечать каждую прямую дугу Очередь:

13 Алгоритм Инициализация for ( u (V\{s}) { color u белый; Π[u] NULL; d[u] ; } d[s] 0; Π[s] NULL; put (s, Q);

14 while (Q ø ) { u first (Q); for ( v Adj[u]) { if (color[v]== белый){ color v серый; Π[v] u; d[v] d[u]+1; put(s,Q); } get(Q); color[u]== черный; }

15 Доказательство

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

17 Каркасы графа G(V,E) - связный неориентированный граф с заданной функцией стоимости Остовное дерево или каркас графа - подграф: 1) содержит все вершины графа, 2) является деревом. Нас интересуют алгоритмы построения минимального каркаса. Минимальным каркасом является такой каркас, сумма весов ребер которого минимальна.

18 Алгоритм Краскала (Джозеф Краскал, 1956 год) 1.Сортируем ребра графа по возрастанию весов. 2.Полагаем что каждая вершина относится к своей компоненте связности. 3.Проходим ребра в "отсортированном" порядке. Для каждого ребра выполняем: а)если вершины, соединяемые данным ребром лежат в разных компонентах связности, то объединяем эти компоненты в одну, а рассматриваемое ребро добавляем к минимальному остовному дереву; б)если вершины, соединяемые данным ребром лежат в одной компоненте связности, то исключаем ребро из рассмотрения. 4.Если есть еще нерассмотренные ребра и не все компоненты связности объеденены в одну, то переходим к шагу 3, иначе выход.

19 Вход. Неориентированный граф G= (V, Е) с функцией стоимости с, заданной на его ребрах. Выход. Остовное дерево S= (V, Т) наименьшей стоимости для G. Метод: 1. Т ; // остовное дерево (каркас) 2. VS ; // набор непересекающихся множеств вершин 3. построить очередь с приоритетами Q, содержащую все ребра из Е; 4. Для v V ВЫПОЛНИТЬ: добавить {v} к VS; Пока |VS|> 1 выполнить: 6. { выбрать в Q ребро (v, w) наименьшей стоимости; 7. удалить (v, w) из Q; 8. если v и w принадлежат различным множествам W1 и W2 из VS то 9. {заменить W1 и W2 на W1 W2 в VS; 10.добавить (v, w) к Т; } }

20 Пример Время работы: Cортировка рёбер - O(|E|×log|E|) Компоненты связности удобно хранить в виде системы непересекающихся множеств. Все операции в таком случае займут O(E)

21 Получившееся дерево является каркасом минимального веса. Введем массив меток вершин графа Mark. Начальные значения элементов массива равны номерам соответствующих вершин (Mark[i] = i; i 1.. N). Ребро выбирается в каркас в том случае, если вершины, соединяемые им, имеют разные значения меток. Пример приведен на следующем слайде, изменения Mark показаны в таблице.

22

23 Система непересекающихся множеств (СНМ) (Таржан (Tarjan), 1975 г.) Система непересекающихся множеств - это структура данных, которая может хранить несколько элементов, разделённых на несколько множеств (деревьев): каждый элемент принадлежит ровно одному множеству (дереву). Каждое дерево характеризуется своим представителем. Структура данных поддерживает следующие операции: MakeSet (X) Добавляет в систему новый элемент X, который заносится в отдельное (новое) дерево, представителем которого становится X. За O(1) FindSet (X) Ищет дерево, которому принадлежит элемент X, и возвращает его представителя. За О(4) - амортизированная оценка Union (X, Y) Ищет деревья, к которым принадлежат элементы X и Y, и объединяет их в одно дерево. Возвращает элемент, который становится представителем нового дерева. За O(1) - амортизированная оценка

24 Алгоритмы, реализующие СНМ 1) Простая реализация: для каждого элемента хранится номер/цвет множества, которому элемент принадлежит. FindSet (X) – O(1); Union (X, Y) – O(n) ) Реализация списком FindSet (X) - O(n); Union (X, Y) - O(1) 3) Весовая эвристика – улучшение наивной реализации: перекрашивать элементы из множества меньшей мощности, для этого элемента хранится количество элементов этого цвета Сколько раз перекрасится 1? log n раз FindSet (X) - O(1); Union (X, Y) - O(log n )

25 4) Множество хранится в виде дерева, для каждого элемента хранится его предок, представителем множества является клрень дерева. FindSet (X) - O(n); Union (X, Y) - O(1) Худший случай, когда к корню дерева подвешиваем следующий элемент: Весовая эвристика здесь не поможет: Глубина дерева увеличилась, а это плохо.

26 5) Эвристика объединением по рангу: хранится глубина (ранг) дерева. Дерево с меньшим рангом подвешивается к дереву с большим рангом. при этом ранг нового дерева не изменяется. Если ранги деревьев равны, то ранг нового дерева увеличивается на единицу. FindSet (X) - O(log n); Union (X, Y) - O(1)

27 6) Эвристика сжатия путей: когда при определении представителя множества от вершины нашли путь к корню, можно эту вершину подвесить к корню, как показано на рисунке ниже. В реализации перевешивание вершины выполняется на выходе из рекурсии. FindSet (X) - O(обратная функция Аккермана); Union (X, Y) - O(1) Для чисел int64 обратная функция Аккермана 4. хх....

28 Функция Аккермана -функция A[i, j] двух целых положительных переменных: A[1, j] = 2 j, если j 1 ; A[ i, 1] = A[ i-1, 2], если i 2; A[ i, 1] = A[ i-1, A[ i, j -1]], если i, j 2;

29 Описание алгоритма 6. Пусть элементы X - это некоторые числа. Вся структура данных хранится в виде двух массивов: P и Rank. Массив P содержит предков, т.е. P[x] - это предок элемента x. Т.о., мы имеем древовидную структуру данных: двигаясь по предкам от любого элемента х, придём к представителю множества, к которому принадлежит х. Если P[X] = X, то это означает, что x является представителем множества, к которому он принадлежит, и корнем дерева. Массив Rank хранит ранги представителей, его значения имеют cмысл только для элементов-представителей. Ранг некоторого элемента-представителя x - это верхняя граница его высоты в его дереве. Ранги используются в операции Union.

30 Реализация Инициализация for (int i=0; i

31 FindSet (X) Будем двигаться от X по предкам, до тех пор пока не найдём представителя. У каждого элемента, который мы проходим, мы также исправляем P, указывая его сразу на найденного представителя. Т.е. фактически операция FindSet двухпроходная: на первом проходе мы ищем представителя, а на втором исправляем значения P. int find_set (int x) { if (x == p[x]) return x; return p[x] = find_set (p[x]); }

32 Union (X, Y) Сначала заменяем элементы X и Y на редставителей их множеств, вызывая функцию FindSet. Объединяем два множества, присваивая P[X] = Y или P[Y] = X: - если ранги элементов X и Y отличны, то мы делаем корень с бо'льшим рангом родительским по отношению к корню с меньшим рангом. - если же ранги обоих элементов совпадают, родитель выбирается произвольным образом, его ранг увеличивается на 1.

33 void unite (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]; } }

34 Реализация со случайным выбором родительского узла void unite (int x, int y) { x = find_set (x); y = find_set (y); if (rand() & 1) p[y] = x; else p[x] = y; }

35 Алгоритм Краскала с системой непересекающихся множеств Так же, как и в простой версии алгоритма Крускала, отсортируем все рёбра по неубыванию веса. Затем поместим каждую вершину в своё дерево (т.е. в своё множество) с помощью вызова функции MakeSet - на это уйдёт в сумме O (N). Перебираем все рёбра и для каждого ребра за O (1) определяем, принадлежат ли его концы разным деревьям (с помощью двух вызовов FindSet за O (1)). Наконец, объединение двух деревьев будет осуществляться вызовом Union - также за O (1). Итого мы получаем: O (M log N + N + M) = O (M log N).

36 Алгоритм Прима Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году. Время работы алгоритма – O(V * E) Можно улучшить – O(E log V + V 2 ) При использовании двоичной кучи – O(E log V ) При использовании фибоначчиевой кучи – O(E + V log V)

37 1) Выбирается произвольная вершина - она будет корнем остовного дерева; 2) Измеряется расстояние от нее до всех других вершин, т.е. находится минимальное расстояние s от дерева до вершин, которые не включены в дерево; 3) До тех пор пока в дерево не добавлены все вершины делать: - найти вершину u, расстояние от дерева до которой минимально; - добавить ее к дереву; - пересчитать расстояния от невключенных вершин до дерева следующим образом: если расстояние до какой-либо вершины от u меньше текущего расстояния s от дерева, то в s записывается новое расстояние.

38 Запускаем алгоритм обхода графа, начиная с произвольной вершины. В качестве контейнера выбираем очередь с приоритетами. Приоритет – текущая величина найденного расстояния до уже построенной части остовного дерева. Релаксации подвергаются прямые и обратные ребра n π 0 d В результате работы получаем список ребер остовного дерева вместе с весами

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

40 Алгоритм Прима (другой алгоритм) На каждом шаге вычеркиваем из графа дугу максимальной стоимости с тем условием, что она не разрывает граф на две или более компоненты связности, т.е. после удаления дуги граф должен оставаться связным. Для того, чтобы определить, остался ли граф связным, достаточно запустить поиск в глубину от одной из вершин, связанных с удаленной дугой. Условие окончания алгоритма? Например, пока количество ребер больше либо равно количеству вершин, нужно продолжать, иначе – остановиться.

41 Пример м