418
правок
Изменения
→Псевдокод
Функция для построения списка обратных ребер.
'''vector'''[][] buildReverseEdges('''int''' n, '''int'''[][] <tex>\delta</tex>):
'''int''' <tex>\delta^{-1}</tex>[n][n]
'''for''' i = 0 .. n - 1
'''for''' c <tex>\in</tex> <tex>\Sigma</tex>
<tex>\delta^{-1}</tex>[<tex>\delta</tex>[i][c]][c].add(i)
'''return''' <tex>\delta^{-1}</tex>
Функция для проверки достижимости состояний.
marked[r][s] = marked[s][r] = true
Q.push(<tex>\langle r, s \rangle</tex>)
Основная функция алгоритма.
'''function''' minimization('''int''' n, '''boolean'''[] isTerminal, '''int'''[][] <tex>\delta</tex>):
<font color="green">// Шаг 1</font>
'''int'''[][] <tex>\delta^{-1}</tex> = buildReverseEdges(n, <tex>\delta</tex>)
<font color="green">// Шаг 2</font>
'''boolean''' reachable[n]
checkReachability(1, reachable)
<font color="green">// Шаг 3</font>
'''queue''' Q
'''boolean''' marked[n][n]
initTable(n, isTerminal, Q, marked)
<font color="green">// Шаг 4</font>
computeTable(n, <tex>\delta^{-1}</tex>, Q, marked)
<font color="green">// Шаг 5</font>
'''int'''[] component[n] <font color="green">// По позиции i будем хранить номер компоненты эквивалентности для i-ого состояния.</font>
fill(component, -1)
'''list''' classes <font color="green">// По позиции i будем хранить представителя i-ой компоненты эквивалентности.</font>
'''for''' i = 0 .. n - 1
'''if''' '''not''' table[0][i]
component[i] = 0
'''int''' components_count = 0
'''for''' i = 1 .. n - 1
'''if''' '''not''' visited[i]
continue
'''if''' component[i] == -1
components_count++
component[i] = components_count
classes.add(i)
'''for''' j = i + 1 .. n - 1
'''if''' '''not''' table[i][j]
component[j] = components_count
<font color="green">// Шаг 6</font>
'''for''' i = 0 .. length(classes) - 1
'''int''' u = component[classes[i]]
'''for''' c <tex>\in</tex> <tex>\Sigma</tex>
if reachable[<tex>\delta</tex>[classes[i]][c]] '''and''' component[<tex>\delta</tex>[classes[i]][c]] != 0
int v = component[<tex>\delta</tex>[classes[i]][c]]
output(u ->[c]-> v) <font color="green">// Ребро из u в v по символу c</font>
==Асимптотики==
