Алгоритм Тар'яна — алгоритм пошуку компонент сильної зв'язності в орієнтованому графі, що працює за лінійний час.
анімація алгоритму Тар'яна | |
Структура даних | Граф |
---|---|
Найгірша швидкодія |
Цей алгоритм ґрунтується на тому, що:
- Вершини розглядаються у зворотному топологічному порядку, тому в кінці рекурсивної функції для початкової вершини не зустрінеться жодна вершина з тієї ж сильної компоненти, оскільки всі вершини, досяжні з початкової, вже опрацьовано.
- Зворотні зв'язки в дереві дають інший шлях з однієї вершини в іншу і зв'язують сильні компоненти.
Неформальний опис алгоритму
Алгоритм Тар'яна можна розуміти як варіацію алгоритму пошуку в глибину, в якому під час відвідування вершини і при закінченні опрацювання вершини виконуються додаткові дії. Відвідування вершини відбувається при русі від кореня до листя, а закінчення обробки вершини — на зворотному шляху. Під час відвідування вершини вона проштовхується в допоміжний стек, а виштовхується звідти при закінченні опрацювання.
Індекси компонент зв'язності всіх вершин зберігаються у векторі id, індексованому номерами вершин. Вектор low відстежує вершину з найменшим номером у прямому порядку обходу, досяжну з кожного вузла через послідовність прямих зв'язків, за якими слідує один висхідний зв'язок. Скориставшись пошуком у глибину з тим, щоб розглядати вершини в зворотному топологічному порядку, для кожної вершини v обчислюється максимальна точка, досяжна через зворотний зв'язок із попередника (low[v]). Коли для вершини v виконується pre[v]=low[v], вона виштовхується зі стека, а також всі вершини вище від неї і всім їм присвоюється номер компоненти[].
Час роботи
Алгоритм має часову складність , де — кількість ребер, а — кількість вершин графу.
Простова складність становить , бо стек може вирости не більш ніж до (коли граф це одна велика компонента). Також ми зберігаємо додаткові ознаки для вершин.
Алгоритм у псевдокоді
алгоритм Тар'яна це вхід: граф 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 вивести поточну компоненту сильної зв'язності
Змінна index
це лічильник порядку вершини в обході в глибину. S
це стек вершин, який напочатку порожній і зберігає історію досліджених вершин, які ще не були записані до якоїсь КСЗ. Зауважте, що це не звичаний стек пошуку в глибину, бо ми не виштовхуємо вершини з нього коли повертаємось вгору деревом, ми виштовхуємо їх лише коли повна компонента сильної зв'язності була знайдена.
Коли кожна вершина завершує рекурсію, якщо її lowlink
все ще рівний її index
, тоді це корінь компоненти сильної зв'язності, утвореної всіма вершинами вище в стеку. Алгоритм виштовхує зі стеку все вище цієї вершини і її саму записуючи всі ці вершини в нову компоненту.
Див. також
- — аналогічний алгоритм, що використовує пошук у глибину.
Примітки
Література
- Tarjan R. E. Depth-first search and linear graph algorithms // SIAM Journal on Computing. — 1972. — Vol. 1, no. 2 (13 July). — P. 146–160. — DOI: .
Посилання
- Реалізація алгоритму Тар'яна на Java [ 19 березня 2021 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm Tar yana algoritm poshuku komponent silnoyi zv yaznosti v oriyentovanomu grafi sho pracyuye za linijnij chas animaciya algoritmu Tar yanaStruktura danihGrafNajgirsha shvidkodiyaO V E displaystyle O V E Cej algoritm gruntuyetsya na tomu sho Vershini rozglyadayutsya u zvorotnomu topologichnomu poryadku tomu v kinci rekursivnoyi funkciyi dlya pochatkovoyi vershini ne zustrinetsya zhodna vershina z tiyeyi zh silnoyi komponenti oskilki vsi vershini dosyazhni z pochatkovoyi vzhe opracovano Zvorotni zv yazki v derevi dayut inshij shlyah z odniyeyi vershini v inshu i zv yazuyut silni komponenti Neformalnij opis algoritmuAlgoritm Tar yana mozhna rozumiti yak variaciyu algoritmu poshuku v glibinu v yakomu pid chas vidviduvannya vershini i pri zakinchenni opracyuvannya vershini vikonuyutsya dodatkovi diyi Vidviduvannya vershini vidbuvayetsya pri rusi vid korenya do listya a zakinchennya obrobki vershini na zvorotnomu shlyahu Pid chas vidviduvannya vershini vona proshtovhuyetsya v dopomizhnij stek a vishtovhuyetsya zvidti pri zakinchenni opracyuvannya Indeksi komponent zv yaznosti vsih vershin zberigayutsya u vektori id indeksovanomu nomerami vershin Vektor low vidstezhuye vershinu z najmenshim nomerom u pryamomu poryadku obhodu dosyazhnu z kozhnogo vuzla cherez poslidovnist pryamih zv yazkiv za yakimi sliduye odin vishidnij zv yazok Skoristavshis poshukom u glibinu z tim shob rozglyadati vershini v zvorotnomu topologichnomu poryadku dlya kozhnoyi vershini v obchislyuyetsya maksimalna tochka dosyazhna cherez zvorotnij zv yazok iz poperednika low v Koli dlya vershini v vikonuyetsya pre v low v vona vishtovhuyetsya zi steka a takozh vsi vershini vishe vid neyi i vsim yim prisvoyuyetsya nomer komponenti dzherelo Chas robotiAlgoritm maye chasovu skladnist O V E displaystyle mathrm O V E de E displaystyle E kilkist reber a V displaystyle V kilkist vershin grafu Prostova skladnist stanovit O V displaystyle mathrm O V bo stek mozhe virosti ne bilsh nizh do V displaystyle V koli graf ce odna velika komponenta Takozh mi zberigayemo dodatkovi oznaki dlya vershin Algoritm u psevdokodialgoritm Tar yana ce vhid graf G V E vihid mnozhina komponent silnoyi zv yaznosti mnozhini vershin index 0 S porozhnij stek dlya kozhnogo v z V zrobiti yaksho v index neviznachenij todi silnozv yazna v funkciya silnozv yazna v Vstanoviti indeks glibini dlya v u najmenshij nezajnyatij indeks v index index v lowlink index index index 1 S push v v onStack istina Nastupnici v dlya kozhnogo v w z E zrobiti yaksho w index neviznachenij todi Cyu nastupnicyu w she ne vidviduvali zapuskayemo rekursiyu na nij silnozv yazna w v lowlink min v lowlink w lowlink inakshe yaksho w onStack todi Nastupnicya w na steku S i znachit v potochnij KSZ yakshowne na steku todi v w ce rebro sho vkazuye na vzhe znajdenu KSZ i mi yim nehtuyemo Primitka Nastupnij ryadok mozhe viglyadati divnim ale vin pravilnij Vin vikoristovuye w index a ne w lowlink ce navmisno i bulo v originalnij statti v lowlink min v lowlink w index Yaksho v ce korin to vishtovhnuti zi steku i poroditi KSZ yaksho v lowlink v index todi rozpochati novu komponentu silnoyi zv yaznosti povtoryuvati w S pop w onStack hiba dodati w do potochnoyi komponenti silnoyi zv yaznosti dopoki w v vivesti potochnu komponentu silnoyi zv yaznosti Zminna index ce lichilnik poryadku vershini v obhodi v glibinu S ce stek vershin yakij napochatku porozhnij i zberigaye istoriyu doslidzhenih vershin yaki she ne buli zapisani do yakoyis KSZ Zauvazhte sho ce ne zvichanij stek poshuku v glibinu bo mi ne vishtovhuyemo vershini z nogo koli povertayemos vgoru derevom mi vishtovhuyemo yih lishe koli povna komponenta silnoyi zv yaznosti bula znajdena Koli kozhna vershina zavershuye rekursiyu yaksho yiyi i lowlink i vse she rivnij yiyi i index i todi ce korin komponenti silnoyi zv yaznosti utvorenoyi vsima vershinami vishe v steku Algoritm vishtovhuye zi steku vse vishe ciyeyi vershini i yiyi samu zapisuyuchi vsi ci vershini v novu komponentu Div takozh analogichnij algoritm sho vikoristovuye poshuk u glibinu PrimitkiDzheremi Sik i dr 2006 LiteraturaTarjan R E Depth first search and linear graph algorithms SIAM Journal on Computing 1972 Vol 1 no 2 13 July P 146 160 DOI 10 1137 0201010 PosilannyaRealizaciya algoritmu Tar yana na Java 19 bereznya 2021 u Wayback Machine