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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 42: Строка 42:
 
== Однопроходный алгоритм ==
 
== Однопроходный алгоритм ==
  
Можно найти компоненты реберной двусвязности за один проход, используя стек.
+
 
+
Однопроходный алгоритм строится на базе алгоритма поиска мостов. Во-первых, создадим глобальный стек, и при спуске по дереву dfs добавляем в него вершины. Во-вторых, когда возвращаемся назад, проверяем не является ли ребро мостом (при помощи [[Использование обхода в глубину для поиска мостов#Лемма | леммы]]). Если это так, то то все вершины, находящиеся до текущего сына в стеке, принадлежат одной компоненте, эта компонента будет висячей вершиной в дереве блоков и мостов, так как обходили граф поиском в глубину. Значит, ее можно выкинуть и продолжить поиск в оставшемся графе. Действуя по аналогии в оставшемся графе, найдем оставшиеся компоненты реберной двусвязности.
Рекурсивый алгоритм на основе обхода в глубину.
+
 
Если мы посетили вершину, то добавляем её в стек. Теперь определим, когда надо окрасить компоненту.
 
Если мы возвращаясь рекурсии) обратно  оказались в вершине, которая является вершиной моста, то все вершины, находящиеся, до текущей в стеке, принадлежат этой компоненте. Это следует из того, что [[Граф компонент реберной двусвязности | граф блоков и мостов, является деревом]]. По свойству обхода в глубину, мы окажемся в висячей вершине, покрасим её, то есть эту компоненту покрасим. Её можно выкинут и рассматривать оставшийся граф. Действуя по аналогии мы всегда выкидываем компоненту реберной двусвязности следовательно, если мы вернулись в вершину, которая была концом нашего моста, то все вершины лежащие до нашей в стеке, принадлежат данной компоненте, либо если моста нет, то окрашиваемся всё, что лежит в стеке.  
 
 
Псевдокод:
 
Псевдокод:
  
Строка 56: Строка 54:
 
    
 
    
  
   '''void dfs(вершина v, предок вершины p):
+
   '''dfs'''(<tex> v </tex>)
    добавляем вершину в в стек;
+
  <tex> time \leftarrow time + 1</tex>
    state[v] = 1
+
  <tex> stack.push(v) </tex>
    ret[v] = enter[v] = ++time
+
  <tex>enter[v] \leftarrow time</tex>
    для всех вершин u смежных v:
+
  <tex>ret[v] \leftarrow time </tex>
      если (u == parent):
+
  '''for''' всех <tex>u</tex> смежных с <tex>v</tex>
        переходим к следующей итерации
+
    ''if'' <tex>(v, u)</tex> - обратное ребро
      если (state[u] = 1):
+
      <tex>ret[v] \leftarrow min(ret[v], enter[u])</tex>
          ret[v] = min(ret[v], enter[u])
+
    '''if''' вершина <tex>u</tex> - белая
        иначе:
+
      '''dfs'''(u)
          если (state[u] = 0):
+
      <tex> ret[v] \leftarrow min(ret[v], ret[u]) </tex>
            dfs(u, v)
+
      '''if''' <tex>ret[u] > enter[v]</tex>
            ret[v] = min(ret[v], ret[u])
+
        <tex>paint(u)</tex>
            если (enter[v] < ret[u]):
 
            paint(u)
 
    state[v] = 2
 
 
   
 
   
  

Версия 07:51, 23 ноября 2011

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

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

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

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

Первый проход определяет для каждой вершины [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].

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

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

Псевдокод:

 void paint(int v):
   maxcolor++
     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