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

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

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

Первый проход Используем первый проход, чтобы найти точки сочленения.
Определим для каждой вершины две величины: [math] enter [i] [/math] - время входа поиска в глубину в вершину [math] i [/math], [math] return [i] [/math] – минимальное из времен входа вершин, достижимых из [math] i [/math] по дереву [math] dfs [/math] и не более, чем одному обратному ребру. Ребро к родителю не является обратным ребром.

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

   dfs([math]v[/math], [math]parent[/math])
       [math]enter[v] \leftarrow return[v] \leftarrow time[/math]++
       для всех  вершин [math]u[/math] смежных [math]v[/math]:
           если ([math]u[/math] родитель) 
               переходим к следующей итерации
           если ([math]u[/math] посещена)
               [math]return[v] \leftarrow min(return[v], enter[u])[/math]
           иначе
               dfs([math]u, v[/math])
               [math]return[v] \leftarrow min(return[v], return[u])[/math]

   start()
       для всех [math]v[/math] вершин графа:
           если ([math]v[/math] не посещена)
               [math]time \leftarrow 0[/math]
               dfs([math]v, -1[/math])

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

   dfs([math]v, c, parent[/math])
       для всех  вершин u смежных v:
           если ([math]u[/math] родитель) 
               переходим к следующей итерации
           если ([math]u[/math] не посещена)
               если ([math]return[u] \gt = enter[v][/math])
                   [math]c2 \leftarrow[/math] новый цвет
                   [math]col[vu] \leftarrow c2[/math]
                   dfs([math]u, c2, v[/math])
               иначе
                   [math]col[vu] \leftarrow c[/math]
                   dfs([math]u, c, v[/math])
           иначе:
               если ([math]enter[u] \lt = enter[v][/math])
                   [math]col[vu] \leftarrow c[/math]          
   start()
       для всех v вершин графа:
           если ([math]v[/math] не посещена)
               dfs([math]v, -1, -1[/math])

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

Время работы двупроходного алгоритма

В алгоритме выполняется два прохода [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] будут будут добавлены в стеке после дуги ведущей из точки сочленения в блок. В стеке в момент обнаружения точки сочленения будут находиться только дуги блока, связанного с ней, т.к. блоки найденный до него (если таковые имеется) будет извлечен уже из стека и помечены в свой цвет.
Псевдокод:

   void dfs(v, parent) {
       enter[v] = return[v] = time++;
       used[v] = true;
       для всех  вершин u смежных v:
           если (u == parent): 
               переходим к следующей итерации
           если (!used[u]):
               stack.push(vu);
               dfs(u, v);
               если (return[u] >= enter[v]):
                   c = newColor()
                   пока (stack.top() <> (vu)):
                       color[stack.top()] = c;
                       stack.pop();
                   color[vu] = c;
                   stack.pop();
               если (return[u] < return[v]):
                   return[v] = return[u];
           иначе:
               если (enter[u] < enter[v]): 
                   stack.push(vu);
               если (return[v] > enter[u]):
                   return[v] = return[u];
   }
   void start() {
       used для всех вершин заполняем false
       для всех v вершин графа:
           если (!used[v]):
               time = 0;
               dfs(v, -1);
   }

См. также

• Использование обхода в глубину для поиска точек сочленения
• Построение компонент реберной двусвязности
• Отношение вершинной двусвязности

Литература

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