Изменения

Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))

10 байт убрано, 19:54, 16 января 2017

→‎Альтернативная реализация

<tex>\mathtt{P} \leftarrow \{ F, \ Q \setminus F \}</tex>

'''for''' <tex>c \in \Sigma</tex>

~~'''~~insert~~'''~~ <tex>\langle F,\ c \rangle</tex>, <tex>\langle Q \setminus F,\ c \rangle</tex> '''into''' <tex> \mathtt{Queue}</tex>

'''while''' <tex>\mathtt{Queue} \ne \varnothing</tex>

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

<tex>\mathtt{Involved} = \{\}</tex>

'''for''' <tex>q \in C</tex> '''and''' <tex>r \in \mathtt{Inv}[q][a]</tex>

'''if''' <tex>\mathtt{Involved}[i] == \varnothing</tex>

<tex>\mathtt{Involved}[i] = \{\}</tex>

~~'''~~add~~'''~~ <tex>r</tex> '''to''' <tex>\mathtt{Involved}[i]</tex>

'''for''' <tex> i \in \mathtt{Involved}</tex> //Перебираем ключи <tex>\mathtt{Involved}</tex>

'''if''' <tex>|\mathtt{Involved}[i]| < |\mathtt{P}[i]|</tex>

<tex>j = |\mathtt{P}|</tex> //Запишем в <tex>j</tex> индекс нового класса

'''for''' <tex>r</tex> '''in''' <tex>\mathtt{Involved}[i]</tex>

~~'''~~remove~~'''~~ <tex>r</tex> '''from''' <tex>\mathtt{P}[i]</tex> ~~'''~~add~~'''~~ <tex>r</tex> '''to''' <tex>\mathtt{P}[j]</tex>

'''if''' <tex>|\mathtt{P}[j]| > |\mathtt{P}[i]|</tex> //Парный класс должен быть меньшего размера

<tex>\mathtt{swap}(\mathtt{P}[i],\ \mathtt{P}[j])</tex> //swap за <tex>\mathtt{O(1) }</tex> - просто переставить указатели

'''for''' <tex>r \in \mathtt{P}[j]</tex> //Обновляем номера классов для вершин, у которых они изменились

<tex>\mathtt{Class}[r] = j</tex>

'''for''' <tex>c \in \Sigma</tex>

~~'''~~push~~'''~~ <tex>\langle j, c \rangle</tex> '''into''' <tex>\mathtt{Queue}</tex>

'''return''' <tex>\mathtt{P}</tex>

Анонимный участник