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

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

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

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

Первым проходом запустим алгоритм для поиска мостов, чтобы посчитать две величины: [math]enter(v)[/math] и [math]ret(v)[/math].

Определим критерий перехода к новой компоненте. Воспользуемся ранее доказанной леммой.

Основываясь на этом, определим алгоритм окраски вершин графа: перешли по мосту, следовательно началась новая компонента.

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

 function [math]paint(v, color)[/math]:
   [math]colors[v]\leftarrow[/math] color
   for [math]u \in V :  (u, v) \in E[/math]:
     if [math]colors[u][/math] == 0:
       if [math]ret[u] \gt  enter[v][/math]:
         maxColor++
         [math]paint[/math]([math]u[/math], maxColor)
       else:
         [math]paint[/math]([math]u[/math], color)
 ...
 for [math]v \in V[/math] :
   [math]colors[v] \leftarrow 0 [/math]
 maxColor [math]\leftarrow 0[/math]
 for [math]v \in V[/math] :
   if [math]colors[v] == 0[/math]:
     maxColor++
     [math]paint[/math]([math]v[/math], maxColor)

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

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

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

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

Псевдокод:

 paint([math]v[/math]):
   [math]maxcolor[/math]++
    while (пока вершина стека не вершина [math]v[/math] и стек не пустой)
        извлекаем вершину стека и красим её 

 dfs([math] v [/math])
  [math] time \leftarrow time + 1[/math]
  [math] stack.push(v) [/math]
  [math]enter[v] \leftarrow time[/math]
  [math]ret[v] \leftarrow time [/math]
  for всех [math]u[/math] смежных с [math]v[/math]
    if [math](v, u)[/math] — обратное ребро
        [math]ret[v] \leftarrow min(ret[v], enter[u])[/math]
    if вершина [math]u[/math] — белая
      dfs([math]u[/math])
      [math] ret[v] \leftarrow min(ret[v], ret[u]) [/math]
      if [math]ret[u] \gt  enter[v][/math] 
          paint([math]u[/math]) 

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

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

Визуализатор

• Визуализация построение компонент реберной двусзяности

Литература

Седжвик Р. Фундаментальные алгоритмы на C++. Часть 5: Алгоритмы на графах. Пер. с англ. — СПб.: ООО «ДиаСофтЮП», 2002. — С. 123-128

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