Просмотр исходного текста страницы Построение компонент вершинной двусвязности

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

'''Первый проход:
[[Использование обхода в глубину для поиска точек сочленения|ищем точки сочленения с помощью обхода в глубину]], заполняем массивы <tex>tin</tex> и <tex>up</tex>. <br>

'''Второй проход:
[[Точка сочленения, эквивалентные определения|точка сочленения]] принадлежит как минимум двум компонентам вершинной двусвязности.
Вершина <tex> v \ne root </tex> является точкой сочленения, если у нее есть сын <tex> u</tex>, такой что <tex> up[u] \geqslant tin[v] </tex>. <br> Это также значит, что ребро <tex> vu </tex> содержится в другой компоненте вершинной двусвязности, нежели ребро по которому мы пришли в вершину <tex> v </tex> , используя поиск в глубину. Получается, что перейдя по этому ребру, мы окажемся в другой компоненте вершинной двусвязности. <br>
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.<br>
=== Псевдокод второго прохода ===
* Во время первого запуска <tex>dfs</tex> будут заполняться массивы <tex>tin</tex> и <tex>up</tex>, поэтому при запуске функции <tex>paint</tex> мы считаем, что они уже посчитаны.
* <tex>\mathtt{maxColor}</tex> изначально равен <tex>0</tex>, что эквивалентно тому, что никакое ребро не окрашено.
* <tex>\mathtt{color}</tex> хранит в себе цвет, компоненты, из которой вызвалась функция <tex>\mathrm{paint}</tex> для текущей вершины.
* <tex>\mathtt{parent}</tex> {{---}} это вершина, из которой мы попали в текущую.

 '''function''' paint(<tex>v</tex>, color, parent):
   visited[<tex>v</tex>] = '''true'''
   '''for''' <tex> (v, u) \in E</tex>:
     '''if''' <tex>u</tex> == parent
       '''continue'''
     '''if''' '''not''' visited[<tex>u</tex>]
       '''if''' up[<tex>u</tex>] <tex>\geqslant</tex> tin[<tex>v</tex>]
         newColor = ++maxColor
         col[<tex>vu</tex>] = newColor
         paint(<tex>u</tex>, newColor, <tex>v</tex>)
       '''else'''
         col[<tex>vu</tex>] = color
         paint(<tex>u</tex>, color, <tex>v</tex>)
     '''else''' '''if''' tin[<tex>u</tex>] <tex><</tex> tin[<tex>v</tex>]
       col[<tex>vu</tex>] = color

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

Ребра каждой из компонент вершинной двусвязности окажутся окрашенными в свой цвет.
<br>
В алгоритме выполняется два прохода <tex>dfs</tex>, каждый из которых работает <tex>O(|V| + |E|)</tex>. Значит время работы алгоритма <tex>O(|V| + |E|)</tex>.

== Однопроходный алгоритм ==
Заведем [[Стек|стек]], в который будем записывать все дуги в порядке их обработки. Если обнаружена точка сочленения, дуги очередного блока окажутся в этом стеке, начиная с дуги дерева обхода, которая привела в этот блок, до верхушки стека. <br>
Таким образом, каждый раз находя компоненту вершинной двусвязности мы сможем покрасить все ребра, содержащиеся в ней, в новый цвет.
=== Доказательство корректности алгоритма ===
Предположим, что граф содержит точку сочленения <tex> i' \in V </tex> , за которой следует один или несколько блоков. Вершины из этих блоков образуют подмножество <tex> V' \subset V </tex>. В таком случае: <br>
# Все вершины <tex> V' </tex> являются потомками <tex> i' </tex> в дереве обхода;
# Все вершины <tex> V' </tex> будут пройдены в течение периода серого состояния <tex> i' </tex>;
# В <tex> G </tex> не может быть обратных дуг из <tex> V' </tex> в <tex> V \setminus V' </tex>.<br>
Значит все дуги <tex> V' </tex> будут будут добавлены в стек после дуги ведущей из точки сочленения в блок. В стеке в момент обнаружения точки сочленения будут находиться только дуги блока, связанного  с ней, т.к. блоки найденные до него (если таковые имеются) будет уже извлечены из стека и покрашены в свой цвет.<br>
=== Псевдокод ===
 '''function''' paint(<tex>v</tex>, parent):
   visited[<tex>v</tex>] = '''true'''
   tin[<tex>v</tex>] = up[<tex>v</tex>] = time++
   '''for''' <tex> (v, u) \in E</tex>:
     '''if''' <tex>u</tex> == parent 
       '''continue'''
     '''if''' '''not''' visited[<tex>u</tex>]
       stack.push(<tex>vu</tex>)
       paint(<tex>u, v</tex>)
       '''if''' up[<tex>u</tex>] <tex>\geqslant</tex> tin[<tex>v</tex>]
         color = maxColor++
         '''while''' stack.top() != (<tex>vu</tex>)
           colors[stack.top()] = color
           stack.pop()
         colors[<tex>vu</tex>] = color
         stack.pop()
       '''if''' up[<tex>u</tex>] < up[<tex>v</tex>]
         up[<tex>v</tex>] = up[<tex>u</tex>]
     '''else''' '''if''' tin[<tex>u</tex>] < tin[<tex>v</tex>] 
       stack.push(<tex>vu</tex>)
       '''if''' tin[<tex>u</tex>] < up[<tex>v</tex>]
         up[<tex>v</tex>] = tin[<tex>u</tex>]
     '''else''' '''if''' up[<tex>v</tex>] > tin[<tex>u</tex>]
       up[<tex>v</tex>] = up[<tex>u</tex>]

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

Во время алгоритма совершается один проход <tex>dfs</tex>, который работает за <tex>O(|V| + |E|)</tex>. Внутри него совершается еще цикл, который суммарно выполняет <tex>O(|E|)</tex> операций, т.к. каждое ребро может быть добавлено в стек только один раз. Следовательно, общее время работы алгоритма <tex>O(|V| + |E|) + O(|E|) = O(|V| + |E|)</tex>

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

== Источники информации ==
* В.А.Кузнецов, А.М.Караваев. "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/biconnected-components-2005 Дискретная математика: Алгоритмы {{---}} Компоненты двусвязности, мосты и точки сочленения]

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