Алгоритм сильно связанных компонентов Тарьяна

Алгоритм сильно связанных компонентов Тарьяна
	Анимация алгоритма Тарьяна
Структура данных	График
Худшая производительность

Алгоритм сильно связанных компонентов Тарьяна — это алгоритм в теории графов для поиска сильно связанных компонентов (SCC) ориентированного графа . Он работает за линейное время , что соответствует временным ограничениям для альтернативных методов, включая алгоритм Косараджу и алгоритм сильной компоненты на основе путей . Алгоритм назван в честь его изобретателя Роберта Тарьяна . ^{[ 1 ]}

Обзор

Алгоритм принимает ориентированный граф в качестве входных данных и разбивает вершины на графа сильно связные компоненты графа. Каждая вершина графа входит ровно в одну из сильно связных компонент. Любая вершина, не входящая в направленный цикл, сама по себе образует сильно связный компонент: например, вершина, входящая или исходящая степень которой равна 0, или любая вершина ациклического графа.

Основная идея алгоритма такова: поиск в глубину (DFS) начинается с произвольного начального узла (и последующие поиски в глубину проводятся на любых узлах, которые еще не были найдены). Как обычно при поиске в глубину, поиск посещает каждый узел графа ровно один раз, отказываясь повторно посещать любой узел, который уже был посещен. Таким образом, совокупность деревьев поиска представляет собой остовный лес графа. Сильно связанные компоненты будут восстановлены как определенные поддеревья этого леса. Корни этих поддеревьев называются «корнями» сильно связных компонент. Любой узел сильно связанного компонента может служить корнем, если он оказывается первым узлом компонента, обнаруженного при поиске.

Инвариант стека

Узлы помещаются в стек в том порядке, в котором они посещаются. Когда поиск в глубину рекурсивно посещает узел v и его потомков, эти узлы не обязательно извлекаются из стека, когда этот рекурсивный вызов возвращается. Важнейшим инвариантным свойством является то, что узел остается в стеке после того, как его посетили, тогда и только тогда, когда во входном графе существует путь от него к какому-либо узлу, находящемуся ранее в стеке. Другими словами, это означает, что в DFS узел будет удален из стека только после того, как будут пройдены все его связанные пути. Когда DFS выполнит возврат, он удалит узлы на одном пути и вернется к корню, чтобы начать новый путь.

В конце звонка, который посещает v и его потомков, мы знаем, v сам имеет путь к любому узлу, находящемуся ранее в стеке. Если да, вызов возвращается, оставляя v в стеке, чтобы сохранить инвариант. Если нет, то v должен быть корнем своей сильно связной компоненты, состоящей из v вместе с любыми узлами, расположенными позже в стеке, чем v (все такие узлы имеют пути обратно к v но не к любому более раннему узлу, потому что если бы у них были пути к более ранним узлам, то v также будут иметь пути к более ранним узлам, что неверно). Связный компонент с корнем в v затем извлекается из стека и возвращается, снова сохраняя инвариант.

Бухгалтерия

Каждый узел v присваивается уникальное целое число v.index, который нумерует узлы последовательно в порядке их обнаружения. Он также сохраняет ценность v.lowlink который представляет собой наименьший индекс любого узла в стеке, который, как известно, доступен из v через vподдерево DFS, включая v сам. Поэтому v должен быть оставлен в стеке, если v.lowlink < v.index, тогда как v необходимо удалить как корень сильно связного компонента, если v.lowlink == v.index. Значение v.lowlink вычисляется во время поиска в глубину из v, так как при этом находятся узлы, достижимые из v.

Lowlink отличается от lowpoint, который представляет собой наименьший индекс, достижимый из v через любую часть графика. ^{[ 1 ]}^: 156^{[ 2 ]}

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

