Изменения

Перейти к: навигация, поиск

Построение компонент вершинной двусвязности

1510 байт убрано, 08:32, 1 декабря 2011
Нет описания правки
'''Первый проход
Используем первый проход, чтобы [[Использование обхода в глубину для поиска точек сочленения|найти точки сочленения.]] <br>
Определим для каждой вершины две величины: <tex> enter [i] </tex> - время входа поиска в глубину в вершину <tex> i </tex>, <tex> return [i] </tex> – минимальное из времен входа вершин, достижимых из <tex> i </tex> по дереву <tex> dfs </tex> и не более, чем одному обратному ребру. Ребро к родителю не является обратным ребром. <br>
 
'''Псевдокод первого прохода:
dfs(<tex>v</tex>, <tex>parent</tex>)
<tex>enter[v] \leftarrow return[v] \leftarrow time</tex>++
для всех вершин <tex>u</tex> смежных <tex>v</tex>:
если (<tex>u</tex> родитель)
переходим к следующей итерации
если (<tex>u</tex> посещена)
<tex>return[v] \leftarrow min(return[v], enter[u])</tex>
иначе
dfs(<tex>u, v</tex>)
<tex>return[v] \leftarrow min(return[v], return[u])</tex>
start()
для всех <tex>v</tex> вершин графа:
если (<tex>v</tex> не посещена)
<tex>time \leftarrow 0</tex>
dfs(<tex>v, -1</tex>)
'''Второй проход
dfs(<tex>v, -1, -1</tex>)
Ребра каждой из компонент вершинной двусвязности окажутся окрашенными в свой цвет.
 ==Время работы двупроходного алгоритма==<br>
В алгоритме выполняется два прохода <tex>dfs</tex>, каждый из которых работает <tex>O(V + E)</tex>. Значит время работы алгоритма <tex>O(V + E)</tex>.
<tex>time \leftarrow 0</tex>
dfs(<tex>v</tex>, -1)
 ==Время работы однопроходного алгоритма==<br>
Во время алгоритма совершается один проход <tex>dfs</tex>, который работает за <tex>O(V + E)</tex>. Внутри него совершается еще цикл, уоторый суммарно выполняет <tex>O(E)</tex> операций, т.к. каждое ребро может быть добавлено в стек только один раз. Следовательно Общее время работы алгоритма <tex>O(V + E) + O(E) = O(V + E)</tex>
==Литература==
* В.А.Кузнецов, А.М.Караваев. "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007
Dimitrova
148
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/13754»

Навигация