Алгоритм сильно связных компонентов Тарьяна - Tarjans strongly connected components algorithm

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

Алгоритм сильносвязных компонентов Тарьяна является алгоритм в теория графов для поиска компоненты сильной связности (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 необходимо удалить как корень компоненты сильной связности, если v.lowlink == v.index. Значение v.lowlink вычисляется во время поиска в глубину из v, так как это находит узлы, доступные из v.

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










алгоритм Tarjan является    Вход: график грамм = (V, E)    выход: множество компонент сильной связности (множества вершин) индекс := 0    S : = пустой стек для каждого v в V делать        если v.index не определен тогда            Strongconnect (v)        конец, если    конец для       функция Strongconnect (v)        // Устанавливаем индекс глубины для v равным наименьшему неиспользуемому индексу        v.index: = индекс        v.lowlink: = индекс        индекс := индекс + 1        S.толкать(v)        v.onStack: = истина // Рассмотрим наследников v        для каждого (v, ш) в E делать            если ш.index не определен тогда                // Наследник w еще не был посещен; повторить это                Strongconnect (ш)                v.lowlink: = мин (v.lowlink, ш.lowlink) иначе если ш.onStack тогда                // Преемник w находится в стеке S и, следовательно, в текущем SCC                // Если ш не в стеке, то (v, ш) - это край, указывающий на уже найденный SCC, и его следует игнорировать                // Примечание: следующая строка может выглядеть странно, но правильная.                // Он говорит, что w.index не w.lowlink; это сделано намеренно и из оригинальной статьи                v.lowlink: = мин (v.lowlink, ш.индекс) конец, если        конец для              // Если v является корневым узлом, извлекаем стек и генерируем SCC        если v.lowlink = v.индекс тогда            запустить новый компонент с сильной связью повторение                ш := S.pop () ш.onStack: = false добавить ш к текущему сильно связному компоненту пока ш ≠ v            вывести текущий сильно связанный компонент конец, если    конечная функция
В индекс Переменная - счетчик числа узлов поиска в глубину. S - это стек узлов, который начинается пустым и хранит историю узлов, исследованных, но еще не закрепленных за сильно связным компонентом. Обратите внимание, что это не обычный стек поиска в глубину, поскольку узлы не выталкиваются, когда поиск возвращается вверх по дереву; они выскакивают только тогда, когда обнаруживается вся сильно связная компонента.
Самый внешний цикл просматривает каждый узел, который еще не был посещен, гарантируя, что узлы, недоступные с первого узла, в конечном итоге будут пройдены. Функция Strongconnect выполняет один поиск в глубину графа, находя всех последователей узла v, и сообщая обо всех сильно связанных компонентах этого подграфа.
Когда каждый узел завершает рекурсию, если его lowlink все еще установлен на его индекс, тогда это корневой узел сильно связного компонента, образованный всеми узлами над ним в стеке. Алгоритм выдвигает стек до текущего узла включительно и представляет все эти узлы как сильно связанный компонент.
Обратите внимание, что v.lowlink: = мин (v.lowlink, ш.индекс)  это правильный способ обновления v.lowlink если ш находится в стеке. Потому что ш уже в стеке, (v, w) это задний край в дереве DFS и, следовательно, ш не входит в поддерево v. Потому что v.lowlink учитывает узлы, достижимые только через узлы в поддереве v мы должны остановиться на ш и использовать w.index вместо w.lowlink.
Сложность









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









Хотя нет ничего особенного в порядке узлов в каждом сильно связном компоненте, одно полезное свойство алгоритма заключается в том, что ни один сильно связанный компонент не будет идентифицирован до любого из его преемников. Следовательно, порядок, в котором идентифицируются компоненты сильной связи, составляет обратный топологическая сортировка из DAG образованный сильно связными компонентами.^[4]
Дональд Кнут описал алгоритм SCC Тарьяна как одну из его любимых реализаций в книге Стэнфордская база данных GraphBase.^[5]
Он также написал:^[6] 
Структуры данных, которые он разработал для этой задачи, удивительно красиво сочетаются друг с другом, так что величины, на которые нужно смотреть при изучении ориентированного графа, всегда волшебным образом у вас под рукой. И его алгоритм также выполняет топологическую сортировку в качестве побочного продукта.
Рекомендации









^ Тарьян, Р.Э. (1972), "Поиск в глубину и алгоритмы линейного графа", SIAM Журнал по вычислениям, 1 (2): 146–160, Дои:10.1137/0201010
^ Нуутила, Эско (1994). «Об отыскании сильно связанных компонентов в ориентированном графе». Письма об обработке информации. 49 (1): 9–14. Дои:10.1016/0020-0190(94)90047-7.
^ Пирс, Дэвид. «Эффективный с точки зрения пространства алгоритм для обнаружения сильно связанных компонентов». Письма об обработке информации. 116 (1): 47–52. Дои:10.1016 / j.ipl.2015.08.010.
^ Харрисон, Пол. «Надежная топологическая сортировка и алгоритм Тарьяна в Python». Получено 9 февраля 2011.
^ Кнут, Стэнфордская база данных GraphBase, страницы 512–519.
^ Кнут, Дональд (2014-05-20). Двадцать вопросов Дональду Кнуту.

[1] Тарьян, Р.Э. (1972), "Поиск в глубину и алгоритмы линейного графа", SIAM Журнал по вычислениям, 1 (2): 146–160, Дои:10.1137/0201010

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

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

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

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

[6] Кнут, Дональд (2014-05-20). Двадцать вопросов Дональду Кнуту.

[1]

[2]

[3]

[4]

[5]

[6]