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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Двупроходный алгоритм)
м (rollbackEdits.php mass rollback)
 
(не показано 7 промежуточных версий 5 участников)
Строка 8: Строка 8:
 
Воспользуемся ранее доказанной [[Использование обхода в глубину для поиска мостов#Лемма | леммой]]. Получается {{---}} перешли по мосту, следовательно началась новая компонента.
 
Воспользуемся ранее доказанной [[Использование обхода в глубину для поиска мостов#Лемма | леммой]]. Получается {{---}} перешли по мосту, следовательно началась новая компонента.
  
'''Первый проход:''' Ищем в графе мосты.
+
'''Первый проход:''' запустим [[Использование обхода в глубину для поиска мостов|алгоритм для поиска мостов]], чтобы посчитать две величины: <tex>tin(v)</tex> и <tex>up(v)</tex>.
  
'''Второй проход:''' Окрашиваем вершины.
+
'''Второй проход:''' окрашиваем вершины, т.е. если перешли по мосту, то оказались в новой компоненте реберной двусвязности.
Первым проходом запустим [[Использование обхода в глубину для поиска мостов|алгоритм для поиска мостов]], чтобы посчитать две величины: <tex>tin(v)</tex> и <tex>up(v)</tex>.
 
  
 
=== Псевдокод второго прохода ===
 
=== Псевдокод второго прохода ===
 +
* В переменной <tex>\mathtt{color}</tex> хранится цвет текущей компоненты.
 +
* <tex>\mathtt{maxColor}</tex> изначально равен <tex>0</tex>, что эквивалентно тому, что никакая компонента не окрашена.
  
 
  '''function''' paint(<tex>v</tex>, color):
 
  '''function''' paint(<tex>v</tex>, color):
Строка 43: Строка 44:
  
  
Однопроходный алгоритм строится на базе алгоритма поиска мостов. Во-первых, создадим глобальный стек, и при спуске по дереву <tex> dfs </tex> добавляем в него вершины. Во-вторых, когда возвращаемся назад, проверяем не является ли ребро мостом (при помощи [[Использование обхода в глубину для поиска мостов#Лемма | леммы]]). Если это так, то то все вершины, находящиеся до текущего потомка в стеке, принадлежат одной компоненте.Заметим, что эта компонента будет висячей вершиной в дереве блоков и мостов, так как обходили граф поиском в глубину. Значит, ее можно выкинуть и продолжить поиск в оставшемся графе. Действуя по аналогии в получившемся графе, найдем оставшиеся компоненты реберной двусвязности.
+
Однопроходный алгоритм строится на базе алгоритма поиска мостов. Во-первых, создадим глобальный [[Стек|стек]], и при спуске по дереву <tex> dfs </tex> добавляем в него вершины. Во-вторых, когда возвращаемся назад, проверяем не является ли ребро мостом (при помощи [[Использование обхода в глубину для поиска мостов#Лемма | леммы]]). Если это так, то все вершины, находящиеся до текущего потомка в стеке, принадлежат одной компоненте.Заметим, что эта компонента будет висячей вершиной в дереве блоков и мостов, так как обходили граф поиском в глубину. Значит, ее можно выкинуть и продолжить поиск в оставшемся графе. Действуя по аналогии в получившемся графе, найдем оставшиеся компоненты реберной двусвязности.
  
 
=== Псевдокод ===
 
=== Псевдокод ===
  
  '''function''' <tex>paint</tex>(<tex>v</tex>):
+
'''function''' paint(<tex>v</tex>):
    maxColor++
+
  maxColor++
    '''while''' stack.top() != <tex>v</tex> '''and''' '''not''' stack.empty()
+
  last = -1
        colors[stack.top()] <tex>\leftarrow</tex> maxColor
+
  '''while''' last != <tex>v</tex> '''and''' '''not''' stack.empty()
        stack.pop()
+
    colors[stack.top()] = maxColor
 
+
    last = stack.top()
 +
    stack.pop()
  
  '''function''' <tex>dfs</tex>(<tex> v </tex>)
+
'''function''' dfs(<tex> v </tex>)
   time<tex> \leftarrow</tex> time + <tex>1</tex>
+
   time time + 1
 
   stack.push(<tex>v</tex>)
 
   stack.push(<tex>v</tex>)
   enter[<tex>v</tex>] <tex>\leftarrow</tex> time
+
   tin[<tex>v</tex>] = time
   ret[<tex>v</tex>] <tex> \leftarrow</tex> time
+
   up[<tex>v</tex>] = time
   '''for''' <tex>u \in V : (v, u) \in E</tex>:
+
   '''for''' <tex> (v, u) \in E</tex>:
 
     '''if''' <tex>(v, u)</tex> — обратное ребро
 
     '''if''' <tex>(v, u)</tex> — обратное ребро
       ret[<tex>v</tex>] <tex> \leftarrow </tex> min(ret[<tex>v</tex>], enter[<tex>u</tex>])
+
       up[<tex>v</tex>] = min(up[<tex>v</tex>], tin[<tex>u</tex>])
 
     '''if''' '''not''' visited[<tex>u</tex>]
 
     '''if''' '''not''' visited[<tex>u</tex>]
       <tex>dfs</tex>(<tex>u</tex>)
+
       dfs(<tex>u</tex>)
       ret[<tex>v</tex>] <tex>\leftarrow</tex> min(ret[<tex>v</tex>], ret[<tex>u</tex>])
+
       up[<tex>v</tex>] = min(up[<tex>v</tex>], up[<tex>u</tex>])
       '''if''' ret[<tex>u</tex>] > enter[<tex>v</tex>]  
+
       '''if''' up[<tex>u</tex>] > tin[<tex>v</tex>]  
          <tex>paint</tex>(<tex>u</tex>)  
+
        paint(<tex>u</tex>)  
+
 
 +
Так же после вызова dfs нужно не забыть в конце вызвать ещё раз paint.
  
 
Теперь две вершины имеют одинаковый цвет тогда и только тогда, когда они принадлежат одной компоненте реберной двусвязности.
 
Теперь две вершины имеют одинаковый цвет тогда и только тогда, когда они принадлежат одной компоненте реберной двусвязности.
Строка 73: Строка 76:
 
Время работы dfs <tex> O(|V| + |E|)</tex>. Покраска за <tex> O(|V|) </tex>.
 
Время работы dfs <tex> O(|V| + |E|)</tex>. Покраска за <tex> O(|V|) </tex>.
 
Итоговое время работы алгоритма <tex> O(|V| + |E|)</tex>.
 
Итоговое время работы алгоритма <tex> O(|V| + |E|)</tex>.
 +
 +
== См. также ==
 +
* [[Построение компонент вершинной двусвязности]]
 +
* [[Использование обхода в глубину для поиска мостов]]
  
 
== Источники информации ==
 
== Источники информации ==

Текущая версия на 19:17, 4 сентября 2022

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

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

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

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

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

Второй проход: окрашиваем вершины, т.е. если перешли по мосту, то оказались в новой компоненте реберной двусвязности.

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

  • В переменной [math]\mathtt{color}[/math] хранится цвет текущей компоненты.
  • [math]\mathtt{maxColor}[/math] изначально равен [math]0[/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 paint([math]v[/math]):
  maxColor++
  last = -1
  while last != [math]v[/math] and not stack.empty()
    colors[stack.top()] = maxColor
    last = stack.top()
    stack.pop()
function dfs([math] v [/math])
  time =  time + 1
  stack.push([math]v[/math])
  tin[[math]v[/math]] = time
  up[[math]v[/math]] = time
  for [math] (v, u) \in E[/math]:
    if [math](v, u)[/math] — обратное ребро
      up[[math]v[/math]] = min(up[[math]v[/math]], tin[[math]u[/math]])
    if not visited[[math]u[/math]]
      dfs([math]u[/math])
      up[[math]v[/math]] = min(up[[math]v[/math]], up[[math]u[/math]])
      if up[[math]u[/math]] > tin[[math]v[/math]] 
        paint([math]u[/math]) 

Так же после вызова dfs нужно не забыть в конце вызвать ещё раз paint.

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

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

См. также

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