Построение компонент рёберной двусвязности — различия между версиями
Novik (обсуждение | вклад) м |
Novik (обсуждение | вклад) (→Двупроходный алгоритм) |
||
Строка 8: | Строка 8: | ||
Воспользуемся ранее доказанной [[Использование обхода в глубину для поиска мостов#Лемма | леммой]]. Получается {{---}} перешли по мосту, следовательно началась новая компонента. | Воспользуемся ранее доказанной [[Использование обхода в глубину для поиска мостов#Лемма | леммой]]. Получается {{---}} перешли по мосту, следовательно началась новая компонента. | ||
− | '''Первый проход:''' | + | '''Первый проход:''' запустим [[Использование обхода в глубину для поиска мостов|алгоритм для поиска мостов]], чтобы посчитать две величины: <tex>tin(v)</tex> и <tex>up(v)</tex>. |
− | '''Второй проход:''' | + | '''Второй проход:''' окрашиваем вершины, т.е. если перешли по мосту, то оказались в новой компоненте реберной двусвязности. |
− | |||
=== Псевдокод второго прохода === | === Псевдокод второго прохода === | ||
+ | * В переменной <tex>\mathtt{color}</tex> хранится цвет текущей компоненты. | ||
+ | * <tex>\mathtt{maxColor}</tex> изначально равен <tex>0</tex>, что эквивалентно тому, что никакая компонента не окрашена. | ||
'''function''' paint(<tex>v</tex>, color): | '''function''' paint(<tex>v</tex>, color): |
Версия 17:05, 11 ноября 2015
Построение компонент реберной двусвязности будет осуществляться с помощью обхода в глубину.
Содержание
Двупроходный алгоритм
Первый способ найти искомые компоненты — сначала определить критерий перехода в новую компоненту реберной двусвязности, а затем покрасить вершины графа в нужные цвета.
Определим критерий перехода к новой компоненте. Воспользуемся ранее доказанной леммой. Получается — перешли по мосту, следовательно началась новая компонента.
Первый проход: запустим алгоритм для поиска мостов, чтобы посчитать две величины: и .
Второй проход: окрашиваем вершины, т.е. если перешли по мосту, то оказались в новой компоненте реберной двусвязности.
Псевдокод второго прохода
- В переменной хранится цвет текущей компоненты.
- изначально равен , что эквивалентно тому, что никакая компонента не окрашена.
function paint(, color): colors[ ] = color for : if colors[ ] == 0: if up[ ] > tin[ ]: maxColor++ paint( , maxColor) else: paint( , color)
function solve(): for: colors[ ] = 0 if not visited[ ] dfs( ) maxColor = 0 for : if colors[ ] == 0: maxColor++ paint( , maxColor)
Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цвет.
Время работы алгоритма будет время работы двух запусков dfs, то есть
, что есть .Однопроходный алгоритм
Однопроходный алгоритм строится на базе алгоритма поиска мостов. Во-первых, создадим глобальный стек, и при спуске по дереву добавляем в него вершины. Во-вторых, когда возвращаемся назад, проверяем не является ли ребро мостом (при помощи леммы). Если это так, то то все вершины, находящиеся до текущего потомка в стеке, принадлежат одной компоненте.Заметим, что эта компонента будет висячей вершиной в дереве блоков и мостов, так как обходили граф поиском в глубину. Значит, ее можно выкинуть и продолжить поиск в оставшемся графе. Действуя по аналогии в получившемся графе, найдем оставшиеся компоненты реберной двусвязности.
Псевдокод
function paint(): maxColor++ while stack.top() != and not stack.empty() colors[stack.top()] = maxColor stack.pop()
function dfs() time = time + 1 stack.push( ) tin[ ] = time up[ ] = time for : if — обратное ребро up[ ] = min(up[ ], tin[ ]) if not visited[ ] dfs( ) up[ ] = min(up[ ], up[ ]) if up[ ] > tin[ ] paint( )
Теперь две вершины имеют одинаковый цвет тогда и только тогда, когда они принадлежат одной компоненте реберной двусвязности.
Время работы dfs
. Покраска за . Итоговое время работы алгоритма .См. также
Источники информации
- Седжвик Р. Фундаментальные алгоритмы на C++. Часть 5: Алгоритмы на графах. Пер. с англ. — СПб.: ООО «ДиаСофтЮП», 2002. — С. 123-128
- Кузнецов В.А., Караваев. А.М. "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007
- Визуализация — Построение компонент реберной двусзяности