algorithm tarjan is
    input: graph G = (V, E)
    output: set of strongly connected components (sets of vertices)
   
    index := 0
    S := empty stack
    for each v in V do
        if v.index is undefined then
            strongconnect(v)
   
    function strongconnect(v)
        // Set the depth index for v to the smallest unused index
        v.index := index
        v.lowlink := index
        index := index + 1
        S.push(v)
        v.onStack := true
      
        // Consider successors of v
        for each (v, w) in E do
            if w.index is undefined then
                // Successor w has not yet been visited; recurse on it
                strongconnect(w)
                v.lowlink := min(v.lowlink, w.lowlink)
            else if w.onStack then
                // Successor w is in stack S and hence in the current SCC
                // If w is not on stack, then (v, w) is an edge pointing to an SCC already found and must be ignored
                // See below regarding the next line
                v.lowlink := min(v.lowlink, w.index)
      
        // If v is a root node, pop the stack and generate an SCC
        if v.lowlink = v.index then
            start a new strongly connected component
            repeat
                w := S.pop()
                w.onStack := false
                add w to current strongly connected component
            while w ≠ v
            output the current strongly connected component

The index Переменная — счетчик количества узлов поиска в глубину. S — это стек узлов, который изначально пуст и хранит историю узлов, исследованных, но еще не привязанных к сильно связанному компоненту. Это не обычный стек поиска в глубину, поскольку узлы не извлекаются при возврате поиска вверх по дереву; они извлекаются только тогда, когда найден весь сильно связанный компонент.

Самый внешний цикл ищет каждый узел, который еще не был посещен, гарантируя, что узлы, которые недоступны из первого узла, все равно в конечном итоге будут пройдены. Функция strongconnect выполняет одиночный поиск в глубину графа, находя всех преемников узла vи сообщать обо всех сильно связанных компонентах этого подграфа.

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

В статье Тарьяна, когда w находится в стеке, v.lowlink обновляется с заданием v.lowlink := min(v.lowlink, w.index). ^{[ 1 ]}^: 157 Распространенным вариантом является использование вместо этого v.lowlink := min(v.lowlink, w.lowlink). ^{[ 3 ]}^{[ 4 ]} Этот модифицированный алгоритм не вычисляет числа нижних звеньев, как их определил Тарьян, но тест v.lowlink = v.index по-прежнему идентифицирует корневые узлы сильно связанных компонентов, и поэтому общий алгоритм остается действительным. ^{[ 2 ]}

Сложность

Временная сложность : процедура Tarjan вызывается один раз для каждого узла; оператор forall рассматривает каждое ребро не более одного раза. Таким образом, время работы алгоритма линейно зависит от количества ребер и узлов в G, т.е. $O(|V|+|E|)$ .

Чтобы достичь этой сложности, необходимо проверить, является ли w находится в стеке, должно выполняться за постоянное время. Это можно сделать, как в приведенном выше псевдокоде: сохранить на каждом узле флаг, указывающий, находится ли он в стеке, и выполнить этот тест, проверив флаг.

Пространственная сложность : процедура Тарьяна требует двух слов дополнительных данных на каждую вершину для index и lowlink поля, а также один бит для onStack и еще один для определения того, когда index является неопределенным. Кроме того, для хранения каждого кадра стека требуется одно слово. v и еще один для текущей позиции в списке ребер. Наконец, наихудший размер стека S должно быть $|V|$ (т.е. когда граф представляет собой одну гигантскую компоненту). Это дает окончательный анализ $O(|V|\cdot (2+5w))$ где $w$ — размер машинного слова. Вариант Нуутилы и Сойсалона-Сойнинена свел это к $O(|V|\cdot (1+4w))$ и, следовательно, теория Пирса требует только $O(|V|\cdot (1+3w))$ . ^{[ 5 ]}^{[ 6 ]}

Дополнительные замечания

Хотя в порядке узлов внутри каждого сильно связного компонента нет ничего особенного, одно полезное свойство алгоритма заключается в том, что ни один сильно связный компонент не будет идентифицирован раньше любого из его преемников. Следовательно, порядок идентификации сильно связанных компонентов представляет собой обратную топологическую разновидность DAG , образованную сильно связными компонентами. ^{[ 7 ]}

Дональд Кнут описал алгоритм SCC Тарьяна как одну из своих любимых реализаций в книге The Stanford GraphBase . ^{[ 8 ]}

Он также написал: ^{[ 9 ]}

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

Ссылки

