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

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

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

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

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

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

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

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

 function [math]paint[/math]([math]v[/math], color):
   colors[[math]v[/math]] [math]\leftarrow[/math] color
   for [math]u \in V :  (u, v) \in E[/math]:
     if colors[[math]u[/math]] == 0:
       if ret[[math]u[/math]] > enter[[math]v[/math]]:
         maxColor++
         [math]paint[/math]([math]u[/math], maxColor)
       else:
         [math]paint[/math]([math]u[/math], color)
 ...
 for [math]v \in V[/math] :
   colors[[math]v[/math]] [math]\leftarrow[/math] 0
 maxColor [math]\leftarrow[/math] 0
 for [math]v \in V[/math] :
   if colors[[math]v[/math]] == 0:
     maxColor++
     [math]paint[/math]([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
• Визуализация — Построение компонент реберной двусзяности