212
правок
Изменения
→Однопроходный алгоритм
В алгоритме выполняется два прохода <tex>dfs</tex>, каждый из которых работает <tex>O(V + E)</tex>. Значит время работы алгоритма <tex>O(V + E)</tex>.
==Однопроходный алгоритм==
Заведем стек, в который будем записывать все дуги в порядке их обработки. Если обнаружена точка сочленения, дуги очередного блока окажутся в этом стеке, начиная с дуги дерева обхода, которая привела в этот блок, до верхушки стека. <br>
Таким образом, каждый раз находя компоненту вершинной двусвязности мы сможем покрасить все ребра, содержащиеся в ней, в новый цвет.
===Доказательство корректности алгоритма===
Предположим, что граф содержит точку сочленения <tex> i' \in V </tex> , за которой следует один или несколько блоков. Вершины из этих блоков образуют подмножество <tex> V' \subset V </tex>. В таком случае: <br>
# Все вершины <tex> V' </tex> являются потомками <tex> i' </tex> в дереве обхода;
# В <tex> G </tex> не может быть обратных дуг из <tex> V' </tex> в <tex> V \setminus V' </tex>.<br>
Значит все дуги <tex> V' </tex> будут будут добавлены в стек после дуги ведущей из точки сочленения в блок. В стеке в момент обнаружения точки сочленения будут находиться только дуги блока, связанного с ней, т.к. блоки найденные до него (если таковые имеются) будет уже извлечены из стека и покрашены в свой цвет.<br>
=== Псевдокод === '''Псевдокод: function''' <tex>dfs</tex>(<tex>v, parent</tex>, parent): enter[<tex>enter[v</tex>] <tex>\leftarrow </tex> return[<tex>v</tex>] <tex>\leftarrow time</tex>time++ для всех вершин '''for''' <tex>u\in V : (v, u) \in E</tex> смежных : '''if''' <tex>vu</tex>:== parent continue если ('''if''' '''not''' visited[<tex>u</tex> родитель) ] переходим к следующей итерации если stack.push(<tex>uvu</tex> не посещена) добавить в стек ребро<tex>vudfs</tex> dfs(<tex>u, v</tex>) если ('''if''' return[<tex>return[u</tex>] <tex>\geqslant</tex>= enter[<tex>v]</tex>)] color <tex>c \leftarrow </tex> новый цветmaxColor++ пока '''while''' stack.top(ребро ) != <tex>vu</tex> не равно вершине стека) <tex>color</tex>colors[вершина стекаstack.top()] <tex> \leftarrow c</tex>color извлечь вершину стекаstack.pop() colors[<tex>color[vu</tex>] <tex>\leftarrow c</tex>color извлечь вершину стекаstack.pop() если ('''if''' return[<tex>return[u</tex>] < return[<tex>v]</tex>)] return[<tex>return[v</tex>] <tex>\leftarrow </tex> return[<tex>u]</tex>] иначе'''else''' если ('''if''' enter[<tex>enter[u</tex>] < enter[<tex>v]</tex>) ] добавить в стек ребро stack.push(<tex>vu</tex>) если ('''else''' return[<tex>return[v</tex>] > enter[<tex>u]</tex>)] return[<tex>return[v</tex>] <tex>\leftarrow </tex> return[<tex>u]</tex>] start()... для всех '''for''' <tex>v\in V</tex> вершин графа: если ( '''if''' '''not''' visited[<tex>v</tex> не посещена)] time <tex>time \leftarrow 0</tex>0 <tex>dfs</tex>(<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>
