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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Неформальное описание алгоритма[править | править вики-текст]

Algorithm Tarjan.gif

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

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

Время работы[править | править вики-текст]

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

Примечания[править | править вики-текст]

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]

  • 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