Алгоритм Пурдома

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Алгоритм Пурдома находит транзитивное замыкание ориентированного графа за время [math]O(\mu n)[/math], где [math]\mu \le m[/math] – число рёбер, соединяющих компоненты сильной связности этого графа.

1.2 Математическое описание

Алгоритм основан на следующих свойствах:

1. Если вершины [math]v[/math] и [math]w[/math] принадлежат одной компоненте сильной связности графа [math]G[/math], то его транзитивное замыкание [math]G^+[/math] содержит рёбра [math](v, w)[/math] и [math](w, v)[/math].
2. Если вершины [math]x[/math] и [math]y[/math] принадлежат одной компоненте сильной связности графа [math]G[/math], а вершины [math]z[/math] и [math]t[/math] – другой, то рёбра [math](x, z)[/math], [math](x, t)[/math], [math](y, z)[/math], [math](y, t)[/math] принадлежат или не принадлежат транзитивному замыканию [math]G^+[/math] одновременно.

Таким образом, поиск транзитивного замыкания графа [math]G[/math] сводится к поиску транзитивного замыкания ациклического графа [math]\tilde G[/math], полученного из [math]G[/math] схлопыванием каждой компоненты сильной связности в одну вершину. Транзитивное замыкание ациклического графа вычисляется с использованием топологической сортировки вершин графа.

1.4 Макроструктура алгоритма

Вычисления производятся в четыре этапа:

1. Найти компоненты сильной связности исходного графа, заменить каждую компоненту на одну вершину и удалить образовавшиеся рёбра-петли.
2. Выполнить топологическую сортировку полученного ациклического графа [math]\tilde G[/math].
3. Вычислить транзитивное замыкание графа [math]\tilde G[/math], двигаясь от вершин с бо́льшими номерами к меньшим.
4. По найденному транзитивному замыканию [math]\tilde G[/math] восстановить транзитивное замыкание исходного графа.

Последний этап не является обязательным, если рассматривать транзитивное замыкание [math]\tilde G[/math] как «упакованное» транзитивное замыкание [math]G[/math].

2 Программная реализация алгоритмов

2.7 Существующие реализации алгоритма

• Boost Graph Library (функция transitive_closure).