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

Материал из Викиконспекты
Перейти к: навигация, поиск
(См. также)
м (rollbackEdits.php mass rollback)
 
(не показано 37 промежуточных версий 10 участников)
Строка 2: Строка 2:
 
Найти [[Отношение вершинной двусвязности|компоненты вершинной двусвязности]] неориентированного графа можно с помощью [[Обход_в_глубину,_цвета_вершин |обхода в глубину]].
 
Найти [[Отношение вершинной двусвязности|компоненты вершинной двусвязности]] неориентированного графа можно с помощью [[Обход_в_глубину,_цвета_вершин |обхода в глубину]].
  
'''Первый проход
+
'''Первый проход:
Используем первый проход, чтобы [[Использование обхода в глубину для поиска точек сочленения|найти точки сочленения.]] <br>
+
[[Использование обхода в глубину для поиска точек сочленения|ищем точки сочленения с помощью обхода в глубину]], заполняем массивы <tex>tin</tex> и <tex>up</tex>. <br>
Определим для каждой вершины две величины: <tex> enter [i] </tex> - время входа поиска в глубину в вершину <tex> i </tex>, <tex> return [i] </tex> – минимальное из времен входа вершин, достижимых из <tex> i </tex> по дереву <tex> dfs </tex> и не более, чем одному обратному ребру. Ребро к родителю не является обратным ребром. <br>
 
  
'''Псевдокод первого прохода:
+
'''Второй проход:
    dfs(<tex>v</tex>, <tex>parent</tex>)
+
[[Точка сочленения, эквивалентные определения|точка сочленения]] принадлежит как минимум двум компонентам вершинной двусвязности.
        <tex>enter[v] \leftarrow return[v] \leftarrow time</tex>++
+
Вершина <tex> v \ne root </tex> является точкой сочленения, если у нее есть сын <tex> u</tex>, такой что <tex> up[u] \geqslant tin[v] </tex>. <br> Это также значит, что ребро <tex> vu </tex> содержится в другой компоненте вершинной двусвязности, нежели ребро по которому мы пришли в вершину <tex> v </tex> , используя поиск в глубину. Получается, что перейдя по этому ребру, мы окажемся в другой компоненте вершинной двусвязности. <br>
        для всех вершин <tex>u</tex> смежных <tex>v</tex>:
+
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.<br>
            если (<tex>u</tex> родитель)
+
=== Псевдокод второго прохода ===
                переходим к следующей итерации
+
* Во время первого запуска <tex>dfs</tex> будут заполняться массивы <tex>tin</tex> и <tex>up</tex>, поэтому при запуске функции <tex>paint</tex> мы считаем, что они уже посчитаны.
            если (<tex>u</tex> посещена)
+
* <tex>\mathtt{maxColor}</tex> изначально равен <tex>0</tex>, что эквивалентно тому, что никакое ребро не окрашено.
                <tex>return[v] \leftarrow min(return[v], enter[u])</tex>
+
* <tex>\mathtt{color}</tex> хранит в себе цвет, компоненты, из которой вызвалась функция <tex>\mathrm{paint}</tex> для текущей вершины.
            иначе
+
* <tex>\mathtt{parent}</tex> {{---}} это вершина, из которой мы попали в текущую.
                dfs(<tex>u, v</tex>)
+
 
                <tex>return[v] \leftarrow min(return[v], return[u])</tex>
+
  '''function''' paint(<tex>v</tex>, color, parent):
   
+
  visited[<tex>v</tex>] = '''true'''
    start()
+
  '''for''' <tex> (v, u) \in E</tex>:
        для всех <tex>v</tex> вершин графа:
+
    '''if''' <tex>u</tex> == parent
            если (<tex>v</tex> не посещена)
+
      '''continue'''
                <tex>time \leftarrow 0</tex>
+
    '''if''' '''not''' visited[<tex>u</tex>]
                dfs(<tex>v, -1</tex>)
