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

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

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

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

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

Первый проход: Ищем в графе мосты.

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

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

function paint([math]v[/math], color):
  colors[[math]v[/math]] = color
  for [math](u, v) \in E[/math]:
    if colors[[math]u[/math]] == 0:
      if up[[math]u[/math]] > tin[[math]v[/math]]:
        maxColor++
        paint([math]u[/math], maxColor)
      else:
        paint([math]u[/math], color)

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

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

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

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

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

Псевдокод

 function [math]paint[/math]([math]v[/math]):
   maxColor++
    while stack.top() != [math]v[/math] and not stack.empty()
        colors[stack.top()] [math]\leftarrow[/math] maxColor
        stack.pop()
 

 function [math]dfs[/math]([math] v [/math])
  time[math] \leftarrow[/math] time + [math]1[/math]
  stack.push([math]v[/math])
  enter[[math]v[/math]] [math]\leftarrow[/math] time
  ret[[math]v[/math]] [math] \leftarrow[/math] time
  for [math]u \in V : (v, u) \in E[/math]:
    if [math](v, u)[/math] — обратное ребро
      ret[[math]v[/math]] [math] \leftarrow [/math] min(ret[[math]v[/math]], enter[[math]u[/math]])
    if not visited[[math]u[/math]]
      [math]dfs[/math]([math]u[/math])
      ret[[math]v[/math]] [math]\leftarrow[/math] min(ret[[math]v[/math]], ret[[math]u[/math]])
      if ret[[math]u[/math]] > enter[[math]v[/math]] 
          [math]paint[/math]([math]u[/math]) 

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

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

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

• Седжвик Р. Фундаментальные алгоритмы на C++. Часть 5: Алгоритмы на графах. Пер. с англ. — СПб.: ООО «ДиаСофтЮП», 2002. — С. 123-128
• Кузнецов В.А., Караваев. А.М. "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007
• Визуализация — Построение компонент реберной двусзяности