Изменения

# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>F</tex> и класс недопускающих состояний (<tex>\mathtt{P} \leftarrow \{ \mathtt{F, \ Q} \setminus \mathtt{F} \}</tex>).# Перебираются символы алфавита <tex>c \in \Sigma</tex>, все пары <<tex>\langle F,\ c\rangle</tex>> и <<tex>\langle Q \setminus F, c\rangle</tex>> помещаются в очередь.# Из очереди извлекается пара <<tex>\langle C,\ a\rangle</tex>>, <tex>C</tex> далее именуется как сплиттер.# Каждый класс <tex>R</tex> текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер (<tex>(R_1)</tex>), а второй из всех оставшихся (<tex>(R_2)</tex>). # Если <tex>R</tex> разбился на два непустых подкласса (т.е. то есть <tex> R_1 \ne \emptyset \ \land \ R_2 \ne \emptyset </tex>).

## Перебираются символы алфавита <tex>c \in \Sigma</tex>, все пары <<tex>\langle R_1, c\rangle</tex>> и <<tex>\langle R_2, c\rangle</tex>> помещаются в очередь.

*<tex>\mathtt{Q}</tex> {{---}} множество состояний ДКА.,*<tex>\mathtt{F}</tex> {{---}} множество терминальных состояний.,*<tex>\mathtt{\delta}</tex> {{---}} функция перехода (<tex>\delta (r,\ a)</tex> {{--- }} состояние, в которое можно совершить переход из <tex>r</tex> по символу <tex>a</tex>),*<tex>\mathtt{S}</tex> {{---}} очередь пар <<tex>\langle C,\ a\rangle</tex>>.,*<tex>\mathtt{P}</tex> {{---}} разбиение множества состояний ДКА.,*<tex>\mathtt{R}</tex> {{---}} класс состояний ДКА.

'''function''' findEquivalenceClasses<tex>\mathtt{findEquivalenceClasses}(\mathtt{Q},\ \mathtt{F},\ \delta)</tex>: '''vector''' <tex>\mathtt{P} \leftarrow \{ \mathtt{F,\ Q} \setminus \mathtt{F} \}</tex>

'''push''' <<tex>\langle F,\ c\rangle</tex>>, <<tex>\langle Q \setminus F,\ c\rangle</tex>> '''into''' <tex> \mathtt{S}</tex>

<<tex>\langle C,\ a\rangle</tex>> <tex>\leftarrow</tex> '''pop''' '''from''' <tex>\mathtt{S}</tex>

''' replace''' <tex>R</tex> '''in''' <tex>\mathtt{P}</tex> '''with''' <tex>R_1</tex> '''and''' <tex>R_2</tex> '''for''' <tex>c \in \Sigma</tex> ''' insert''' <<tex>\langle R_1,\ c\rangle</tex>> '''in''' <tex>\mathtt{S}</tex> ''' insert''' <<tex>\langle R_2,\ c\rangle</tex>> '''in''' <tex>\mathtt{S}</tex>

Время работы алгоритма оценивается как <tex>O(|\Sigma| \cdot n^2)</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex> {{---}} алфавит. Это следует из того, что если пара <<tex>\langle C,\ a\rangle</tex>> попала в очередь, и класс <tex>C</tex> использовался в качестве сплиттера, то при последующем разбиении этого класса в очередь добавляется два класса <tex>C_1</tex> и <tex>C_2</tex>, причем можно гарантировать лишь следующее уменьшение размера: <tex>|C| \ge geqslant |C_i| + 1</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, поэтому каждый переход в автомате будет просмотрен не более, чем <tex>O(n)</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| \cdot n)</tex>, получаем указанную оценку.

:<tex>\forall r \in B \,\,\, \delta(r, a) \in R \ \land \ \delta(r, a) \in R_1\ \lor</tex>:<tex> \ \lor \ \forall r \in B \,\,\, \delta(r, a) \in R \ \land \ \delta(r, a) \notin R_1\ \lor</tex>:<tex> \ \lor \ \forall r \in B \,\,\, \delta(r, a) \notin R \ \land \ \delta(r, a) \notin R_1</tex>

:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_2 \ \lor</tex>:<tex> \ \lor \ \forall r \in B \,\,\, \delta(r, a) \notin R_2</tex>

:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_1 \ \land \ \delta(r, a) \notin R_2\ \lor</tex>:<tex> \ \lor \ \forall r \in B \,\,\, \delta(r, a) \notin R_1 \ \land \ \delta(r, a) \in R_2\ \lor</tex>:<tex> \ \lor \ \forall r \in B \,\,\, \delta(r, a) \notin R_1 \ \land \ \delta(r, a) \notin R_2</tex>

:<tex>\forall r \in B \,\,\, \delta(r, a) \in R \ \lor</tex>:<tex> \ \lor \ \forall r \in B \,\,\, \delta(r, a) \notin R</tex>

Если пара <<tex>\langle R,\ c\rangle</tex>> уже есть в очереди, то согласно лемме можно просто заменить её на пары <<tex>\langle R_1, c\rangle</tex>> и <<tex>\langle R_2, c\rangle</tex>>.

Если пары <<tex>\langle R,\ c\rangle</tex>> нет в очереди, то достаточно добавить любую из пар <<tex>\langle R_1, c\rangle</tex>> и <<tex>\langle R_2, c\rangle</tex>>. Это следует из следующих соображений: <tex>R</tex> может быть в разбиении только если в очередь были положены пары <<tex>\langle R,\ a\rangle</tex>> для <tex>\forall a \in \Sigma</tex>, а поскольку в очереди пары <<tex>\langle R,\ c\rangle</tex>> нет, то мы её уже успели рассмотреть, следовательно классы из разбиения <tex>P</tex> уже были разбиты по <<tex>\langle R,\ c\rangle</tex>>.

*<tex>\mathtt{Q}</tex> {{---}} множество состояний ДКА.,*<tex>\mathtt{F}</tex> {{---}} множество терминальных состояний.,*<tex>\mathtt{\delta}</tex> {{---}} функция перехода (<tex>\delta (r,\ a)</tex> {{--- }} состояние, в которое можно совершить переход из <tex>r</tex> по символу <tex>a</tex>),*<tex>\mathtt{S}</tex> {{---}} очередь пар <<tex>\langle C,\ a\rangle</tex>>.,*<tex>\mathtt{P}</tex> {{---}} разбиение множества состояний ДКА.,*<tex>\mathtt{R}</tex> {{---}} класс состояний ДКА.

'''function''' findEquivalenceClasses<tex>\mathtt{findEquivalenceClasses}(\mathtt{Q},\ \mathtt{F},\ \delta)</tex>: '''vector''' <tex>\mathtt{P} \leftarrow \{ \mathtt{F, \ Q} \setminus \mathtt{F} \}</tex>

'''push''' <<tex>\langle F,\ c\rangle</tex>>, <<tex>\langle Q \setminus F,\ c\rangle</tex>> '''into''' <tex> \mathtt{S}</tex>

<<tex>\langle C,\ a\rangle</tex>> <tex>\leftarrow</tex> '''pop''' '''from''' <tex>\mathtt{S}</tex>

