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

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

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

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

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

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

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

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

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

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

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

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

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

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

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