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

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

Найти компоненты вершинной двусвязности неориентированного графа можно с помощью обхода в глубину.

Первый проход: Используем первый проход, чтобы найти точки сочленения.

Второй проход: Точка сочленения принадлежит как минимум двум компонентам вершинной двусвязности. Вершина [math] v \ne root [/math] является точкой сочленения, если у нее есть сын [math] u : up[u] \geqslant tin[v] [/math].
Это также значит, что ребро [math] vu [/math] содержится в другой компоненте вершинной двусвязности, нежели ребро по которому мы пришли в вершину [math] v [/math] , используя поиск в глубину. Получается, что перейдя по этому ребру, мы окажемся в другой компоненте вершинной двусвязности.
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.

Псевдокод второго прохода

function [math]dfs[/math]([math]v[/math], color, parent): for [math] u : (v, u) \in E[/math]: if [math]u[/math] == parent continue if not visited[[math]u[/math]] if up[[math]u[/math]] [math]\geqslant[/math] tin[[math]v[/math]] newColor = maxColor++ col[[math]vu[/math]] = newColor dfs([math]u[/math], newColor, [math]v[/math]) else col[[math]vu[/math]] = color dfs([math]u[/math], color, [math]v[/math]) else if up[[math]u[/math]] [math]\leqslant[/math] tin[[math]v[/math]] col[[math]vu[/math]] = color for [math] v \in V[/math]: if not visited[[math]v[/math]] dfs([math]v[/math], -1, -1)

Компоненты обозначены разным цветом

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

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

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

Доказательство корректности алгоритма

Предположим, что граф содержит точку сочленения [math] i' \in V [/math] , за которой следует один или несколько блоков. Вершины из этих блоков образуют подмножество [math] V' \subset V [/math]. В таком случае:

1. Все вершины [math] V' [/math] являются потомками [math] i' [/math] в дереве обхода;
2. Все вершины [math] V' [/math] будут пройдены в течение периода серого состояния [math] i' [/math];
3. В [math] G [/math] не может быть обратных дуг из [math] V' [/math] в [math] V \setminus V' [/math].
   

Значит все дуги [math] V' [/math] будут будут добавлены в стек после дуги ведущей из точки сочленения в блок. В стеке в момент обнаружения точки сочленения будут находиться только дуги блока, связанного с ней, т.к. блоки найденные до него (если таковые имеются) будет уже извлечены из стека и покрашены в свой цвет.

Псевдокод

   function [math]dfs[/math]([math]v[/math], parent):
       enter[[math]v[/math]] [math]\leftarrow[/math] return[[math]v[/math]] [math]\leftarrow[/math] time++
       for [math] u \in V : (v, u) \in E[/math]:
           if [math]u[/math] == parent 
               continue
           if not visited[[math]u[/math]]
               stack.push([math]vu[/math])
               [math]dfs[/math]([math]u, v[/math])
               if return[[math]u[/math]] [math]\geqslant[/math] enter[[math]v[/math]]
                   color [math]\leftarrow [/math] maxColor++
                   while stack.top() != [math]vu[/math]
                       colors[stack.top()] [math] \leftarrow [/math] color
                       stack.pop()
                   colors[[math]vu[/math]] [math]\leftarrow [/math] color
                   stack.pop()
               if return[[math]u[/math]] < return[[math]v[/math]]
                   return[[math]v[/math]] [math]\leftarrow[/math] return[[math]u[/math]]
           else
               if enter[[math]u[/math]] < enter[[math]v[/math]] 
                   stack.push([math]vu[/math])
               else return[[math]v[/math]] > enter[[math]u[/math]]
                   return[[math]v[/math]] [math]\leftarrow[/math] return[[math]u[/math]]
   ...
   for [math] v \in V[/math]:
       if not visited[[math]v[/math]]
           time [math]\leftarrow[/math] 0
           [math]dfs[/math]([math]v[/math], -1)

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

Источники информации

• В.А.Кузнецов, А.М.Караваев. "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007