188
правок
Изменения
Нет описания правки
Таким образом, после завершения внешнего цикла у нас будет $W[i][j] = true$, если между этими вершинами есть путь, содержащий в качестве промежуточных вершин из множества всех остальных вершин графа, что и есть транзитивное замыкание.
</wikitex>
=== Оптимизация с помощью битовых масок ===
Строки матрицы <tex>W</tex> можно хранить с помощью массива битовых маск длиной <tex>k</tex>. Тогда последний цикл будет выполняться в <tex>k</tex> раз быстрее и сложность алгоритма снижается до <tex>O(\frac{n^3}{k})</tex>.
Пример реализации с использованием массива чисел типа ''unsigned int'':
'''unsigned int''' W[N][N / 32 + 1]
''...''
'''for''' k = 1 '''to''' n
'''for''' i = 1 '''to''' n
'''if''' бит с номером ''(k % 32)'' в маске ''a[i][k / 32]'' единичный
'''for''' j = 1 '''to''' n
W[i][j] = W[i][j] '''or''' W[k][j]
== Источники информации ==
