Алгоритм Тарьяна (Glikjnmb Mgj,xug)

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

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

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

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

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

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

    // входные данные: ориентированный граф 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
            вывести текущую компоненту сильной связности

Время работы

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

См. также

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

Примечания

↑ ¹ ² Джереми Сик и др., 2006.

Ссылки

Литература

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.

[_4e983efe9644fec8-1] ¹ ² Джереми Сик и др., 2006.

[1]