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

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

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

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

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

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

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

Алгоритм в псевдокоде

    // входные данные: ориентированный граф G = (V, A) 
    // выходные данные: множество компонент сильной связности 
   
    index := 0
    S := empty stack
    for each v in V do
        if v.index is undefined then
            strongconnect(v)
   
    function strongconnect(v)
        // В index храним количество ранее обработанных вершин, v.index - это "время входа" в вершину v
        v.index := index
        v.lowlink := index
        index := index + 1
        S.push(v)
        // Поле onStack нужно, чтобы проверять принадлежность вершины стеку за O(1)
        v.onStack := true
      
        // Перебираем дуги, исходящие из v
        for each (v, w) in A do
            if w.index is undefined then
                // Вершина w ранее не посещалась; запустимся из неё рекурсивно
                strongconnect(w)
                v.lowlink := min(v.lowlink, w.lowlink)
            else if w.onStack then
                // Вершина w находится в стеке S, значит, принадлежит той же компоненте сильной связности, что и v
                // Если w не в стеке, значит, дуга (v, w) ведёт в ранее обработанную компоненту сильной связности и должна быть проигнорирована
                // Замечание: в следующей строке намеренно используется w.index вместо w.lowlink - это отсылает к исходной статье Тарьяна
                // Если заменить w.index на w.lowlink, алгоритм останется корректным
                v.lowlink := min(v.lowlink, w.index)
      
        // Вершина v - корень текущей компоненты сильной связности, все верхние вершины стека образуют эту компоненту
        if v.lowlink = v.index then
            создать новую компоненту сильной связности
            repeat
                w := S.pop()
                w.onStack := false
                добавить w в текущую компоненту сильной связности
            while w ≠ v
            вывести текущую компоненту сильной связности

Время работы

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

См. также

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

Ссылки

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

Литература

• Tarjan R. E. Depth-first search and linear graph algorithms (англ.) // SIAM Journal on Computing. — 1972. — Vol. 1, no. 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.