Алгоритм Тарьяна
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/60/Tarjan%27s_Algorithm_Animation.gif/220px-Tarjan%27s_Algorithm_Animation.gif)
Алгоритм Тарьяна — алгоритм поиска компонент сильной связности в орграфе, работающий за линейное время.
Этот алгоритм основан на том, что:
- Вершины рассматриваются в обратном топологическом порядке, поэтому в конце рекурсивной функции для исходной вершины не будет встречено ни одной вершины из той же компоненты сильной связности, так как все вершины, достижимые из исходной, уже обработаны.
- Обратные связи в дереве дают второй путь из одной вершины в другую и связывают компоненты сильной связности в одну.
Неформальное описание алгоритма
[править | править код]Алгоритм Тарьяна можно понимать как вариацию алгоритма поиска в глубину, в котором при посещении вершины и окончании обработки вершины выполняются дополнительные действия. Посещение вершины происходит при движении от корня к листьям, а окончание обработки вершины — на обратном пути... При посещении вершины она проталкивается во вспомогательный стек, при окончании обработки компоненты сильной связности все её вершины выталкиваются из этого стека[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 вывести текущую компоненту сильной связности
Время работы
[править | править код]Алгоритм имеет временну́ю сложность , где — количество рёбер, а — вершин графа[1].
См. также
[править | править код]Алгоритм поиска компонент сильной связности с двумя стеками — аналогичный алгоритм, использующий поиск в глубину.
Примечания
[править | править код]Ссылки
[править | править код]Литература
[править | править код]- 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.