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

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

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

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

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

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

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

Время работы

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

См. также

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

Примечания

Ссылки

Литература

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