Изменения

==Постановка задачиДвупроходный алгоритм==Дан неориентированный граф. Требуется определить его Найти [[Отношение вершинной двусвязности|компоненты вершинной двусвязности]] неориентированного графа можно с помощью [[Обход_в_глубину,_цвета_вершин |обхода в глубину]].

Задачу будем решать '''Первый проход:[[Использование обхода в глубину для поиска точек сочленения|ищем точки сочленения с помощью обхода в глубину]], заполняем массивы <tex>tin</tex> и <tex>up</tex>.<br>

==Двупроходный алгоритм=='''Первый Второй проход:Используем первый проход, чтобы [[Использование обхода в глубину для поиска точек Точка сочленения, эквивалентные определения|найти точки точка сочленения]] принадлежит как минимум двум компонентам вершинной двусвязности.Вершина <tex> v \ne root </tex> является точкой сочленения, если у нее есть сын <tex> u</tex>, такой что <tex> up[u]\geqslant tin[v] </tex>. <br>Определим для каждой вершины две величины: Это также значит, что ребро <tex> vu </tex> содержится в другой компоненте вершинной двусвязности, нежели ребро по которому мы пришли в вершину <tex> enter [i] v </tex> - время входа поиска , используя поиск в глубину . Получается, что перейдя по этому ребру, мы окажемся в другой компоненте вершинной двусвязности. <br>Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в вершину различные цвета.<br>=== Псевдокод второго прохода ===* Во время первого запуска <tex>dfs</tex> будут заполняться массивы <tex>tin</tex> и <tex> i up</tex>, поэтому при запуске функции <tex> return [i] paint</tex> – минимальное из времен входа вершинмы считаем, достижимых из что они уже посчитаны.* <tex> i \mathtt{maxColor}</tex> по дереву изначально равен <tex> dfs 0</tex> и , что эквивалентно тому, что никакое ребро не болееокрашено.* <tex>\mathtt{color}</tex> хранит в себе цвет, компоненты, чем одному обратному ребру. Ребро к родителю не является обратным ребромиз которой вызвалась функция <tex>\mathrm{paint}</tex> для текущей вершины. * <tex>\mathtt{parent}<br/tex>{{---}} это вершина, из которой мы попали в текущую.  '''Псевдокод первого прохода: void dfsfunction''' paint(<tex>v</tex>, color, parent) {: enter visited[<tex>v</tex>] = return[v] = time++;'''true''' used[ '''for''' <tex> (v] = true; для всех вершин , u смежных v) \in E</tex>: если ( '''if''' <tex>u </tex> == parent): переходим к следующей итерации '''continue''' если (used '''if''' '''not''' visited[<tex>u</tex>]): return '''if''' up[<tex>u</tex>] <tex>\geqslant</tex> tin[<tex>v</tex>] : newColor = min(return++maxColor col[v<tex>vu</tex>]= newColor paint(<tex>u</tex>, newColor, enter<tex>v</tex>) '''else''' col[u<tex>vu</tex>]);= color иначе: dfs paint(<tex>u</tex>, color, <tex>v</tex>); return '''else''' '''if''' tin[v<tex>u</tex>] := min(return<tex><</tex> tin[<tex>v</tex>], return col[u<tex>vu</tex>]= color  '''function''' solve();: } '''for''' <tex> v \in V</tex>: void start dfs(<tex>v</tex>) { used для всех вершин заполняем false для всех '''for''' <tex> v вершин графа\in V</tex>: если (!used '''if''' '''not''' visited[<tex>v</tex>]): time = 0; maxColor++ dfs paint(<tex>v</tex>, maxColor, -1); }

==Однопроходный алгоритм==Заведем [[Стек|стек]], в который будем записывать все дуги в порядке их обработки. Если обнаружена точка сочленения, дуги очередного блока окажутся в этом стеке, начиная с дуги дерева обхода, которая привела в этот блок, до верхушки стека. <br>

===Доказательство корректности алгоритма===

Значит все дуги <tex> V' </tex> будут будут добавлены в стеке стек после дуги ведущей из точки сочленения в блок. В стеке в момент обнаружения точки сочленения будут находиться только дуги блока, связанного с ней, т.к. блоки найденный найденные до него (если таковые имеетсяимеются) будет извлечен уже извлечены из стека и помечены покрашены в свой цвет.<br>=== Псевдокод === '''function'''Псевдокод: void dfspaint(<tex>v</tex>, parent) {: enter visited[<tex>v</tex>] = return'''true''' tin[<tex>v</tex>] = up[<tex>v</tex>] = time++; used[ '''for''' <tex> (v] = true; для всех вершин , u смежных v) \in E</tex>: если ( '''if''' <tex>u </tex> == parent): переходим к следующей итерации '''continue''' если (!used '''if''' '''not''' visited[<tex>u</tex>]): stack.push(<tex>vu</tex>); dfs paint(<tex>u, v</tex>); если (return '''if''' up[<tex>u</tex>] <tex>\geqslant</tex>= entertin[<tex>v</tex>]): c color = newColor()maxColor++ пока ( '''while''' stack.top() != (<tex> (vu</tex>)): color colors[stack.top()] = c;color stack.pop(); color colors[<tex>vu</tex>] = c;color stack.pop(); если (return '''if''' up[<tex>u</tex>] < returnup[<tex>v</tex>]): return up[<tex>v</tex>] = returnup[<tex>u</tex>]; иначе: если (enter '''else''' '''if''' tin[<tex>u</tex>] < entertin[<tex>v</tex>]): stack.push(<tex>vu</tex>); если (return '''if''' tin[<tex>u</tex>] < up[<tex>v</tex>] up[<tex>v</tex>] = tin[<tex>u</tex>] '''else''' '''if''' up[<tex>v</tex>] > entertin[<tex>u</tex>]): return up[<tex>v</tex>] = returnup[<tex>u</tex>]; } void start '''function''' solve() {: used для всех вершин заполняем false '''for''' <tex> v \in V</tex>: dfs(<tex>v</tex>) для всех '''for''' <tex> v вершин графа\in V</tex>: если (!used '''if''' '''not''' visited[<tex>v</tex>]): time = 0; dfs 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>

*[[Использование обхода в глубину для поиска точек сочленения]]*[[Построение компонент реберной двусвязности]]*[[Отношение вершинной двусвязности]]==ЛитератураИсточники информации ==