Меню
Главная
Случайная статья
Настройки
|
Алгоритм Тарьяна — алгоритм поиска компонент сильной связности в орграфе, работающий за линейное время.
Этот алгоритм основан на том, что:
- Вершины рассматриваются в обратном топологическом порядке, поэтому в конце рекурсивной функции для исходной вершины не будет встречено ни одной вершины из той же компоненты сильной связности, так как все вершины, достижимые из исходной, уже обработаны.
- Обратные связи в дереве дают второй путь из одной вершины в другую и связывают компоненты сильной связности в одну.
Неформальное описание алгоритма
Алгоритм Тарьяна можно понимать как вариацию алгоритма поиска в глубину, в котором при посещении вершины и окончании обработки вершины выполняются дополнительные действия. Посещение вершины происходит при движении от корня к листьям, а окончание обработки вершины — на обратном пути... При посещении вершины она проталкивается во вспомогательный стек, при окончании обработки компоненты сильной связности все её вершины выталкиваются из этого стека[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].
См. также
Алгоритм поиска компонент сильной связности с двумя стеками — аналогичный алгоритм, использующий поиск в глубину.
Примечания
- 1 2 Джереми Сик и др., 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.
|
|
