Алгоритм Тарьяна

Алгоритм Тарьяна, алгоритм поиска компонент сильной связности в орграфе, работающий за линейное время.

Этот алгоритм основан на том, что:

1) Мы рассматриваем вершины в обратном топологическом порядке, поэтому, когда мы придем в конец рекурсивной функции для исходной вершины, мы не встретим ни одной вершины из той же сильной компоненты, так как все вершины, достижимые из этой, уже обработаны.

2) Обратные связи в дереве дают второй путь из одной вершины в другую и связывают сильные компоненты.

В основе А.Т. лежит рекурсивный поиск в глубину, в который добавлена операция проталкивания вершин в стек. Он вычисляет индекс компоненты для каждой вершины в векторе id, индексированном именами вершин, используя векторы pre и low (справа). Вектор low отслеживает вершину с наименьшим номером в прямом порядке обхода, достижимую из каждого узла через последовательность прямых связей, за которыми следует одна восходящая связь. Воспользовавшись поиском в глубину с тем, чтобы рассматривать вершины в обратном топологическом порядке, мы вычисляем для каждой вершины v максимальную точку, достижимую через обратную связь из предшественника (low[v]). Когда для вершины v выполняется pre[v]=low[v], мы выталкиваем ее из стека, а также все вершины выше ее и всем им присваиваем номер следующей компоненты.

Этот метод линеен по времени, так как в данном случае к стандартному DFS добавляется несколько операций, работающих за константу.

Лит.: Роберт Седжвик. Алгоритмы на графах = Graph algorithms — 3-е изд. — Россия, Санкт-Петербург: «ДиаСофтЮП», 2002. — С. 496. — ISBN 5-93772-054-7.