Перегляд вихідного коду сторінки Алгоритм Тар'яна

{{Картка_алгоритм
|назва=
|зображення= [[File:Tarjan's Algorithm Animation.gif|250px]]
|підпис= анімація алгоритму Тар'яна
|клас=
|дані= [[Граф (абстрактний тип даних)|Граф]]
|час= <math>O(|V|+|E|)</math>
|найкращий_час=
|середній_час=
|простір=
|оптимальний=
|стабільний=
}}
'''Алгоритм Тар'яна'''&nbsp;— алгоритм пошуку [[Компонента сильної зв'язності графу|компонент сильної зв'язності]] в [[Орієнтований граф|орієнтованому графі]], що працює за лінійний час.

Цей алгоритм ґрунтується на тому, що:

# Вершини розглядаються у зворотному топологічному порядку, тому в кінці рекурсивної функції для початкової вершини не зустрінеться жодна вершина з тієї ж сильної компоненти, оскільки всі вершини, досяжні з початкової, вже опрацьовано.
# Зворотні зв'язки в дереві дають інший шлях з однієї вершини в іншу і зв'язують сильні компоненти.

== Неформальний опис алгоритму ==
[[Файл:Algorithm_Tarjan.png|550x550пкс|right]]

Алгоритм Тар'яна можна розуміти як варіацію алгоритму [[Пошук у глибину|пошуку в глибину]], в якому під час відвідування вершини і при закінченні опрацювання вершини виконуються додаткові дії. Відвідування вершини відбувається при русі від кореня до листя, а закінчення обробки вершини&nbsp;— на зворотному шляху. Під час відвідування вершини вона проштовхується в допоміжний стек, а виштовхується звідти при закінченні опрацювання{{Sfn|Джереми Сик и др.|2006}}.

Індекси компонент зв'язності всіх вершин зберігаються у векторі id, індексованому номерами вершин. Вектор low відстежує вершину з найменшим номером у прямому порядку обходу, досяжну з кожного вузла через послідовність прямих зв'язків, за якими слідує один висхідний зв'язок. Скориставшись пошуком у глибину з тим, щоб розглядати вершини в зворотному топологічному порядку, для кожної вершини v обчислюється максимальна точка, досяжна через зворотний зв'язок із попередника (low[v]). Коли для вершини v виконується pre[v]=low[v], вона виштовхується зі стека, а також всі вершини вище від неї і всім їм присвоюється номер компоненти{{Джерело?}}.

== Час роботи ==
Алгоритм має часову складність <math>\mathrm{O}(|V|+|E|)</math>, де <math>|E|</math>&nbsp;— кількість ребер, а <math>|V|</math>&nbsp;— кількість вершин графу{{Sfn|Джереми Сик и др.|2006}}.

Простова складність становить <math>\mathrm{O}(|V|)</math>, бо стек може вирости не більш ніж до <math>|V|</math> (коли граф це одна велика компонента). Також ми зберігаємо додаткові ознаки для вершин.

== Алгоритм у псевдокоді ==
 
 '''алгоритм''' Тар'яна '''це'''
     '''вхід:''' граф ''G'' = (''V'', ''E'')
     '''вихід:''' множина компонент сильної зв'язності (множини вершин)
    
     ''index'' := 0
     ''S'' := порожній стек
     '''для кожного''' ''v'' '''з''' ''V'' '''зробити'''
         '''якщо''' ''v''.index невизначений '''тоді'''
             сильнозв'язна(''v'')
    
     '''функція''' сильнозв'язна(''v'')
         ''// Встановити індекс глибини для v у найменший незайнятий індекс''
         ''v''.index := ''index''
         ''v''.lowlink := ''index''
         ''index'' := ''index'' + 1
         ''S''.push(''v'')
         ''v''.onStack := істина
       
         ''// Наступниці v''
         '''для кожного''' (''v'', ''w'') '''з''' ''E'' '''зробити'''
             '''якщо''' ''w''.index невизначений '''тоді'''
                 ''// Цю наступницю w ше не відвідували; запускаємо рекурсію на ній''
                 сильнозв'язна(''w'')
                 ''v''.lowlink := min(''v''.lowlink, ''w''.lowlink)
             '''інакше, якщо''' ''w''.onStack '''тоді'''
                 ''// Наступниця w на стеку S і, значить, в поточній КСЗ''
                 ''// якщо ''w'' не на стеку, тоді (''v'', ''w'') це ребро, що вказує на вже знайдену КСЗ і ми їм нехтуємо
                 ''// Примітка: Наступний рядок може виглядати дивним, але він правильний.''
                 ''// Він використовує w.index, а не w.lowlink; це навмисно і було в оригінальній статті''
                 ''v''.lowlink := min(''v''.lowlink, ''w''.index)
       
         ''// Якщо v це корінь, то виштовхнути зі стеку і породити КСЗ''
         '''якщо''' ''v''.lowlink = ''v''.index '''тоді'''
             розпочати нову компоненту сильної зв'язності
             '''повторювати'''
                 ''w'' := ''S''.pop()
                 ''w''.onStack := хиба
                 додати ''w'' до поточної компоненти сильної зв'язності
             '''допоки''' ''w'' ≠ ''v''
             вивести поточну компоненту сильної зв'язності

Змінна <code>index</code> це лічильник порядку вершини в [[Пошук у глибину|обході в глибину]]. <code>S</code> це стек вершин, який напочатку порожній і зберігає історію досліджених вершин, які ще не були записані до якоїсь КСЗ. Зауважте, що це не звичаний стек пошуку в глибину, бо ми не виштовхуємо вершини з нього коли повертаємось вгору деревом, ми виштовхуємо їх лише коли повна компонента сильної зв'язності була знайдена.

Коли кожна вершина завершує рекурсію, якщо її <code>''lowlink''</code> все ще рівний її <code>''index''</code>, тоді це корінь компоненти сильної зв'язності, утвореної всіма вершинами вище в стеку. Алгоритм виштовхує зі стеку все вище цієї вершини і її саму записуючи всі ці вершини в нову компоненту.

== Див. також ==
* [[Алгоритм знаходження компонент сильної зв'язності]]&nbsp;— аналогічний алгоритм, що використовує пошук у глибину.

== Примітки ==
{{Reflist}}

== Література ==
* {{Стаття|author=Tarjan R. E.|title=Depth-first search and linear graph algorithms|language=en|видання=SIAM Journal on Computing|date=1972|том=1|номер=2|pages=146–160|doi=10.1137/0201010}}

== Посилання ==
* [https://web.archive.org/web/20080531010721/http://rain.ifmo.ru/cat/view.php/vis/graph-general/scc-2008 Візуалізатор алгоритмів пошуку компонент сильної зв'язності]
* [http://sites.google.com/site/indy256/algo/scc_tarjan Реалізація алгоритму Тар'яна на Java] {{Webarchive|url=https://web.archive.org/web/20210319023536/https://sites.google.com/site/indy256/algo/scc_tarjan |date=19 березня 2021 }}

{{Алгоритми на графах}}
[[Категорія:Алгоритми на графах]]