+
      '''if''' up[<tex>u</tex>] <tex>\geqslant</tex> tin[<tex>v</tex>]
 +
        newColor = ++maxColor
 +
        col[<tex>vu</tex>] = newColor
 +
        paint(<tex>u</tex>, newColor, <tex>v</tex>)
 +
      '''else'''
 +
        col[<tex>vu</tex>] = color
 +
        paint(<tex>u</tex>, color, <tex>v</tex>)
 +
    '''else''' '''if''' tin[<tex>u</tex>] <tex><</tex> tin[<tex>v</tex>]
 +
      col[<tex>vu</tex>] = color
 +
 
 +
  '''function''' solve():
 +
  '''for''' <tex> v \in V</tex>:
 +
    dfs(<tex>v</tex>)  
 +
  '''for''' <tex> v \in V</tex>:
 +
    '''if''' '''not''' visited[<tex>v</tex>]
 +
      maxColor++
 +
      paint(<tex>v</tex>, maxColor, -1)
  
'''Второй проход
 
[[Точка сочленения, эквивалентные определения|Точка сочленения]] принадлежит как минимум двум компонентам вершинной двусвязности.
 
Вершина <tex> v \ne root </tex> является точкой сочленения, если у нее <tex> \exists </tex> непосредственный сын <tex> u : return[u] \ge enter[v] </tex>. <br> Это так же значит, что ребро <tex> vu </tex> содержится в другой компоненте вершинной двусвязности, нежели ребро, по которому мы пришли в вершину <tex> v </tex> , используя поиск в глубину. <br>
 
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.<br>
 
'''Псевдокод второго прохода:
 
    dfs(<tex>v, c, parent</tex>)
 
        для всех  вершин u смежных v:
 
            если (<tex>u</tex> родитель)
 
                переходим к следующей итерации
 
            если (<tex>u</tex> не посещена)
 
                если (<tex>return[u] >= enter[v]</tex>)
 
                    <tex>c2 \leftarrow</tex> новый цвет
 
                    <tex>col[vu] \leftarrow c2</tex>
 
                    dfs(<tex>u, c2, v</tex>)
 
                иначе
 
                    <tex>col[vu] \leftarrow c</tex>
 
                    dfs(<tex>u, c, v</tex>)
 
            иначе:
 
                если (<tex>enter[u] <= enter[v]</tex>)
 
                    <tex>col[vu] \leftarrow c</tex>         
 
    start()
 
        для всех v вершин графа:
 
            если (<tex>v</tex> не посещена)
 
                dfs(<tex>v, -1, -1</tex>)
 
 
Ребра каждой из компонент вершинной двусвязности окажутся окрашенными в свой цвет.
 
Ребра каждой из компонент вершинной двусвязности окажутся окрашенными в свой цвет.
 +
<br>
 +
В алгоритме выполняется два прохода <tex>dfs</tex>, каждый из которых работает <tex>O(|V| + |E|)</tex>. Значит время работы алгоритма <tex>O(|V| + |E|)</tex>.
  
==Время работы двупроходного алгоритма==
+
== Однопроходный алгоритм ==
В алгоритме выполняется два прохода <tex>dfs</tex>, каждый из которых работает <tex>O(V + E)</tex>. Значит время работы алгоритма <tex>O(V + E)</tex>.
+
Заведем [[Стек|стек]], в который будем записывать все дуги в порядке их обработки. Если обнаружена точка сочленения, дуги очередного блока окажутся в этом стеке, начиная с дуги дерева обхода, которая привела в этот блок, до верхушки стека. <br>
 
 
==Однопроходный алгоритм==
 
Заведем стек, в который будем записывать все дуги в порядке их обработки. Если обнаружена точка сочленения, дуги очередного блока окажутся в этом стеке, начиная с дуги дерева обхода, которая привела в этот блок, до верхушки стека. <br>
 
 
Таким образом, каждый раз находя компоненту вершинной двусвязности мы сможем покрасить все ребра, содержащиеся в ней, в новый цвет.
 
Таким образом, каждый раз находя компоненту вершинной двусвязности мы сможем покрасить все ребра, содержащиеся в ней, в новый цвет.
===Доказательство корректности алгоритма===
+
=== Доказательство корректности алгоритма ===
 
Предположим, что граф содержит точку сочленения <tex> i' \in V </tex> , за которой следует один или несколько блоков. Вершины из этих блоков образуют подмножество <tex> V' \subset V </tex>. В таком случае: <br>
 
Предположим, что граф содержит точку сочленения <tex> i' \in V </tex> , за которой следует один или несколько блоков. Вершины из этих блоков образуют подмножество <tex> V' \subset V </tex>. В таком случае: <br>
 
