Обходы графа

Дисциплина «Алгоритмы и структуры данных» Лекция 10. Обходы графа Филатов Вячеслав Валерьевич к.т.н., доцент кафедры КБ-2 «Прикладные информационные технологии» Способы обходов графа. Различают следующие обходы графов • Методом поиска в глубину (depth-first-search), dfs() • Методом поиска в ширину (breadth-first-search), bfs() Обходом графа называется систематическая процедура поиска еще не посещенных узлов графа с целью выполнения определенных действий с текущим узлом (как правило - единоразово). Способы обходов графа. Обходы графов • В глубину (depth-first-search), dfs() • В ширину (breadth-first-search), bfs() Способы обходов графа. Обходы графов • В глубину (depth-first-search), dfs() • В ширину (breadth-first-search), bfs() Поиск в ширину работает путем последовательного просмотра отдельных уровней графа, начиная с узла-источника u (подобно распространению волны от источника). Способы обходов графа. Обходы графов • В глубину (depth-first-search), dfs(u) • В ширину (breadth-first-search), bfs(u) Поиск в ширину работает путем последовательного просмотра отдельных уровней графа, начиная с узла-источника u (подобно распространению волны от источника). Поиск в ширину был формально предложен Э. Ф. Муром в контексте поиска пути в лабиринте. Ли независимо открыл этот же алгоритм при формализации алгоритмов трассировки печатных плат в 1961 году (алгоритм волновой трассировки, алгоритм поиска кратчайшего пути на планарном графе) Обход графа в глубину Принцип обхода графа в глубину Принцип обхода графа в глубину Принцип обхода графа в глубину Принцип обхода графа в глубину Принцип обхода графа в глубину Это конкретно какую? Принцип обхода графа в глубину В лексикографическом порядке! Принцип обхода графа в глубину Пример обхода графа в глубину Обход графа в глубину (depth-first-search), dfs() Пусть а – стартовая вершина • Переходим из нее в вершину b. • У вершины b нет смежных непосещенных вершин, вернемся к вершине a. • Из a переходим в d, из d переходим в c. • У вершины с нет смежных непосещенных вершин, вернемся к вершине d. • Из d переходим в e. • У вершины e нет смежных непосещенных вершин, вернемся к вершине d. • У вершины d нет смежных непосещенных вершин, вернемся к вершине a. • У вершины a нет смежных непосещенных вершин. Все вершины графа посещены, получили глубинное остовное дерево Обход графа: построение глубинного остовного леса (ГОЛ) (ребро дерева) Обход графа в глубину: три цвета маркировки В ряде случаев используют три цвета окраски (маркировки) вершин для определения класса дуги • белая (mark [v]=0), если вершина не посещалась, то есть к ней процедура dfs() не применялась • серая (mark [v]= 1), если вершина посещается, то есть обработка всех смежных с ней вершин не завершена • черная (mark [v]= 2), если для данной вершины обработка всех смежных с ней вершин завершено Принцип определения класса дуги в глубинном остовном лесу Дуга (v, w) графа G=(V, E) (v – текущая при обходе вершина) будет • ребром дерева, если mark[v] = серый И mark[w] = белый • прямым ребром, если mark[v] = серый И mark[w] = черный • обратным ребром, если mark[v] = серый И mark[w] = серый • поперечным ребром, если mark[v] = серый И mark[w] = черный Принцип определения класса дуги в глубинном остовном лесу Дуга (v, w) графа G=(V, E) (v – текущая при обходе вершина) будет • ребром дерева, если mark[v] = серый И mark[w] = белый • прямым ребром, если mark[v] = серый И mark[w] = черный • обратным ребром, если mark[v] = серый И mark[w] = серый • поперечным ребром, если mark[v] = серый И mark[w] = черный Выводы: 1. Для определения ацикличности графа (факта отсутствия циклов) достаточно трех цветов маркировки и факта отсутствия какой-либо обратной дуги 2. Для определения всех классов дуг одной только маркировки не хватает. Принцип определения класса дуги в глубинном остовном лесу ? Как определить, Дуга (v, w) графа G=(V, E) (vкакие – текущая обходе вершина ) будет узлы при являются потомками? • ребром дерева, если mark[v] = серый И mark[w] = белый • прямым ребром, если mark[v] = серый И mark[w] = черный И узел v является потомком узла w в глубинном дереве • обратным ребром, если mark[v] = серый И mark[w] = серый • поперечным ребром, если mark[v] = серый И mark[w] = черный И узел v НЕ является потомком узла w в глубинном дереве (т.е. они находятся в различных деревьях или поддеревьях глубинного леса). Принцип определения класса дуги в глубинном остовном лесу ! Ответ: с помощью пары глубинных чисел – счетных Дуга (v, w) графа G=(V, E) (v – текущаяизменения при обходе вершина будет моментов цветов) (dfn, fin) • ребром дерева, если mark[v] = серый И mark[w] = белый • прямым ребром, если mark[v] = серый И mark[w] = черный И узел v является потомком узла w в глубинном дереве • обратным ребром, если mark[v] = серый И mark[w] = серый • поперечным ребром, если mark[v] = серый И mark[w] = черный И узел v НЕ является потомком узла w в глубинном дереве (т.е. они находятся в различных деревьях или поддеревьях глубинного леса). Принцип определения класса дуги в глубинном остовном лесу Дуга (v, w) графа G=(V, E) (v – текущая при обходе вершина) будет • ребром дерева, если mark[v] = серый И mark[w] = белый • прямым ребром, если mark[v] = серый И mark[w] = черный И узел v является потомком узла w в глубинном дереве • обратным ребром, если mark[v] = серый И mark[w] = серый • поперечным ребром, если mark[v] = серый И mark[w] = черный И узел v НЕ является потомком узла w в глубинном дереве (т.е. они находятся в различных деревьях или поддеревьях глубинного леса). Обхода графа: построение ГОЛ Обход графа: построение ГОЛ Обход графа: анализ построения ГОЛ Пример обхода графа: построение ГОЛ V mark dfn, d fin, f parent v1 v2 v3 v4 v5 v6 v7 v8 Пример обхода графа: построение ГОЛ Этап 1. Начальная инициализация. mark – признак посещения вершины, parent – указатель, индекс или курсор на отца – позволяет построить (сохранить структуру дерева) для последующей возможной обработке. V v1 v2 v3 v4 v5 v6 v7 v8 mark -1 -1 -1 -1 -1 -1 -1 -1 dfn fin parent Пример обхода графа: построение ГОЛ Этап 2. Выбор в лексикографическом порядке стартовой точки для построения дерева обхода в глубину. Инициализация глубинного числа (dfn), окрашивание в серый цвет, для поиска всех потомков текущего узла. Корень дерева: parent [v1]=-1 V v1 v2 v3 v4 v5 v6 v7 v8 mark 1 dfn 1 -1 -1 -1 -1 -1 -1 -1 fin parent -1 Пример обхода графа: построение ГОЛ Иллюстрация перехода к первой в лексикографическом порядке («углубление») не посещенной вершине v2 , смежной с текущей v1. V v1 v2 v3 v4 v5 v6 v7 v8 mark 1 1 dfn 1 2 -1 -1 -1 -1 -1 -1 -1 fin parent Пример обхода графа: построение ГОЛ Дальнейшее «углубление»: переход к вершине v3 , смежной с текущей v2, все вершины окрашены в серый цвет – обработка смежных вершин еще не завершена. V v1 v2 v3 v4 v5 v6 v7 v8 mark 1 1 1 dfn 1 2 3 -1 1 -1 -1 -1 -1 -1 fin parent Пример обхода графа: построение ГОЛ Завершение обработки вершины v3 , формирование глубинного значения завершения вершины (fin), окрашивание вершины v3 в черный цвет (обработка вершины завершена). V v1 v2 v3 v4 v5 v6 v7 v8 mark 1 1 2 dfn 1 2 3 -1 -1 -1 -1 -1 fin parent 4 -1 1 Пример обхода графа: построение ГОЛ Завершение обработки вершины v4 , формирование глубинного значения завершения вершины (fin), окрашивание вершины v4 в черный цвет (обработка вершины завершена). V v1 v2 v3 v4 v5 v6 v7 v8 mark 1 1 2 2 dfn 1 2 3 5 4 6 1 1 -1 -1 -1 -1 fin parent -1 Пример обхода графа: построение ГОЛ Завершение обработки вершины v2 , все потомки данного узла обработаны, формирование глубинного значения завершения вершины (fin), окрашивание вершины v2 в черный цвет. V v1 v2 v3 v4 v5 v6 v7 v8 mark 1 2 2 2 dfn 1 2 3 5 7 4 6 1 1 -1 -1 -1 -1 fin parent -1 Пример обхода графа: построение ГОЛ Завершение обработки вершины v1 , все потомки данного узла обработаны, дерево, корнем которого является v1 сформировано, вершина v1 окрашивается в черный цвет. Начало построения дерева с корнем v6. V v1 v2 v3 v4 v5 v6 v7 v8 mark 2 2 2 2 2 dfn 1 2 3 5 8 fin 10 7 4 6 9 parent -1 1 1 -1 -1 -1 Пример обхода графа: построение ГОЛ V v1 v2 v3 v4 v5 v6 v7 v8 mark 2 2 2 2 2 2 2 2 dfn 1 2 3 5 8 11 12 14 fin 10 7 4 6 9 16 13 15 - v1 v2 v2 v1 - v6 v6 parent Итоговое заполнение значениями массива структур вершин. Пример обхода графа: построение ГОЛ Итоговое дерево обхода в глубину. (цветом обозначены соответствующие типы дуг в дереве) Пример обхода графа: построение ГОЛ V v1 v2 v3 v4 v5 v6 v7 v8 mark 2 2 2 2 2 2 2 2 dfn 1 2 3 5 8 11 12 14 fin 10 7 4 6 9 16 13 15 - v1 v2 v2 v1 - v6 v6 parent Свойства поиска в глубину Свойства поиска в глубину Использование значений моментов начала и завершения обработки вершин позволяет без формирования и, соответственно, анализа структуры дерева определять для произвольного узла всех предков и потомков произвольного узла и, соответственно, типа дуги, включая обратную дугу (для поперечны дуг возможно пересечение или нахождения вне отрезка для смежного узла. Пример использования обхода в глубину: топологическая сортировка Топологическая сортировка — упорядочивание вершин бесконтурного (ациклического) ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин, т.е. это процесс линейного упорядочивания вершин ациклического орграфа таким образом, что если существует дуга от вершины i к вершине j, то в упорядоченном списке вершин орграфа вершина i предшествует вершине j. Топологическая сортировка В чем «подвох»? Топологическая сортировка Если вершина серая — найден цикл, топологическая сортировка невозможна. Алгоритм Тарьяна Пример использования обхода в глубину: нахождение сильно связанных компонентов графа (самостоятельно к практическому занятию) Обход в ширину (волновой метод) Исходный граф. Обход в ширину (волновой метод) Выбор источника обхода. Обход в ширину (волновой метод) d=1 d=2 Красный узел - источник. Зеленые – смежные с ним, Заметим, что зеленые равноудалены на расcтояние d=1, а смежные с ними – на расстояние d =2. Поэтому данный алгоритм и называется волновым. Обход в ширину (волновой метод) d=1 d=2 Обобщенный алгоритм обхода 1. Инициализация. Все вершины не посещены. Список для обработки пустой. Занести источник в список, пометить как посещенный 2. На каждом шаге, выбирается очередной элемент из списка узлов. 3. Для текущего узла, перебираются все смежные не посещённые узлы и заносятся в список для последующей обработки, маркируя как посещенный. 4. Повторять шаги 2-4, пока список не пустой, иначе завершить алгоритм. Обход в ширину (волновой метод) d=1 d=2 Очередь: Обход в ширину (1/2) Обход в ширину (2/2) Обход в ширину (волновой метод) Очередь: u 1 V 1 2 3 4 5 6 7 8 цвет 1 предок 0 d - текущая вершина Обход в ширину (волновой метод) Очередь: выход 2 вход u 1 V 1 2 3 4 5 6 7 8 цвет 1 предок 0 1 d - текущая вершина Обход в ширину (волновой метод) Очередь: выход 2 4 5 вход u 1 V 1 2 3 4 5 6 7 8 цвет 1 предок 0 1 1 1 d - текущая вершина Обход в ширину (волновой метод) Очередь: 2 4 5 u 1 V 1 2 3 4 5 6 7 8 цвет 1 предок 0 2 1 1 1 1 d - текущая вершина Обход в ширину (волновой метод) Очередь: 2 4 5 u 1 V 1 2 3 4 5 6 7 8 цвет 2 предок 0 1 1 1 1 1 1 1 1 1 d - текущая вершина Обход в ширину (волновой метод) Очередь: 2 4 5 u 2 V 1 2 3 4 5 6 7 8 цвет 2 предок 0 1 1 1 1 1 1 1 1 1 d - текущая вершина Обход в ширину (волновой метод) Очередь: 4 5 u 2 V 1 2 3 4 5 6 7 8 цвет 2 предок 0 1 1 1 1 1 2 1 1 1 2 1 1 d - текущая вершина Обход в ширину (волновой метод) Очередь: 4 5 3 u 2 V 1 2 3 4 5 6 7 8 цвет 2 предок 0 2 1 1 1 1 2 1 1 1 2 1 1 d - текущая вершина Обход в ширину (волновой метод) Очередь: 4 5 3 u 4 V 1 2 3 4 5 6 7 8 цвет 2 предок 0 2 1 1 1 2 1 6 1 1 d - текущая вершина Обход в ширину (волновой метод) Очередь: 5 3 6 u 4 V 1 2 3 4 5 6 7 8 цвет 2 предок 0 2 1 1 1 1 1 2 1 1 4 1 2 1 1 2 d - текущая вершина Обход в ширину (волновой метод) Очередь: 3 6 7 8 u 5 V 1 2 3 4 5 6 7 8 цвет 2 предок 0 2 2 2 1 1 1 1 1 2 1 4 5 5 1 2 1 1 2 2 2 d - текущая вершина Обход в ширину (волновой метод) Очередь: 8 u 7 V 1 2 3 4 5 6 7 8 цвет 2 предок 0 2 2 2 2 2 1 1 1 2 1 1 4 5 5 1 2 1 1 2 2 2 d - текущая вершина Обход в ширину – итоговые значения вспомогательных структур данных Очередь: пуста u V - текущая вершина 1 2 3 4 5 6 7 8 цвет 2 предок 0 2 2 2 2 2 2 2 1 2 1 1 4 5 5 1 2 1 1 2 2 2 d Обход в ширину: нахождение кратчайшего пути в лабиринте старт фин Обход в ширину: нахождение кратчайшего пути в лабиринте старт фин Обход в ширину: нахождение кратчайшего пути в лабиринте фин Обход в ширину: нахождение кратчайшего пути в лабиринте фин Обход в ширину: нахождение кратчайшего пути в лабиринте фин Обход в ширину: нахождение кратчайшего пути в лабиринте фин Обход в ширину: нахождение кратчайшего пути в лабиринте фин Обход в ширину: нахождение кратчайшего пути в лабиринте фин Обход в ширину: нахождение кратчайшего пути в лабиринте фин Обход в ширину: нахождение кратчайшего пути в лабиринте фин Обход в ширину: нахождение кратчайшего пути в лабиринте фин Обход в ширину: нахождение кратчайшего пути в лабиринте фин Обход в ширину: нахождение кратчайшего пути в лабиринте фин Обход в ширину: нахождение кратчайшего пути в лабиринте фин Обход в ширину: нахождение кратчайшего пути в лабиринте фин Обход в ширину: нахождение кратчайшего пути в лабиринте фин Обход в ширину: нахождение кратчайшего пути в лабиринте фин Обход в ширину: нахождение кратчайшего пути в лабиринте фин Обход в ширину: нахождение кратчайшего пути в лабиринте фин Обход в ширину: нахождение кратчайшего пути в лабиринте фин Обход в ширину: нахождение кратчайшего пути в лабиринте Обход в ширину: нахождение кратчайшего пути в лабиринте Спасибо за внимание!