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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Двупроходный алгоритм)
(Однопроходный алгоритм)
Строка 44: Строка 44:
  
 
== Однопроходный алгоритм ==
 
== Однопроходный алгоритм ==
Заведем стек, в который будем записывать все дуги в порядке их обработки. Если обнаружена точка сочленения, дуги очередного блока окажутся в этом стеке, начиная с дуги дерева обхода, которая привела в этот блок, до верхушки стека. <br>
+
Заведем [[Стек|стек]], в который будем записывать все дуги в порядке их обработки. Если обнаружена точка сочленения, дуги очередного блока окажутся в этом стеке, начиная с дуги дерева обхода, которая привела в этот блок, до верхушки стека. <br>
 
Таким образом, каждый раз находя компоненту вершинной двусвязности мы сможем покрасить все ребра, содержащиеся в ней, в новый цвет.
 
Таким образом, каждый раз находя компоненту вершинной двусвязности мы сможем покрасить все ребра, содержащиеся в ней, в новый цвет.
 
=== Доказательство корректности алгоритма ===
 
=== Доказательство корректности алгоритма ===
Строка 53: Строка 53:
 
Значит все дуги <tex> V' </tex> будут будут добавлены в стек после дуги ведущей из точки сочленения в блок. В стеке в момент обнаружения точки сочленения будут находиться только дуги блока, связанного  с ней, т.к. блоки найденные до него (если таковые имеются) будет уже извлечены из стека и покрашены в свой цвет.<br>
 
Значит все дуги <tex> V' </tex> будут будут добавлены в стек после дуги ведущей из точки сочленения в блок. В стеке в момент обнаружения точки сочленения будут находиться только дуги блока, связанного  с ней, т.к. блоки найденные до него (если таковые имеются) будет уже извлечены из стека и покрашены в свой цвет.<br>
 
=== Псевдокод ===
 
=== Псевдокод ===
  '''function''' <tex>dfs</tex>(<tex>v</tex>, parent):
+
  '''function''' paint(<tex>v</tex>, parent):
 
   tin[<tex>v</tex>] = up[<tex>v</tex>] = time++
 
   tin[<tex>v</tex>] = up[<tex>v</tex>] = time++
   '''for''' <tex> u : (v, u) \in E</tex>:
+
   '''for''' <tex> (v, u) \in E</tex>:
 
     '''if''' <tex>u</tex> == parent  
 
     '''if''' <tex>u</tex> == parent  
 
       '''continue'''
 
       '''continue'''
 
     '''if''' '''not''' visited[<tex>u</tex>]
 
     '''if''' '''not''' visited[<tex>u</tex>]
 
       stack.push(<tex>vu</tex>)
 
       stack.push(<tex>vu</tex>)
       dfs(<tex>u, v</tex>)
+
       paint(<tex>u, v</tex>)
 
       '''if''' up[<tex>u</tex>] <tex>\geqslant</tex> tin[<tex>v</tex>]
 
       '''if''' up[<tex>u</tex>] <tex>\geqslant</tex> tin[<tex>v</tex>]
 
         color = maxColor++
 
         color = maxColor++
Строка 66: Строка 66:
 
           colors[stack.top()] = color
 
           colors[stack.top()] = color
 
           stack.pop()
 
           stack.pop()
         colors[<tex>vu</tex>] = color
+
         colors[<tex>vu</tex>] = color
 
         stack.pop()
 
         stack.pop()
 
       '''if''' up[<tex>u</tex>] < up[<tex>v</tex>]
 
       '''if''' up[<tex>u</tex>] < up[<tex>v</tex>]
Строка 75: Строка 75:
 
       up[<tex>v</tex>] = up[<tex>u</tex>]
 
       up[<tex>v</tex>] = up[<tex>u</tex>]
  
  '''for''' <tex> v \in V</tex>:
+
  '''function''' solve():
  '''if''' '''not''' visited[<tex>v</tex>]
+
  '''for''' <tex> v \in V</tex>:
 +
    '''if''' '''not''' visited[<tex>v</tex>]
 +
      dfs(<tex>v</tex>)
 +
  '''for''' <tex> v \in V</tex>:
 +
    visited[<tex>v</tex>] = '''false'''
 +
  '''for''' <tex> v \in V</tex>:
 
     time = 0
 
     time = 0
     dfs(<tex>v</tex>, -1)
+
     paint(<tex>v</tex>, -1)
 
<br>
 
<br>
 
Во время алгоритма совершается один проход <tex>dfs</tex>, который работает за <tex>O(|V| + |E|)</tex>. Внутри него совершается еще цикл, который суммарно выполняет <tex>O(|E|)</tex> операций, т.к. каждое ребро может быть добавлено в стек только один раз. Следовательно, общее время работы алгоритма <tex>O(|V| + |E|) + O(|E|) = O(|V| + |E|)</tex>
 
Во время алгоритма совершается один проход <tex>dfs</tex>, который работает за <tex>O(|V| + |E|)</tex>. Внутри него совершается еще цикл, который суммарно выполняет <tex>O(|E|)</tex> операций, т.к. каждое ребро может быть добавлено в стек только один раз. Следовательно, общее время работы алгоритма <tex>O(|V| + |E|) + O(|E|) = O(|V| + |E|)</tex>

Версия 23:11, 10 ноября 2015

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

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

Первый проход: Ищем точки сочленения.

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

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

  • [math]maxColor[/math] изначально равен 0, что эквивалентно тому, что ребро не окрашено.
  • [math]color[/math] хранит в себе цвет, компоненты, из которой вызвалась функция [math]paint[/math] для текущей вершины.
  • [math]parent[/math] — это вершина, из которой мы попали в текущую.
function paint([math]v[/math], color, parent):
  for [math] u : (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 up[[math]u[/math]] [math]\leqslant[/math] tin[[math]v[/math]]
      col[[math]vu[/math]] = color
function solve():
  for [math] v \in V[/math]:
    if not visited[[math]v[/math]]
      dfs([math]v,[/math])    
  for [math]v \in V[/math]:
    visited[[math]v[/math]] = false
  for [math] v \in V[/math]:
    if not visited[[math]v[/math]]
      paint([math]v[/math], -1, -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):
  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])
    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]:
    if not visited[[math]v[/math]]
      dfs([math]v[/math])
  for [math] v \in V[/math]:
    visited[[math]v[/math]] = false
  for [math] v \in V[/math]:
    time = 0
    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]

См. также

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

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