148
правок
Изменения
→Двупроходный алгоритм
'''Псевдокод первого прохода:
dfs(<tex>v</tex>, <tex>parent</tex>) { <tex>enter[v] = \leftarrow return[v] = \leftarrow time</tex>++; used[v] = true; для всех вершин <tex>u </tex> смежных <tex>v</tex>: если (<tex>u == parent</tex> родитель):
переходим к следующей итерации
если (used[<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> } void start() { used для всех вершин заполняем false для всех <tex>v </tex> вершин графа: если (!used[<tex>v]</tex> не посещена): <tex>time = \leftarrow 0;</tex> dfs(<tex>v, -1</tex>); }
'''Второй проход
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.<br>
'''Псевдокод второго прохода:
для всех вершин u смежных v:
если (<tex>u == parent</tex> родитель):
переходим к следующей итерации
если (!used[<tex>u]</tex> не посещена): если (<tex>return[u] >= enter[v]</tex>): с2 = newColor();<tex>c2 \leftarrow</tex> новый цвет <tex>col[vu] = \leftarrow c2;</tex> dfs(<tex>u, c2, v</tex>); иначе: <tex>col[vu] = \leftarrow c;</tex> dfs(<tex>u, c, v</tex>);
иначе:
если (<tex>enter[u] <= enter[v]</tex>): <tex>col[vu] = \leftarrow c; </tex> } void start() { used для всех вершин заполняем false;
для всех v вершин графа:
если (!used[<tex>v]</tex> не посещена): dfs(<tex>v, -1, -1</tex>); }
Ребра каждой из компонент вершинной двусвязности окажутся окрашенными в свой цвет.
==Время работы двупроходного алгоритма==
В алгоритме выполняется два прохода <tex>dfs</tex>, каждый из которых работает <tex>O(V + E)</tex>. Значит время работы алгоритма <tex>O(V + E)</tex>.
==Однопроходный алгоритм==
