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

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

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

Алгоритм Пурдома находит транзитивное замыкание ориентированного графа за время [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] схлопыванием каждой компоненты сильной связности в одну вершину. Транзитивное замыкание ациклического графа вычисляется с использованием топологической сортировки вершин графа.