Построение компонент рёберной двусвязности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Однопроходный алгоритм)
(Двупроходный алгоритм)
Строка 10: Строка 10:
 
Первый способ найти искомые компоненты - сначала определить критерий перехода в новую компоненту реберной двусвязности, а затем покрасить вершины графа в нужные цвета.
 
Первый способ найти искомые компоненты - сначала определить критерий перехода в новую компоненту реберной двусвязности, а затем покрасить вершины графа в нужные цвета.
  
Первый проход определяет для каждой вершины <tex>v</tex> две величины: <tex>enter(v)</tex> - время входа поиска в глубину в вершину, <tex>return(v)</tex> - минимальное из времен входа вершин, достижимых из <tex>v</tex> по [[Обход в глубину, цвета вершин|дереву <tex>dfs</tex>]] и не более, чем одному обратному ребру. <tex>return(v)</tex> находится как <tex>min(enter(v), return(u), enter(w))</tex> для всех <tex>u</tex> - сыновей <tex>v</tex> в дереве <tex>dfs</tex>, <tex>w</tex> - соседей <tex>v</tex> по обратным ребрам. Важно, что ребро к родителю дерева <tex>dfs</tex> не является обратным ребром обхода.
+
Первый проход определяет для каждой вершины <tex>v</tex> две величины: <tex>enter(v)</tex> - время входа поиска в глубину в вершину, [[Использование обхода в глубину для поиска мостов#Функция | <tex>ret(v)</tex>]]
  
 
Определим критерий перехода к новой компоненте.
 
Определим критерий перехода к новой компоненте.
Строка 23: Строка 23:
 
     для всех вершин u, смежных v:
 
     для всех вершин u, смежных v:
 
       если colors(u) равен нулю (вершина не покрашена):
 
       если colors(u) равен нулю (вершина не покрашена):
         если return(u) = enter(u):
+
         если ret(u) = enter(u):
 
           увеличиваем максимальный цвет
 
           увеличиваем максимальный цвет
 
           paint(u, максимальный цвет)
 
           paint(u, максимальный цвет)

Версия 05:43, 22 ноября 2011

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

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

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

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

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

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

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

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

 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]ret[v][/math] и [math]enter[v][/math]. Теперь определим, когда надо окрасить компоненту. Если мы возвращаясь обратно оказались в вершине, которая является вершиной моста, то все вершины, находящиеся, до текущей в стеке, принадлежат этой компоненте. Это следует из того, что граф блоков и мостов, является деревом. По свойству обхода в ширину, мы окажемся в висячей вершине, покрасим её, то есть эту компоненту покрасим. Её можно выкинут и рассматривать оставшийся граф. Действуя по аналогии мы всегда выкидываем компоненту реберной двусвязности следовательно, если мы вернулись в вершину, которая была концом нашего моста, то все вершины лежащие до нашей в стеке, принадлежат данной компоненте. Псевдокод:

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


 void dfs(вершина v, предок вершины p):
   добавляем вершину в в стек;
   state[v] = 1;
   ret[v] = enter[v] = ++time;
   для всех  вершин u смежных v:
     если (u == parent): 
       переходим к следующей итерации
      	если (state[u] = 1):
         ret[v] = min(ret[v], enter[u]);
       иначе:
         если (state[u] = 0):
           dfs(u, v);
           ret[v] = min(ret[v], ret[u]);
           если (enter[v] < ret[u]): 
           paint(u);	
   state[v] = 2;

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

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

См. также

Литература

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

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