Построение компонент рёберной двусвязности

2019-10-14T01:19:58Z

176.59.14.112:

Построение компонент реберной двусвязности будет осуществляться с помощью [[Обход в глубину, цвета вершин|обхода в глубину]].

== Двупроходный алгоритм ==

Первый способ найти искомые компоненты {{---}} сначала определить критерий перехода в новую [[Отношение реберной двусвязности#Компоненты реберной двусвязности|компоненту реберной двусвязности]], а затем покрасить вершины графа в нужные цвета.

Определим критерий перехода к новой компоненте.
Воспользуемся ранее доказанной [[Использование обхода в глубину для поиска мостов#Лемма | леммой]]. Получается {{---}} перешли по мосту, следовательно началась новая компонента.

'''Первый проход:''' запустим [[Использование обхода в глубину для поиска мостов|алгоритм для поиска мостов]], чтобы посчитать две величины: <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)

'''function''' solve():
'''for''' <tex>v \in V</tex> :
colors[<tex>v</tex>] = 0
'''if''' '''not''' visited[<tex>v</tex>]
dfs(<tex>v</tex>)
maxColor = 0
'''for''' <tex>v \in V</tex> :
'''if''' colors[<tex>v</tex>] == 0:
maxColor++
paint(<tex>v</tex>, maxColor)

Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цвет.

Время работы алгоритма будет время работы двух запусков dfs, то есть <tex>2 \cdot O(|V| + |E|)</tex>, что есть <tex> O(|V| + |E|)</tex>.

== Однопроходный алгоритм ==

Однопроходный алгоритм строится на базе алгоритма поиска мостов. Во-первых, создадим глобальный [[Стек|стек]], и при спуске по дереву <tex> dfs </tex> добавляем в него вершины. Во-вторых, когда возвращаемся назад, проверяем не является ли ребро мостом (при помощи [[Использование обхода в глубину для поиска мостов#Лемма | леммы]]). Если это так, то все вершины, находящиеся до текущего потомка в стеке, принадлежат одной компоненте.Заметим, что эта компонента будет висячей вершиной в дереве блоков и мостов, так как обходили граф поиском в глубину. Значит, ее можно выкинуть и продолжить поиск в оставшемся графе. Действуя по аналогии в получившемся графе, найдем оставшиеся компоненты реберной двусвязности.

=== Псевдокод ===

'''function''' paint(<tex>v</tex>):
maxColor++
last = -1
'''while''' last != <tex>v</tex> '''and''' '''not''' stack.empty()
colors[stack.top()] = maxColor
last = stack.top()
stack.pop()

'''function''' dfs(<tex> v </tex>)
time = time + 1
stack.push(<tex>v</tex>)
tin[<tex>v</tex>] = time
up[<tex>v</tex>] = time
'''for''' <tex> (v, u) \in E</tex>:
'''if''' <tex>(v, u)</tex> — обратное ребро
up[<tex>v</tex>] = min(up[<tex>v</tex>], tin[<tex>u</tex>])
'''if''' '''not''' visited[<tex>u</tex>]
dfs(<tex>u</tex>)
up[<tex>v</tex>] = min(up[<tex>v</tex>], up[<tex>u</tex>])
'''if''' up[<tex>u</tex>] > tin[<tex>v</tex>]
paint(<tex>u</tex>)

Так же после вызова dfs нужно не забыть в конце вызвать ещё раз paint.

Теперь две вершины имеют одинаковый цвет тогда и только тогда, когда они принадлежат одной компоненте реберной двусвязности.

Время работы dfs <tex> O(|V| + |E|)</tex>. Покраска за <tex> O(|V|) </tex>.
Итоговое время работы алгоритма <tex> O(|V| + |E|)</tex>.

== См. также ==
* [[Построение компонент вершинной двусвязности]]
* [[Использование обхода в глубину для поиска мостов]]

== Источники информации ==
* ''Седжвик Р.'' Фундаментальные алгоритмы на C++. Часть 5: Алгоритмы на графах. Пер. с англ. — СПб.: ООО «ДиаСофтЮП», 2002. — С. 123-128
* ''Кузнецов В.А., Караваев. А.М.'' "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bridges-2001| Визуализация {{---}} Построение компонент реберной двусзяности]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]

Викиконспекты - Вклад участника [ru]

Построение компонент рёберной двусвязности