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

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

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

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

Неформальное описание алгоритма

Алгоритм Тарьяна можно понимать как вариацию алгоритма поиска в глубину, в котором при посещении вершины и окончании обработки вершины выполняются дополнительные действия. Посещение вершины происходит при движении от корня к листьям, а окончание обработки вершины — на обратном пути. При посещении вершины она проталкивается во вспомогательный стек, а выталкивается при окончании обработки^[1].

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

Время работы

Алгоритм имеет временну́ю сложность $\mathrm{O}(|V|+|E|)$, где $|V|$ — количество рёбер, а $|E|$ — вершин графа^[1].

Примечания

1. ↑ ^{1 2} Джереми Сик и др., 2006

Ссылки

• Визуализатор алгоритмов поиска компонент сильной связности
• Реализация алгоритма Тарьяна на Java

Литература

• Tarjan R. E. Depth-first search and linear graph algorithms (англ.) // SIAM Journal on Computing. — 1972. — Т. 1. — № 2. — P. 146–160. — DOI:10.1137/0201010
• Роберт Седжвик. Алгоритмы на графах = Graph algorithms. — 3-е изд. — Россия, Санкт-Петербург: «ДиаСофтЮП», 2002. — С. 496. — ISBN 5-93772-054-7
• Джереми Сик, Лай-Кван Ли, Эндрю Ламсдэйн. C++ Boost Graph Library. — Питер, 2006. — С. 202-205. — 304 с. — ISBN 5-469-00352-3