'''if''' <tex> R_1 \ne \varnothing </tex> '''and''' <tex> R_2 \ne \varnothing </tex> replace <tex>R</tex> '''in''' <tex>\mathtt{P}</tex> with' <tex>R_1</tex> '''and''' <tex>R_2</tex> '''replaceif''' <tex>\langle R,\ c \rangle</tex> '''in''' <tex>\mathtt{PS}</tex> <font color=darkgreen>// смотрим, есть ли пара <tex>\langle R,\ c \rangle</tex> в очереди </font> remove <tex>\langle R, c \rangle</tex> '''withfrom''' <tex>\mathtt{S}</tex> <font color=darkgreen>// заменяем её на пары <tex>\langle R_1, c \rangle</tex>, <tex>\langle R_2, c \rangle</tex> если пара есть </font> push <tex>\langle R_1, c \rangle</tex> '''andinto''' <tex>\mathtt{S}</tex> push <tex>\langle R_2, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex> '''forelse''' '''if''' <tex>c |\mathtt{P}[R_1]| \in leqslant |\Sigmamathtt{P}[R_2]| </tex> <font color=darkgreen>// вставляем любую иначе</font> push <tex>\langle R_1, c \rangle</tex> '''into''' <tex>\mathtt{pushSetsToQueueS}(S,</tex> '''else''' push <tex>\ R_1langle R_2,c \ R_2,rangle</tex> '''into''' <tex>\ c)mathtt{S}</tex>

Понятно, что нам нет никакой необходимости просматривать все классы в разбиении. Вполне достаточно рассмотреть лишь те классы, из состояний которых есть хотя бы одно ребро в состояния сплиттера. Обозначим множество таких классов за <tex>T'</tex> (его нужно будет эффективно находить для каждой пары <tex>\mathtt{langle C,\ a \rangle</tex>).  '''function''' findEquivalenceClasses}<tex>(\mathtt{Q},\ \mathtt{F},\ \delta)</tex>: '''vector''' <tex>\mathtt{P} \leftarrow \{ \mathtt{F, \ Q} \setminus \mathtt{F} \}</tex>

'''push''' <<tex>\langle F,\ c\rangle</tex>>, <<tex>\langle Q \setminus F,\ c\rangle</tex>> '''into''' <tex> \mathtt{S}</tex>

<<tex>\langle C,\ a\rangle</tex>> <tex>\leftarrow</tex> '''pop''' '''from''' <tex>\mathtt{S}</tex> <tex>\mathtt{Inverse} \leftarrow \{r \ | \ r \in \mathtt{Q}, \ \delta(r, a) \in C\}</tex> <tex>T' \leftarrow \{R \ | \ R \in \mathtt{P}, \ R \cap \mathtt{Inverse} \neq \varnothing\}</tex> <font color=darkgreen>// находим классы, из состояний которых есть ребро в состояния сплиттера </font> '''for''' <tex>R</tex> '''in''' <tex>T'</tex> <font color=darkgreen>// перебираем только классы входящие в <tex>T'</tex></font>

replace <tex>R</tex> '''in''' <tex>\mathtt{P}</tex> with <tex>R_1</tex> '''and''' <tex>R_2</tex> '''replaceif''' <tex>\langle R,\ c \rangle</tex> '''in''' <tex>\mathtt{PS}</tex> remove <tex>\langle R, c \rangle</tex> '''withfrom''' <tex>\mathtt{S}</tex> push <tex>\langle R_1, c \rangle</tex> '''andinto''' <tex>\mathtt{S}</tex> push <tex>\langle R_2, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex> '''forelse''' '''if''' <tex>c |\mathtt{P}[R_1]| \in leqslant |\Sigmamathtt{P}[R_2]| </tex> push <tex>\langle R_1, c \rangle</tex> '''into''' <tex>\mathtt{pushSetsToQueueS}(S,</tex> '''else''' push <tex>\ R_1langle R_2,c \ R_2,rangle</tex> '''into''' <tex>\ c)mathtt{S}</tex>

Каждая итерация цикла <tex> \mathrm{while} </tex> может быть выполнена за <tex> O(|Q| + |\mathtt{Inverse}|) \,</tex> для текущей пары <<tex>\langle C,\ a\rangle</tex>>. Покажем, как можно достичь этой оценки.

Классы разбиения <tex>P</tex> будем поддерживать с помощью множеств на [[Хеш-таблица | хэш-таблицах]] (само же разбиение {{- --}} обычный вектор, индекс {{--- }} номер класса). Это позволит нам эффективно переносить состояния из одного класса в другой (за <tex>O(1)</tex>).

*<tex>\mathtt{Class}[r]</tex> {{---}} номер класса, которому принадлежит состояние <tex>r</tex>*<tex>\mathtt{Card}[i]</tex> {{---}} размер класса <tex>i</tex>,*<tex>\mathtt{Queue}</tex> {{---}} очередь пар <<tex>\langle C,\ a\rangle</tex>>, где <tex>C</tex> {{---}} номер класса (сплиттера)*<tex>\mathtt{InQueue}</tex> {{---}} двумерный массив булеанов, <tex>\mathtt{InQueue}[C][a] == true</tex>, если <<tex>C,\ a</tex>> находится в очереди <tex>\mathtt{Queue}</tex>*<tex>\mathtt{Inv}[r][a]</tex> {{---}} массив состояний, из которых есть ребра по символу <tex>a</tex> в состояние <tex>r</tex> (мы не меняем исходный автомат, потому может быть построен раз перед началом работы алгоритма).

Для обработки <tex>T'</tex> за <tex>O(|Q| + |\mathtt{Inverse}|)\,</tex> нам понадобится следующая структура:*<tex>\mathtt{Counter}</tex> {{---}} количество классов;*<tex>\mathtt{Involved}</tex> {{---}} список из номеров классов, содержащихся во множестве <tex>T'</tex>;,*<tex>\mathtt{SizeCount}</tex> {{---}} целочисленный массив, где <tex>\mathtt{SizeCount}[i]</tex> хранит количество состояний из класса <tex>i</tex>, которые содержатся в <tex>\mathtt{Inverse}</tex>;,*<tex>\mathtt{Twin}</tex> {{---}} массив, хранящий в <tex>\mathtt{Twin}[i]</tex> номер нового класса, образовавшегося при разбиении класса <tex>i</tex>.

'''function''' findEquivalenceClasses<tex>\mathtt{findEquivalenceClasses}(\mathtt{Q},\ \mathtt{F},\ \delta)</tex>: '''vector''' <tex>\mathtt{P} \leftarrow \{ \mathtt{F, \ Q} \setminus \mathtt{F} \}</tex>

'''push''' <<tex>\langle F,\ c\rangle</tex>>, <<tex>\langle Q \setminus F,\ c\rangle</tex>> '''into''' <tex> \mathtt{Queue}</tex> <tex>\mathtt{InQueue}[F][c] \ \leftarrow \ true</tex> <tex>\mathtt{InQueue}[Q \setminus F][c] \ \leftarrow \ true</tex>

<<tex>\langle C,\ a\rangle</tex>> <tex>\leftarrow</tex> '''pop''' '''from''' <tex>\mathtt{Queue}</tex>

'''if''' <tex>\mathtt{SizeCount}[i] == 0</tex> '''insert''' <tex>i</tex> '''ininto''' <tex>\mathtt{Involved}</tex> <tex>\mathtt{SizeCount}[i]++</tex>

'''if''' <tex>\mathtt{SizeCount}[i] < |\mathtt{CardP}[i]|</tex> insert <tex>\{\}</tex> '''into''' <tex>\mathtt{P}</tex> <font color=darkgreen>// создадим пустой класс в разбиении <tex>\mathtt{SizeP}</tex></font> <tex>\mathtt{Twin}[i] = -1|\mathtt{P}|</tex> <font color=darkgreen> //Пометим сразу, т.к. запишем в следующем цикле классы уже будут менятся<tex>\mathtt{Twin[i]}</tex> индекс нового класса</font>

<tex>j = \mathtt{Twin}[i]</tex> '''if''' <tex>j \neq 0</tex> remove <tex>r</tex> '''from''' <tex>\mathtt{SizeP}[i] == -1</tex> add <tex>r</tex> '''ifto''' <tex>\mathtt{TwinP}[ij] == 0</tex> '''for''' <tex>i \in \mathtt{CounterInvolved}++</tex> <tex>j = \mathtt{Twin}[i]} = \mathtt{Counter}</tex> '''moveif''' <tex>rj \neq 0 </tex> '''fromif''' <tex>|\mathtt{P}[j]| > |\mathtt{P}[i]|</tex> '''to''' <font color=darkgreen>// парный класс должен быть меньшего размера</font> <tex>\mathtt{Twinswap}(\mathtt{P}[i],\ \mathtt{P}[j])</tex> '''in''' <font color=darkgreen>// swap за <tex>\mathtt{PO(1)}</tex> {{---}} просто переставить указатели</font> '''for''' <tex> j r \in \mathtt{InvolvedP}[j]</tex> <font color=darkgreen> // обновляем номера классов для вершин, у которых они изменились</font> '''if''' <tex> \mathtt{TwinClass}[r] = j] \neq 0 </tex> '''for''' <tex>c \in \Sigma</tex> push <tex>\mathtt{pushSetsToQueue}(\mathtt{Queue},\ langle j,c \ \mathtt{Twin}[j],\ c)rangle</tex> '''to''' <tex>\mathtt{SizeQueue}[j] = 0</tex> <tex>\mathtt{TwinCount}[ji] = 0</tex> <tex>\mathtt{InQueueTwin}[Ci][a] \ \leftarrow \ false= 0</tex>

Осталось только реализовать Стоит отметить, что массивы <tex>\mathtt{pushSetsToQueueCount}</tex>. <tex>,\mathtt{pushSetsToQueue}(\mathtt{QueueTwin},\ R_1,\ R_2,\ c)</tex>:аллоцируются ровно один раз при инициализации алгоритма. <tex>cnt1 \leftarrow \mathtt{Card}[R_1]</tex> <tex>cnt2 \leftarrow \mathtt{Card}[R_2]<Также стоит отметить, что собственно наличие/tex> '''if''' отсутствие пары в очереди можно не проверять. Если для некоторого <tex> \mathtt{InQueue}[R_1][c] == false </tex> '''and''' пара <tex> cnt1 \leqslant cnt2 </tex> '''push''' <<tex>R_1langle i, c\rangle</tex>> '''to''' уже была в очереди, то мы добавим её "вторую половинку" <tex>\mathtt{Queue}</tex> <tex>langle \mathtt{InQueueTwin}[R_1i][, c] \ \leftarrow \ truerangle</tex> '''else''' '''push''' <<tex>R_2. Если её в очереди не было, то мы вольны сами выбирать, какой подкласс добавлять в очередь, c</tex>> '''to''' и таким образом добавляем опять же <tex>\mathtt{Queue}</tex> <tex>langle \mathtt{InQueueTwin}[R_2i][, c] \ \leftarrow \ truerangle</tex>.Кроме того, вместо очереди можно использовать вообще произвольную структуру, хранящую элементы, в том числе стэк, множество, так как порядок извлечения нам по сути не важен.

Для доказательства этого утверждения достаточно показать, что количество пар <<tex>\langle C,\ a\rangle</tex>> добавленных в очередь <tex>S</tex> не превосходит <tex> 2 |\Sigma| |Q| </tex>, так как на каждой итерации мы извлекаем одну пару из очереди.

По [[#Лемма1 | лемме(1)]] количество классов не превосходит <tex>2 |Q| - 1</tex>. Пусть <tex>C</tex> элемент текущего разбиения. Тогда количество пар <<tex>\langle C,\ a\rangle</tex>>, <tex>\ a \in \Sigma</tex> не может быть больше <tex>|\Sigma|</tex>. Отсюда следует, что всего различных пар, которые можно добавить в очередь, не превосходит <tex> 2 |\Sigma| |Q| </tex>.

Пусть <tex>a \in \Sigma</tex> и <tex>p \in Q</tex>. Тогда количество пар <<tex>\langle C,\ a\rangle</tex>>, где <tex>p \in C</tex>, которые мы удалим из очереди, не превосходит <tex>\log_2(|Q|)</tex> для фиксированных <tex>a</tex> и <tex>p</tex>.

Рассмотрим пару <<tex>\langle C,\ a\rangle</tex>>, где <tex>p \in C</tex>, которую мы удаляем из очереди. И пусть <<tex>\langle C',a\rangle</tex>> следующая пара, где <tex>p \in C'</tex> и которую мы удалим из очереди. Согласно нашему алгоритму класс <tex>C'</tex> мог появиться в очереди только после операции <tex>\mathtt{replace}</tex>. Но после первого же разбиения класса <tex>C</tex> на подклассы мы добавим в очередь пару <<tex>\langle C'', a\rangle</tex>>, где <tex>C''</tex> меньший из образовавшихся подклассов, то есть <tex>|C''| \leqslant |C| \ / \ 2</tex>. Так же заметим, что <tex>C' \subseteq C''</tex>, а следовательно <tex>|C'| \leqslant |C| \ / \ 2</tex>. Но тогда таких пар не может быть больше, чем <tex>\log_2(|Q|)</tex>.

Пусть <tex>x, y \in Q</tex>, <tex>a \in \Sigma</tex> и <tex> \delta(x, a) = y</tex>. Зафиксируем эту тройку. Заметим, что количество раз, которое <tex>x</tex> встречается в <tex>\mathtt{Inverse}\,</tex> при условии, что <tex> \delta(x, a) = y</tex>, совпадает с числом удаленных из очереди пар <<tex>\langle C,\ a\rangle</tex>>, где <tex>y \in C</tex>. Но по [[#Лемма3 | лемме(3)]] эта величина не превосходит <tex>\log_2(|Q|)</tex>. Просуммировав по всем <tex> x \in Q </tex> и по всем <tex> a \in \Sigma</tex> мы получим утверждение леммы.

*Операции с множеством <tex>T'</tex> и разбиение классов на подклассы требуют <tex>O(\sum(|\mathtt{Inverse}|))\,</tex> времени. Но по [[#Лемма4 | лемме(4)]] <tex>\sum(|\mathtt{Inverse}|)\,</tex> не превосходит <tex>|\Sigma| |Q| \log_2(|Q|)</tex>, то есть данная часть алгоритма выполняется за <tex>O(|\Sigma| |Q| \log_2(|Q|))</tex>.

== Сравнение с алгоритмом из оригинальной статьи Хопкрофта = Альтернативная реализация ===Вообще, алгоритм можно реализовать и с меньшим количеством используемых структур (что делает код на порядок читабельнее).

В оригинальной статье <ref>[http://i.stanford.edu/pub/cstr/reports/cs/tr/71/190/CSВсе классы разбиения будем по-TR-71прежнему хранить в векторе хэш-190.pdf ''John Hopcroft'' An O(nlogn) algorithm for minimizing states in a finite automation]</ref> использовалась дополнительная структура, которую мы обозначим, как сетов <tex>\mathtt{ClassInvP}</tex>, в <tex>\mathtt{ClassInv}[C][a]</tex> будем хранить множество состояний, из которых есть ребро по символу <tex>a</tex> в состояние <tex>C</tex> (аналогично <tex>Inv</tex>, только для классов).

*<tex>\mathtt{ClassInvClass}[Cr][a] = </tex> {{---}} индекс класса в <tex>\mathtt{P}</tex>, которому принадлежит состояние <tex>r</tex>,*<tex>\mathtt{ sQueue}</tex> {{---}} очередь из пар <tex>\langle C,\ |a \ rangle</tex>,*<tex>\mathtt{ClassInv}[sr] == C \ \land \ \delta^[a]</tex> {{-1--} } массив состояний, из которых есть ребра по символу <tex>a</tex> в состояние <tex>r</tex> (sмы не меняем исходный автомат, aпотому может быть построен раз перед началом работы алгоритма) ,*<tex>\neq \emptyset \mathtt{Involved}</tex>{{---}} ассоциативный массив из номеров классов в векторы из номеров вершин.

<tex>\mathtt{pushSetsToQueuefindEquivalenceClasses}(Q,\ F,\ \delta)</tex> реализуем так:  <tex>\mathtt{pushSetsToQueueP}(\mathttleftarrow \{QueueF, \ Q \setminus F \}</tex> '''for''' <tex>c \in \Sigma</tex> insert <tex>\langle F,\ R_1c \rangle</tex>,<tex>\langle Q \ R_2setminus F,\ c)\rangle</tex> '''into''' <tex> \mathtt{Queue}</tex> '''while''' <tex>\mathtt{Queue} \ne \varnothing</tex> <tex>\langle C,\ a \rangle</tex> <tex>cnt1 \leftarrow </tex> pop '''from''' <tex>\mathtt{Queue}</tex> <tex>\mathtt{Involved} = \{\}</tex> '''for''' <tex>q \in C</tex> '''and''' <tex>r \in \mathtt{ClassInvInv}[R_1q][ca]</tex> <tex>cnt2 \leftarrow i = \mathtt{ClassInvClass}[R_2][cr]</tex> '''if''' <tex> \mathtt{InQueueInvolved}[R_1i]== \varnothing</tex> <tex>\mathtt{Involved}[ci] == false \{\}</tex> add <tex>r</tex> '''andto''' <tex> cnt1 \leqslant cnt2 mathtt{Involved}[i]</tex> '''pushfor''' <tex> i \in \mathtt{Involved}</tex>R_1, c<font color=darkgreen>//Перебираем ключи <tex>\mathtt{Involved}</tex></font> '''toif''' <tex>|\mathtt{Involved}[i]| < |\mathtt{QueueP}[i]|</tex> '''insert''' <tex> c \{\}</tex> '''into''' <tex>\mathtt{InQueueP}</tex> <font color=darkgreen>//Создадим пустой класс в разбиении <tex>\mathtt{P}</tex></font> <tex>j = |\mathtt{P}[R_1]|</tex> <font color=darkgreen>//Запишем в <tex>j</tex> индекс нового класса</font> '''elsefor''' <tex>r</tex> '''pushin''' <tex>\mathtt{Involved}[i]</tex> remove <tex>R_2, cr</tex>> '''tofrom''' <tex>\mathtt{QueueP}[i]</tex> '''insert''' add <tex> c r</tex> '''intoto''' <tex>\mathtt{InQueueP}[R_2j]</tex> Циклы  '''forif''' <tex>q |\mathtt{P}[j]| > |\in Cmathtt{P}[i]|</tex> '''and''' <font color=darkgreen>//Парный класс должен быть меньшего размера</font> <tex>r \in mathtt{swap}(\mathtt{InvP}[qi],\ \mathtt{P}[aj])</tex> <font color=darkgreen>//swap за <tex>\mathtt{O(...1)}</tex> {{---}} просто переставить указатели</font> реализуются так:  '''for''' <tex>q r \in \mathtt{ClassInvP}[Cj]</tex> <font color=darkgreen>//Обновляем номера классов для вершин, у которых они изменились</font> <tex>\mathtt{Class}[ar]= j</tex> '''andfor''' <tex>r c \in \Sigma</tex> push <tex>\langle j, c \rangle</tex> '''into''' <tex>\mathtt{InvQueue}[q][a]</tex> (...) '''return''' <tex>\mathtt{P}</tex>

Тогда время работы внутреннего цикла можно будет оценить как <tex>O(|\mathtt{ClassInv}[C][a]| + |\mathtt{Inverse}|)</tex>. А реализация <tex>\mathtt{pushSetsToQueue}</tex> выбирает множество, на котором <tex>O(|\mathtt{ClassInv}[C][a]|)</tex> будет меньшим== См.также ==

Кроме того, вместо * [[Хеш-таблица | хэш-таблицАлгоритм Бржозовского]] для хранения множеств (<tex>\mathtt{ClassInv}</tex>, разбиение <tex>P</tex>) можно использовать комбинацию из двусвязного списка и вектора (добавление/удаление через список, поиск через вектор). Что и используется в оригинальной статье.