# Все вершины <tex> V' </tex> являются потомками <tex> i' </tex> в дереве обхода;
 
# Все вершины <tex> V' </tex> являются потомками <tex> i' </tex> в дереве обхода;
 
# Все вершины <tex> V' </tex> будут пройдены в течение периода серого состояния <tex> i' </tex>;
 
# Все вершины <tex> V' </tex> будут пройдены в течение периода серого состояния <tex> i' </tex>;
 
# В <tex> G </tex> не может быть обратных дуг из <tex> V' </tex> в <tex> V \setminus V' </tex>.<br>
 
# В <tex> G </tex> не может быть обратных дуг из <tex> V' </tex> в <tex> V \setminus V' </tex>.<br>
Значит все дуги <tex> V' </tex> будут будут добавлены в стеке после дуги ведущей из точки сочленения в блок. В стеке в момент обнаружения точки сочленения будут находиться только дуги блока, связанного  с ней, т.к. блоки найденный до него (если таковые имеется) будет извлечен уже из стека и помечены в свой цвет.<br>
+
Значит все дуги <tex> V' </tex> будут будут добавлены в стек после дуги ведущей из точки сочленения в блок. В стеке в момент обнаружения точки сочленения будут находиться только дуги блока, связанного  с ней, т.к. блоки найденные до него (если таковые имеются) будет уже извлечены из стека и покрашены в свой цвет.<br>
'''Псевдокод:
+
=== Псевдокод ===
    void dfs(v, parent) {
+
'''function''' paint(<tex>v</tex>, parent):
        enter[v] = return[v] = time++;
+
  visited[<tex>v</tex>] = '''true'''
        used[v] = true;
+
  tin[<tex>v</tex>] = up[<tex>v</tex>] = time++
        для всех  вершин u смежных v:
+
  '''for''' <tex> (v, u) \in E</tex>:
            если (u == parent):
+
    '''if''' <tex>u</tex> == parent  
                переходим к следующей итерации
+
      '''continue'''
            если (!used[u]):
+
    '''if''' '''not''' visited[<tex>u</tex>]
                stack.push(vu);
+
      stack.push(<tex>vu</tex>)
                dfs(u, v);
+
      paint(<tex>u, v</tex>)
                если (return[u] >= enter[v]):
+
      '''if''' up[<tex>u</tex>] <tex>\geqslant</tex> tin[<tex>v</tex>]
                    c = newColor()
+
        color = maxColor++
                    пока (stack.top() <> (vu)):
+
        '''while''' stack.top() != (<tex>vu</tex>)
                        color[stack.top()] = c;
+
          colors[stack.top()] = color
                        stack.pop();
+
          stack.pop()
                    color[vu] = c;
+
        colors[<tex>vu</tex>] = color
                    stack.pop();
+
        stack.pop()
                если (return[u] < return[v]):
+
      '''if''' up[<tex>u</tex>] < up[<tex>v</tex>]
                    return[v] = return[u];
+
        up[<tex>v</tex>] = up[<tex>u</tex>]
            иначе:
+
    '''else''' '''if''' tin[<tex>u</tex>] < tin[<tex>v</tex>]  
                если (enter[u] < enter[v]):
+
      stack.push(<tex>vu</tex>)
                    stack.push(vu);
+
      '''if''' tin[<tex>u</tex>] < up[<tex>v</tex>]
                если (return[v] > enter[u]):
+
        up[<tex>v</tex>] = tin[<tex>u</tex>]
                    return[v] = return[u];
+
    '''else''' '''if''' up[<tex>v</tex>] > tin[<tex>u</tex>]
    }
+
      up[<tex>v</tex>] = up[<tex>u</tex>]
    void start() {
 
        used для всех вершин заполняем false
 
        для всех v вершин графа:
 
            если (!used[v]):
 
                time = 0;
 
                dfs(v, -1);
 
    }
 
  
==Литература==
+
'''function''' solve():
 +
  '''for''' <tex> v \in V</tex>:
 +
    dfs(<tex>v</tex>)
 +
  '''for''' <tex> v \in V</tex>:
 +
    '''if''' '''not''' visited[<tex>v</tex>]:
 +
      time = 0
 +
      maxColor++
 +
      paint(<tex>v</tex>, -1)
 +
 
 +
Во время алгоритма совершается один проход <tex>dfs</tex>, который работает за <tex>O(|V| + |E|)</tex>. Внутри него совершается еще цикл, который суммарно выполняет <tex>O(|E|)</tex> операций, т.к. каждое ребро может быть добавлено в стек только один раз. Следовательно, общее время работы алгоритма <tex>O(|V| + |E|) + O(|E|) = O(|V| + |E|)</tex>
 +
 
 +
== См. также ==
 +
* [[Использование обхода в глубину для поиска точек сочленения]]
 +
* [[Построение компонент реберной двусвязности]]
 +
 
 +
== Источники информации ==
 
* В.А.Кузнецов, А.М.Караваев. "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007
 
* В.А.Кузнецов, А.М.Караваев. "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007
 +
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/biconnected-components-2005 Дискретная математика: Алгоритмы {{---}} Компоненты двусвязности, мосты и точки сочленения]
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Обход в глубину]]

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

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

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

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

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

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

  • Во время первого запуска [math]dfs[/math] будут заполняться массивы [math]tin[/math] и [math]up[/math], поэтому при запуске функции [math]paint[/math] мы считаем, что они уже посчитаны.
  • [math]\mathtt{maxColor}[/math] изначально равен [math]0[/math], что эквивалентно тому, что никакое ребро не окрашено.
  • [math]\mathtt{color}[/math] хранит в себе цвет, компоненты, из которой вызвалась функция [math]\mathrm{paint}[/math] для текущей вершины.
  • [math]\mathtt{parent}[/math] — это вершина, из которой мы попали в текущую.
function paint([math]v[/math], color, parent):
  visited[[math]v[/math]] = true
  for [math] (v, u) \in E[/math]:
    if [math]u[/math] == parent
      continue
    if not visited[[math]u[/math]]
      if up[[math]u[/math]] [math]\geqslant[/math] tin[[math]v[/math]]
        newColor = ++maxColor
        col[[math]vu[/math]] = newColor
        paint([math]u[/math], newColor, [math]v[/math])
      else
        col[[math]vu[/math]] = color
        paint([math]u[/math], color, [math]v[/math])
    else if tin[[math]u[/math]] [math]\lt [/math] tin[[math]v[/math]]
      col[[math]vu[/math]] = color
function solve():
  for [math] v \in V[/math]:
    dfs([math]v[/math])    
  for [math] v \in V[/math]:
    if not visited[[math]v[/math]]
      maxColor++
      paint([math]v[/math], maxColor, -1)

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

Псевдокод

function paint([math]v[/math], parent):
  visited[[math]v[/math]] = true
  tin[[math]v[/math]] = up[[math]v[/math]] = time++
  for [math] (v, u) \in E[/math]:
    if [math]u[/math] == parent 
      continue
    if not visited[[math]u[/math]]
      stack.push([math]vu[/math])
      paint([math]u, v[/math])
      if up[[math]u[/math]] [math]\geqslant[/math] tin[[math]v[/math]]
        color = maxColor++
        while stack.top() != ([math]vu[/math])
          colors[stack.top()] = color
          stack.pop()
        colors[[math]vu[/math]] = color
        stack.pop()
      if up[[math]u[/math]] < up[[math]v[/math]]
        up[[math]v[/math]] = up[[math]u[/math]]
    else if tin[[math]u[/math]] < tin[[math]v[/math]] 
      stack.push([math]vu[/math])
      if tin[[math]u[/math]] < up[[math]v[/math]]
        up[[math]v[/math]] = tin[[math]u[/math]]
    else if up[[math]v[/math]] > tin[[math]u[/math]]
      up[[math]v[/math]] = up[[math]u[/math]]
function solve():
  for [math] v \in V[/math]:
    dfs([math]v[/math])
  for [math] v \in V[/math]:
    if not visited[[math]v[/math]]:
      time = 0
      maxColor++
      paint([math]v[/math], -1)

Во время алгоритма совершается один проход [math]dfs[/math], который работает за [math]O(|V| + |E|)[/math]. Внутри него совершается еще цикл, который суммарно выполняет [math]O(|E|)[/math] операций, т.к. каждое ребро может быть добавлено в стек только один раз. Следовательно, общее время работы алгоритма [math]O(|V| + |E|) + O(|E|) = O(|V| + |E|)[/math]

См. также

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