Алгоритм Тарьяна | это... Что такое Алгоритм Тарьяна? (original) (raw)

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

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

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

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

Algorithm Tarjan.gif

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

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

Время работы

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

Примечания

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

Ссылки

Литература