^ Перейти обратно: ^а ^б ^с Тарьян, Р.Э. (1972), «Алгоритмы поиска в глубину и линейные графы» (PDF) , SIAM Journal on Computing , 1 (2): 146–160, CiteSeerX 10.1.1.327.8418 , doi : 10.1137/0201010
^ Перейти обратно: ^а ^б «Лекция № 19: Поиск в глубину и сильные компоненты» (PDF) , 15-451/651: Проектирование и анализ алгоритмов , Карнеги-Меллон, 1 ноября 2018 г.
^ Корди, Петр; Лангерак, Ром; Мау, Сьюке; Полдерман, Ян Виллем (2014), «Символический алгоритм для анализа робастных временных автоматов» (PDF) , в книге Джонса, Клиффа Б.; Пихлаясаари, Пекка; Сан, июнь (ред.), FM 2014: Формальные методы – 19-й Международный симпозиум, Сингапур, 12–16 мая 2014 г. Труды , конспекты лекций по информатике, том. 8442, Springer, стр. 351–366, номер doi : 10.1007/978-3-319-06410-9_25 , ISBN. 978-3-319-06409-3
^ «Лекция 19: Алгоритм Тарьяна для идентификации сильно связанных компонентов в графе зависимостей» (PDF) , Разработка программного обеспечения CS130 , Калифорнийский технологический институт, зима 2024 г.
^ Нуутила, Эско (1994), «О поиске сильно связанных компонентов в ориентированном графе», Information Processing Letters , 49 (1): 9–14, doi : 10.1016/0020-0190(94)90047-7
^ Пирс, Дэвид, «Эффективный с точки зрения использования пространства алгоритм для обнаружения сильно связанных компонентов», Information Processing Letters , 116 (1): 47–52, doi : 10.1016/j.ipl.2015.08.010
^ Харрисон, Пол, «Надежная топологическая сортировка и алгоритм Тарьяна в Python» , получено 9 февраля 2011 г.
^ Кнут, Стэнфордская GraphBase , страницы 512–519.
^ Кнут, Дональд (20 мая 2014 г.), Двадцать вопросов Дональду Кнуту

Внешние ссылки

Rosetta Code , показывающий реализации на разных языках
PHP-реализация алгоритма сильно связанных компонентов Тарьяна
Реализация JavaScript алгоритма сильно связанных компонентов Тарьяна

[Tarjan-1] Перейти обратно: ^а ^б ^с Тарьян, Р.Э. (1972), «Алгоритмы поиска в глубину и линейные графы» (PDF) , SIAM Journal on Computing , 1 (2): 146–160, CiteSeerX 10.1.1.327.8418 , doi : 10.1137/0201010

[CMU2018-2] Перейти обратно: ^а ^б «Лекция № 19: Поиск в глубину и сильные компоненты» (PDF) , 15-451/651: Проектирование и анализ алгоритмов , Карнеги-Меллон, 1 ноября 2018 г.

[3] Корди, Петр; Лангерак, Ром; Мау, Сьюке; Полдерман, Ян Виллем (2014), «Символический алгоритм для анализа робастных временных автоматов» (PDF) , в книге Джонса, Клиффа Б.; Пихлаясаари, Пекка; Сан, июнь (ред.), FM 2014: Формальные методы – 19-й Международный симпозиум, Сингапур, 12–16 мая 2014 г. Труды , конспекты лекций по информатике, том. 8442, Springer, стр. 351–366, номер doi : 10.1007/978-3-319-06410-9_25 , ISBN. 978-3-319-06409-3

[4] «Лекция 19: Алгоритм Тарьяна для идентификации сильно связанных компонентов в графе зависимостей» (PDF) , Разработка программного обеспечения CS130 , Калифорнийский технологический институт, зима 2024 г.

[5] Нуутила, Эско (1994), «О поиске сильно связанных компонентов в ориентированном графе», Information Processing Letters , 49 (1): 9–14, doi : 10.1016/0020-0190(94)90047-7

[6] Пирс, Дэвид, «Эффективный с точки зрения использования пространства алгоритм для обнаружения сильно связанных компонентов», Information Processing Letters , 116 (1): 47–52, doi : 10.1016/j.ipl.2015.08.010

[7] Харрисон, Пол, «Надежная топологическая сортировка и алгоритм Тарьяна в Python» , получено 9 февраля 2011 г.

[8] Кнут, Стэнфордская GraphBase , страницы 512–519.

[9] Кнут, Дональд (20 мая 2014 г.), Двадцать вопросов Дональду Кнуту

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]