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

Материал из Викиконспекты
Перейти к: навигация, поиск
(не показано 36 промежуточных версий 6 участников)
Строка 1: Строка 1:
== Основные понятия ==
 
 
[[Отношение реберной двусвязности#Реберная двусвязность|Реберная двусвязность]]
 
 
[[Отношение реберной двусвязности#Компоненты реберной двусвязности|Компонент реберной двусвязности]]
 
 
 
Построение компонент реберной двусвязности будет осуществляться с помощью [[Обход в глубину, цвета вершин|обхода в глубину]].
 
Построение компонент реберной двусвязности будет осуществляться с помощью [[Обход в глубину, цвета вершин|обхода в глубину]].
  
 
== Двупроходный алгоритм ==
 
== Двупроходный алгоритм ==
  
Первый способ найти искомые компоненты - сначала определить критерий перехода в новую компоненту реберной двусвязности, а затем покрасить вершины графа в нужные цвета.
+
Первый способ найти искомые компоненты {{---}} сначала определить критерий перехода в новую [[Отношение реберной двусвязности#Компоненты реберной двусвязности|компоненту реберной двусвязности]], а затем покрасить вершины графа в нужные цвета.
  
Первый проход определяет для каждой вершины <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>tin(v)</tex> и <tex>up(v)</tex>.
  
  '''void dfs(v, родитель):
+
'''Второй проход:''' окрашиваем вершины, т.е. если перешли по мосту, то оказались в новой компоненте реберной двусвязности.
    увеличиваем текущее время
 
    enter(v) := текущее время   
 
    return(v) := enter(v)
 
    для всех вершин u, смежных v:
 
      если enter(u) равен нулю (вершина не посещена):
 
        dfs(u, v)
 
        return(v) := min(return(v), return(u))
 
      иначе если u не родитель:
 
        return(v) := min(return(v), enter(u))
 
  ...
 
  обнуляем массив enter
 
  текущее время := 0
 
  для всех вершин v графа:
 
    если enter(v) = 0:
 
      dfs(v, null)'''
 
  
Определим критерий перехода к новой компоненте.
+
=== Псевдокод второго прохода ===
{{Теорема
+
* В переменной <tex>\mathtt{color}</tex> хранится цвет текущей компоненты.
|statement=
+
* <tex>\mathtt{maxColor}</tex> изначально равен <tex>0</tex>, что эквивалентно тому, что никакая компонента не окрашена.
Ребро <tex>uv</tex> ведет из одной компоненты реберной двусвязности в другую, если оно является частью дерева <tex>dfs</tex>, и либо <tex>u</tex> - предок <tex>v</tex> и <tex>return(v) = enter(v)</tex>, либо <tex>v</tex> - предок <tex>u</tex> и <tex>return(u) = enter(u)</tex>.
 
|proof=
 
Если ребро <tex>uv</tex> - обратное, образуется цикл, содержащий <tex>uv</tex>, поэтому <tex>uv</tex> не может являться мостом.
 
Последнее равенство означает, что из <tex>v</tex> и ее потомков нельзя подняться выше <tex>v</tex> по дереву обхода, в том числе, и в <tex>u</tex>. Таким образом, между <tex>u</tex> и <tex>v</tex> существует лишь один путь - ребро <tex>uv</tex>, - и они принадлежат разным компонентам реберной двусвязности.
 
}}
 
  
Основываясь на этом, определим алгоритм окраски вершин графа. Путь по графу будет точно таким же, как и в первом проходе, что гарантирует постоянность дерева <tex>dfs</tex> и определенных параметров вершин: <tex>enter</tex> и <tex>return</tex>.
+
'''function''' paint(<tex>v</tex>, color):
 +
  colors[<tex>v</tex>] = color
 +
  '''for''' <tex>(u, v) \in E</tex>:
 +
    '''if''' colors[<tex>u</tex>] == 0:
 +
      '''if''' up[<tex>u</tex>] > tin[<tex>v</tex>]:
 +
        maxColor++
 +
        paint(<tex>u</tex>, maxColor)
 +
      '''else''':
 +
        paint(<tex>u</tex>, color)
  
Псевдокод второго прохода:
+
'''function''' solve():
 +
  '''for''' <tex>v \in V</tex> :
 +
    colors[<tex>v</tex>] = 0
 +
    '''if''' '''not''' visited[<tex>v</tex>]
 +
      dfs(<tex>v</tex>)
 +
  maxColor = 0
 +
  '''for''' <tex>v \in V</tex> :
 +
    '''if''' colors[<tex>v</tex>] == 0:
 +
      maxColor++
 +
      paint(<tex>v</tex>, maxColor)
  
  '''void paint(v, цвет):
+
Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цвет.
    colors(v) := цвет
 
    для всех вершин u, смежных v:
 
      если colors(u) равен нулю (вершина не покрашена):
 
        если return(u) = enter(u):
 
          увеличиваем максимальный цвет
 
          paint(u, максимальный цвет)
 
        иначе:
 
          paint(u, цвет)
 
  ...
 
  обнуляем массив colors
 
  максимальный цвет := 0
 
  для всех вершин v графа:
 
    если colors(v) = 0:
 
      увеличиваем максимальный цвет
 
      paint(v, максимальный цвет)'''
 
  
Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цвет.
+
Время работы алгоритма будет время работы двух запусков dfs, то есть  <tex>2 \cdot O(|V| + |E|)</tex>, что есть  <tex> O(|V| + |E|)</tex>.
  
 
== Однопроходный алгоритм ==
 
== Однопроходный алгоритм ==
  
Можно также искать компоненты реберной двусвязности путем конкатенации циклов. Воспользуемся тем, что реберная двусвязность является отношением эквивалентности на вершинах графа; тогда, если у двух циклов существует хоть одна общая вершина, все вершины, располагающиеся на этих циклах, принадлежат одной компоненте. Более того, две вершины <tex>u</tex> и <tex>v</tex> лежат в одной компоненте реберной двусвязности тогда и только тогда, когда существует последовательность простых циклов <tex>c_1 c_2 ... c_n</tex>, причем <tex>u \in c_1</tex>, <tex>v \in c_n</tex>, и <tex>c_i</tex> имеет с <tex>c_{i + 1}</tex> хотя бы одну общую вершину для всех <tex>i \in {1 ... n - 1}</tex>. Действительно, если зафиксировать один путь от <tex>u</tex> до <tex>v</tex>, а затем искать точки пересечения второго, не имеющего одинаковых ребер с первым, пути с ним, то получится последовательность циклов, точками сочленения между которыми будут как раз точки пересечения путей. И наоборот, последовательность простых циклов легко превратить в два реберно непересекающихся пути.
 
  
Совокупность компонент реберной двусвязности будем хранить как систему непересекающихся множеств вершин.
+
Однопроходный алгоритм строится на базе алгоритма поиска мостов. Во-первых, создадим глобальный [[Стек|стек]], и при спуске по дереву <tex> dfs </tex> добавляем в него вершины. Во-вторых, когда возвращаемся назад, проверяем не является ли ребро мостом (при помощи [[Использование обхода в глубину для поиска мостов#Лемма | леммы]]). Если это так, то то все вершины, находящиеся до текущего потомка в стеке, принадлежат одной компоненте.Заметим, что эта компонента будет висячей вершиной в дереве блоков и мостов, так как обходили граф поиском в глубину. Значит, ее можно выкинуть и продолжить поиск в оставшемся графе. Действуя по аналогии в получившемся графе, найдем оставшиеся компоненты реберной двусвязности.
  
Псевдокод:
+
=== Псевдокод ===
  
  '''int dfs(v, родитель): (возвращает 0, если у v и ее потомков нет обратных ребер, и представителя множества, содержащего цикл с v, в обратном случае)
+
'''function''' paint(<tex>v</tex>):
    seen(v) = true
+
  maxColor++
    value = 0, result = 0
+
  last = -1
    для всех вершин u, смежных v:
+
  '''while''' last != <tex>v</tex> '''and''' '''not''' stack.empty()
      если не seen(u):
+
    colors[stack.top()] = maxColor
        value = dfs(u, v)
+
    last = stack.top()
        если value > 0:
+
    stack.pop()
          color(v) = value
 
          result = value
 
        иначе если u не родитель:
 
          color(v) = color(u)
 
          result = color(v)
 
    return result
 
  ...
 
  обнуляем массив seen
 
  нумеруем вершины графа натуральными числами от 1 до мощности множества вершин графа
 
  для всех вершин v графа:
 
    color(v) = номер вершины (номер цвета соответствует номеру вершины-представителя в множестве)
 
  для всех вершин v графа:
 
    если не seen(v):
 
      dfs(v, null)'''
 
 
 
Осталось лишь сопоставить всем вершинам отдельно взятой компоненты единственного представителя.
 
  
Псевдокод:
+
'''function''' dfs(<tex> v </tex>)
 +
  time =  time + 1
 +
  stack.push(<tex>v</tex>)
 +
  tin[<tex>v</tex>] = time
 +
  up[<tex>v</tex>] = time
 +
  '''for''' <tex> (v, u) \in E</tex>:
 +
    '''if''' <tex>(v, u)</tex> — обратное ребро
 +
      up[<tex>v</tex>] = min(up[<tex>v</tex>], tin[<tex>u</tex>])
 +
    '''if''' '''not''' visited[<tex>u</tex>]
 +
      dfs(<tex>u</tex>)
 +
      up[<tex>v</tex>] = min(up[<tex>v</tex>], up[<tex>u</tex>])
 +
      '''if''' up[<tex>u</tex>] > tin[<tex>v</tex>]
 +
        paint(<tex>u</tex>)
  
  '''int relax(v): (возвращает нового представителя)
+
Так же после вызова dfs нужно не забыть в конце вызвать ещё раз paint.
    если color(v) не равен номеру v:
 
      color(v) = relax(color(v))
 
    return color(v)
 
  ...
 
  для всех вершин v графа:
 
    relax(v)
 
  
 
Теперь две вершины имеют одинаковый цвет тогда и только тогда, когда они принадлежат одной компоненте реберной двусвязности.
 
Теперь две вершины имеют одинаковый цвет тогда и только тогда, когда они принадлежат одной компоненте реберной двусвязности.
 +
 +
Время работы dfs <tex> O(|V| + |E|)</tex>. Покраска за <tex> O(|V|) </tex>.
 +
Итоговое время работы алгоритма <tex> O(|V| + |E|)</tex>.
  
 
== См. также ==
 
== См. также ==
* [[Обход в глубину, цвета вершин|Oбхода в глубину]]
 
* [[Использование обхода в глубину для поиска точек сочленения]]
 
 
* [[Построение компонент вершинной двусвязности]]
 
* [[Построение компонент вершинной двусвязности]]
 
* [[Использование обхода в глубину для поиска мостов]]
 
* [[Использование обхода в глубину для поиска мостов]]
  
==Литература==
+
== Источники информации ==
Седжвик Роберт. Фундаментальные алгоритмы на C++. Часть 5: Алгоритмы на графах: Пер. с англ./Роберт Седжвик. — СПб.: ООО «ДиаСофтЮП», 2002. —
+
* ''Седжвик Р.'' Фундаментальные алгоритмы на C++. Часть 5: Алгоритмы на графах. Пер. с англ. — СПб.: ООО «ДиаСофтЮП», 2002. — С. 123-128
 +
* ''Кузнецов В.А., Караваев. А.М.'' "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007
 +
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bridges-2001| Визуализация {{---}} Построение компонент реберной двусзяности]
 +
 
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Обход в глубину]]

Версия 23:48, 31 января 2019

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

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

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

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

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

См. также

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