Построение компонент вершинной двусвязности — различия между версиями
Novik (обсуждение | вклад) м |
Novik (обсуждение | вклад) (→Двупроходный алгоритм) |
||
Строка 2: | Строка 2: | ||
Найти [[Отношение вершинной двусвязности|компоненты вершинной двусвязности]] неориентированного графа можно с помощью [[Обход_в_глубину,_цвета_вершин |обхода в глубину]]. | Найти [[Отношение вершинной двусвязности|компоненты вершинной двусвязности]] неориентированного графа можно с помощью [[Обход_в_глубину,_цвета_вершин |обхода в глубину]]. | ||
− | '''Первый проход | + | '''Первый проход: |
Используем первый проход, чтобы [[Использование обхода в глубину для поиска точек сочленения|найти точки сочленения.]] <br> | Используем первый проход, чтобы [[Использование обхода в глубину для поиска точек сочленения|найти точки сочленения.]] <br> | ||
− | '''Второй проход | + | '''Второй проход: |
[[Точка сочленения, эквивалентные определения|Точка сочленения]] принадлежит как минимум двум компонентам вершинной двусвязности. | [[Точка сочленения, эквивалентные определения|Точка сочленения]] принадлежит как минимум двум компонентам вершинной двусвязности. | ||
− | Вершина <tex> v \ne root </tex> является точкой сочленения, если у нее есть сын <tex> u : | + | Вершина <tex> v \ne root </tex> является точкой сочленения, если у нее есть сын <tex> u : up[u] \geqslant tin[v] </tex>. <br> Это также значит, что ребро <tex> vu </tex> содержится в другой компоненте вершинной двусвязности, нежели ребро по которому мы пришли в вершину <tex> v </tex> , используя поиск в глубину. Получается, что перейдя по этому ребру, мы окажемся в другой компоненте вершинной двусвязности. <br> |
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.<br> | Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.<br> | ||
=== Псевдокод второго прохода === | === Псевдокод второго прохода === | ||
Строка 13: | Строка 13: | ||
|- | |- | ||
| | | | ||
− | + | '''function''' <tex>dfs</tex>(<tex>v</tex>, color, parent): | |
− | + | '''for''' <tex> u : (v, u) \in E</tex>: | |
− | + | '''if''' <tex>u</tex> == parent | |
− | + | '''continue''' | |
− | + | '''if''' '''not''' visited[<tex>u</tex>] | |
− | + | '''if''' up[<tex>u</tex>] <tex>\geqslant</tex> tin[<tex>v</tex>] | |
− | + | newColor = maxColor++ | |
− | + | col[<tex>vu</tex>] = newColor | |
− | + | dfs(<tex>u</tex>, newColor, <tex>v</tex>) | |
− | + | '''else''' | |
− | + | col[<tex>vu</tex>] = color | |
− | + | dfs(<tex>u</tex>, color, <tex>v</tex>) | |
− | + | '''else''' '''if''' up[<tex>u</tex>] <tex>\leqslant</tex> tin[<tex>v</tex>] | |
− | + | col[<tex>vu</tex>] = color | |
− | + | ||
− | + | '''for''' <tex> v \in V</tex>: | |
− | + | '''if''' '''not''' visited[<tex>v</tex>] | |
− | + | dfs(<tex>v</tex>, -1, -1) | |
− | |||
|width = "310px" |[[Файл:Vertex_doubleconnection_1.png|thumb|center|400px|Компоненты обозначены разным цветом]] | |width = "310px" |[[Файл:Vertex_doubleconnection_1.png|thumb|center|400px|Компоненты обозначены разным цветом]] | ||
|} | |} | ||
Строка 37: | Строка 36: | ||
Ребра каждой из компонент вершинной двусвязности окажутся окрашенными в свой цвет. | Ребра каждой из компонент вершинной двусвязности окажутся окрашенными в свой цвет. | ||
<br> | <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>. |
== Однопроходный алгоритм == | == Однопроходный алгоритм == |
Версия 22:15, 10 ноября 2015
Содержание
Двупроходный алгоритм
Найти компоненты вершинной двусвязности неориентированного графа можно с помощью обхода в глубину.
Первый проход:
Используем первый проход, чтобы найти точки сочленения.
Второй проход:
Точка сочленения принадлежит как минимум двум компонентам вершинной двусвязности.
Вершина является точкой сочленения, если у нее есть сын .
Это также значит, что ребро содержится в другой компоненте вершинной двусвязности, нежели ребро по которому мы пришли в вершину , используя поиск в глубину. Получается, что перейдя по этому ребру, мы окажемся в другой компоненте вершинной двусвязности.
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.
Псевдокод второго прохода
function( , color, parent): for : if == parent continue if not visited[ ] if up[ ] tin[ ] newColor = maxColor++ col[ ] = newColor dfs( , newColor, ) else col[ ] = color dfs( , color, ) else if up[ ] tin[ ] col[ ] = color for : if not visited[ ] dfs( , -1, -1) |
Ребра каждой из компонент вершинной двусвязности окажутся окрашенными в свой цвет.
В алгоритме выполняется два прохода , каждый из которых работает . Значит время работы алгоритма .
Однопроходный алгоритм
Заведем стек, в который будем записывать все дуги в порядке их обработки. Если обнаружена точка сочленения, дуги очередного блока окажутся в этом стеке, начиная с дуги дерева обхода, которая привела в этот блок, до верхушки стека.
Таким образом, каждый раз находя компоненту вершинной двусвязности мы сможем покрасить все ребра, содержащиеся в ней, в новый цвет.
Доказательство корректности алгоритма
Предположим, что граф содержит точку сочленения
- Все вершины являются потомками в дереве обхода;
- Все вершины будут пройдены в течение периода серого состояния ;
- В
Значит все дуги
Псевдокод
function( , parent): enter[ ] return[ ] time++ for : if == parent continue if not visited[ ] stack.push( ) ( ) if return[ ] enter[ ] color maxColor++ while stack.top() != colors[stack.top()] color stack.pop() colors[ ] color stack.pop() if return[ ] < return[ ] return[ ] return[ ] else if enter[ ] < enter[ ] stack.push( ) else return[ ] > enter[ ] return[ ] return[ ] ... for : if not visited[ ] time 0 ( , -1)
Во время алгоритма совершается один проход , который работает за . Внутри него совершается еще цикл, который суммарно выполняет операций, т.к. каждое ребро может быть добавлено в стек только один раз. Следовательно, общее время работы алгоритма
Источники информации
- В.А.Кузнецов, А.М.Караваев. "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007