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

Основные понятия

• Реберная двусвязность
• Компонента реберной двусвязности

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

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

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

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

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

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

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

 void paint(v, цвет):
   colors(v) := цвет
   для всех вершин u, смежных v:
     если colors(u) равен нулю (вершина не покрашена):
       если ret(u) = enter(u):
         увеличиваем максимальный цвет
         paint(u, максимальный цвет)
       иначе:
         paint(u, цвет)
 ...
 обнуляем массив colors
 максимальный цвет := 0
 для всех вершин v графа:
   если colors(v) = 0:
     увеличиваем максимальный цвет
     paint(v, максимальный цвет)

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

Время работы алгоритма будет время работы двух запусков dfs, то есть 2 * [math] 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(u)
      [math] ret[v] \leftarrow min(ret[v], ret[u]) [/math]
      if [math]ret[u] \gt  enter[v][/math] 
        [math]paint(u)[/math] 

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

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

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

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

Литература

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

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