== Основные понятия ==
*[[Отношение реберной двусвязности#Реберная двусвязность|Реберная двусвязность]]
*[[Отношение реберной двусвязности#Компоненты реберной двусвязности|Компонента реберной двусвязности]]
Построение компонент реберной двусвязности будет осуществляться с помощью [[Обход в глубину, цвета вершин|обхода в глубину]].
== Двупроходный алгоритм ==
Первый способ найти искомые компоненты {{- --}} сначала определить критерий перехода в новую [[Отношение реберной двусвязности#Компоненты реберной двусвязности|компоненту реберной двусвязности]], а затем покрасить вершины графа в нужные цвета.
Первый проход определяет для каждой вершины <tex>v</tex> две величины: <tex>enter(v)</tex> - время входа поиска в глубину в вершину и Определим критерий перехода к новой компоненте.Воспользуемся ранее доказанной [[Использование обхода в глубину для поиска мостов#Функция Лемма | ret(v)леммой]]. Получается {{---}} перешли по мосту, следовательно началась новая компонента.
Определим критерий перехода к новой компоненте.Воспользуемся ранее доказанной '''Первый проход:''' запустим [[Использование обхода в глубину для поиска мостов#Лемма | леммойалгоритм для поиска мостов]], чтобы посчитать две величины: <tex>tin(v)</tex> и <tex>up(v)</tex>. '''Второй проход:''' окрашиваем вершины, т.е. если перешли по мосту, то оказались в новой компоненте реберной двусвязности.
Основываясь на этом=== Псевдокод второго прохода ===* В переменной <tex>\mathtt{color}</tex> хранится цвет текущей компоненты.* <tex>\mathtt{maxColor}</tex> изначально равен <tex>0</tex>, определим алгоритм окраски вершин графа. Перешли по мостучто эквивалентно тому, следовательно началась новая что никакая компонентане окрашена.
Псевдокод второго прохода '''function''' paint(<tex>v</tex>, color): colors[<tex>v</tex>] = color '''for''' <tex>(u, v) \in E</tex>: '''if''' colors[<tex>u</tex>] == 0: '''if''' up[<tex>u</tex>] > tin[<tex>v</tex>]: maxColor++ paint(<tex>u</tex>, maxColor) '''else''': paint(<tex>u</tex>, color)
'''void paintfunction''' solve(v, цвет): colors( '''for''' <tex>v) \in V</tex> := цвет для всех вершин u, смежных colors[<tex>v: если colors(u) равен нулю (вершина не покрашена): если ret(u) </tex>] = enter(u):0 увеличиваем максимальный цвет '''if''' '''not''' visited[<tex>v</tex>] paint dfs(u, максимальный цвет) иначе: paint(u, цвет<tex>v</tex>) ... обнуляем массив colors максимальный цвет : maxColor = 0 для всех вершин '''for''' <tex>v графа\in V</tex> : если '''if''' colors([<tex>v) </tex>] == 0: увеличиваем максимальный цвет maxColor++ paint(<tex>v</tex>, максимальный цветmaxColor)'''
Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цвет.
Время работы алгоритма будет время работы двух запусков dfs, то есть 2 * <tex> 2 \cdot O(|V| + |E|)</tex>, что есть <tex> O(|V| + |E|)</tex>.
== Однопроходный алгоритм ==
Можно найти компоненты реберной двусвязности за один проход, используя стек.
Рекурсивый алгоритм на основе обхода в глубину.
Если мы посетили вершину, то добавляем её в стек. Теперь определим, когда надо окрасить компоненту.
Если мы возвращаясь (в рекурсии) обратно оказались в вершине, которая является вершиной моста, то все вершины, находящиеся, до текущей в стеке, принадлежат этой компоненте. Это следует из того, что [[Граф компонент реберной двусвязности | граф блоков и мостов, является деревом]]. По свойству обхода в глубину, мы окажемся в висячей вершине, покрасим её, то есть эту компоненту покрасим. Её можно выкинут и рассматривать оставшийся граф. Действуя по аналогии мы всегда выкидываем компоненту реберной двусвязности следовательно, если мы вернулись в вершину, которая была концом нашего моста, то все вершины лежащие до нашей в стеке, принадлежат данной компоненте, либо если моста нет, то окрашиваемся всё, что лежит в стеке.
Псевдокод:
'''void paint(int v): maxcolor++ while (пока вершина стека не вершина Однопроходный алгоритм строится на базе алгоритма поиска мостов. Во-первых, создадим глобальный [[Стек|стек]], и при спуске по дереву <tex>vdfs </tex> и стек добавляем в него вершины. Во-вторых, когда возвращаемся назад, проверяем не пустойявляется ли ребро мостом (при помощи [[Использование обхода в глубину для поиска мостов#Лемма | леммы]]) извлекаем вершину стека . Если это так, то все вершины, находящиеся до текущего потомка в стеке, принадлежат одной компоненте.Заметим, что эта компонента будет висячей вершиной в дереве блоков и мостов, так как обходили граф поиском в глубину. Значит, ее можно выкинуть и красим её продолжить поиск в оставшемся графе. Действуя по аналогии в получившемся графе, найдем оставшиеся компоненты реберной двусвязности.
=== Псевдокод === '''function'''void dfspaint(вершина <tex>v, предок вершины p</tex>): добавляем вершину в в стек; maxColor++ last = -1 '''while''' last != <tex>v</tex> '''and''' '''not''' stack.empty() state colors[stack.top()] = maxColor last = stack.top() stack.pop() '''function''' dfs(<tex> v] </tex>) time = time + 1 ret stack.push(<tex>v</tex>) tin[<tex>v</tex>] = entertime up[<tex>v</tex>] = ++time для всех вершин u смежных '''for''' <tex> (v: если (, u == parent)\in E</tex>: переходим к следующей итерации если '''if''' <tex>(state[v, u] = 1):</tex> — обратное ребро ret up[<tex>v</tex>] = min(retup[<tex>v</tex>], entertin[<tex>u</tex>]) иначе: если (state '''if''' '''not''' visited[<tex>u</tex>] = 0): dfs(<tex>u, v</tex>) ret up[<tex>v</tex>] = min(retup[<tex>v</tex>], retup[<tex>u</tex>]) если (enter '''if''' up[<tex>u</tex>] > tin[<tex>v] < ret[u/tex>]): paint(<tex>u</tex>) state[v] = 2 Так же после вызова dfs нужно не забыть в конце вызвать ещё раз paint.
Теперь две вершины имеют одинаковый цвет тогда и только тогда, когда они принадлежат одной компоненте реберной двусвязности.
Итоговое время работы алгоритма <tex> O(|V| + |E|)</tex>.
== Визуализатор См. также ==* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bridges-2001| Визуализация построение [Построение компонент реберной двусзяностивершинной двусвязности]] ==Литература==Седжвик Роберт. Фундаментальные алгоритмы на C++. Часть 5: Алгоритмы на графах: Пер. с англ./Роберт Седжвик. — СПб.: ООО «ДиаСофтЮП», 2002. — С. 123-128* [[Использование обхода в глубину для поиска мостов]]
== Источники информации ==* ''Седжвик Р.'' Фундаментальные алгоритмы на C++. Часть 5: Алгоритмы на графах. Пер. с англ. — СПб.: ООО «ДиаСофтЮП», 2002. — С. 123-128* ''Кузнецов В.А.Кузнецов, Караваев. А.М.Караваев. '' "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bridges-2001| Визуализация {{---}} Построение компонент реберной двусзяности]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]
