394
правки
Изменения
Нет описания правки
==Реализация==
'''Псевдокод второго прохода:
{| width = 100%
|-
|
dfs(<tex>v, c, parent</tex>)
для всех вершин u смежных v:
если (<tex>u</tex> родитель)
переходим к следующей итерации
если (<tex>u</tex> не посещена)
если (<tex>return[u] >= enter[v]</tex>)
<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>
start()
для всех v вершин графа:
если (<tex>v</tex> не посещена)
dfs(<tex>v, -1, -1</tex>)
|width = "310px" |[[Файл:Vertex_doubleconnection_1.png|thumb|center|400px|Компоненты обозначены разным цветом]]
|}
<b>Вход</b>: граф <tex>G = (V, E)</tex><br>
<b>Выход</b>: минимальный остов <tex>F</tex> графа <tex>G</tex><br>
