Изменения
Нет описания правки
Построение компонент реберной двусвязности будет осуществляться с помощью [[Обход в глубину, цвета вершин|обхода в глубину]].
== Двупроходный алгоритм ==
Первый способ найти искомые компоненты {{- --}} сначала определить критерий перехода в новую [[Отношение реберной двусвязности#Компоненты реберной двусвязности|компоненту реберной двусвязности]], а затем покрасить вершины графа в нужные цвета. Определим критерий перехода к новой компоненте.Воспользуемся ранее доказанной [[Использование обхода в глубину для поиска мостов#Лемма | леммой]]. Получается {{---}} перешли по мосту, следовательно началась новая компонента.
'''Первый проход определяет :''' запустим [[Использование обхода в глубину для поиска мостов|алгоритм для каждой вершины поиска мостов]], чтобы посчитать две величины: <tex>tin(v)</tex> две величины: и <tex>enterup(v)</tex> - время входа поиска в глубину в вершину и [[Использование обхода в глубину для поиска мостов#Функция | ret(v)]].
Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цвет.
Время работы алгоритма будет время работы двух запусков dfs, то есть 2 * <tex> 2 \cdot O(|V| + |E|)</tex>, что есть <tex> O(|V| + |E|)</tex>.
== Однопроходный алгоритм ==
Однопроходный алгоритм строится на базе алгоритма поиска мостов. Во-первых, создадим глобальный [[Стек|стек]], и при спуске по дереву <tex> dfs </tex> добавляем в него вершины. Во-вторых, когда возвращаемся назад, проверяем не является ли ребро мостом (при помощи [[Использование обхода в глубину для поиска мостов#Лемма | леммы]]). Если это так, то то все вершины, находящиеся до текущего потомка в стеке, принадлежат одной компоненте.Заметим, что эта компонента будет висячей вершиной в дереве блоков и мостов, так как обходили граф поиском в глубину. Значит, ее можно выкинуть и продолжить поиск в оставшемся графе. Действуя по аналогии в получившемся графе, найдем оставшиеся компоненты реберной двусвязности.
=== Псевдокод:===
Теперь две вершины имеют одинаковый цвет тогда и только тогда, когда они принадлежат одной компоненте реберной двусвязности.
Итоговое время работы алгоритма <tex> O(|V| + |E|)</tex>.
== Визуализатор См. также ==* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bridges-2001| Визуализация построение [Построение компонент реберной двусзяностивершинной двусвязности]] ==Литература==Седжвик Роберт. Фундаментальные алгоритмы на C++. Часть 5: Алгоритмы на графах: Пер. с англ./Роберт Седжвик. — СПб.: ООО «ДиаСофтЮП», 2002. — С. 123-128* [[Использование обхода в глубину для поиска мостов]]
== Источники информации ==* ''Седжвик Р.'' Фундаментальные алгоритмы на C++. Часть 5: Алгоритмы на графах. Пер. с англ. — СПб.: ООО «ДиаСофтЮП», 2002. — С. 123-128* ''Кузнецов В.А.Кузнецов, Караваев. А.М.Караваев. '' "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bridges-2001| Визуализация {{---}} Построение компонент реберной двусзяности]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]