Офлайновий алгоритм Тарджана для пошуку найменшого спільного предка — алгоритм для знаходження найменшого спільного предка пари вузлів у дереві. Він названий на честь Роберта Андре Тарджана, який відкрив цей алгоритм у 1979 році. Алгоритм Тарджана не є алгоритмом реального часу, тобто, він вимагає, щоб усі пари вузлів, для яких потрібно знайти найменший спільний предок, були вказані заздалегідь.
Формальне визначення завдання
Дано дерево з
вершинами і дано
запитів виду (
,
), потрібно для кожного запиту (
,
) знайти найменшого спільного предка, тобто, таку вершину
, яка найбільш віддалена від кореня дерева і при цьому є предком для обох вершин
та
.
Алгоритм
Опис
Основою для алгоритму є структура даних «система неперетинних множин», яка і була винайдена Тарджаном.
Алгоритм фактично являє собою обхід у глибину із кореня дерева, в процесі якого поступово знаходяться відповіді на запити. А саме, відповідь на запит знаходиться, коли обхід у глибину обробляє вершину , а вершина
вже була відвідана, або навпаки.
Підвісимо наше дерево за будь-яку вершину, і запустимо обхід у глибину з неї. Нехай обхід дерева у глибину знаходиться в деякій вершині . Помістимо її в окремий клас в структурі неперетинних множин,
. Як завжди, в обході у глибину, перебираємо усі вихідні ребра
. Для кожного такого
запускаємо обхід у глибину із цієї вершини, а потім додаємо цю вершину разом з її піддеревом в клас вершини
. Це реалізується операціями структури даних «система неперетинних множин», присвоюванням
для представника множини (так як після об'єднання представник класу міг змінитися). Після обробки всіх ребер ми перебираємо всі запити виду
, і якщо вершина
була позначена як відвідана обходом у глибину, то відповіддю на цей запит буде вершина
. Очевидно, що для кожного запиту ця умова (що одна вершина запиту оброблюється обходом у глибину, а друга була відвідана раніше) виповниться рівно один раз.
Псевдокод
Псевдокод нижче визначає найменший спільний предок для кожної пари із , задано корінь дерева у якому діти вузла
зберігаються у множині
. Для цього алгоритму, множина
повинна бути вказана заздалегідь. В процедурі використовуються MakeSet, Find та Union функції системи неперетинних множин.
розміщує елемент
в нову множину, що складається з одного нього,
повертає представника множини, у якій міститься
,
створює нову множину, яка є об'єднанням множин, які містять
і
.
function TarjanOLCA(u) is MakeSet(u) u.ancestor := u for each v in u.children do TarjanOLCA(v) Union(u, v) Find(u).ancestor := u u.color := black for each v such that {u, v} in P do if v.color == black then print "Tarjan's Lowest Common Ancestor of " + u + " and " + v + " is " + Find(v).ancestor + "."
Нижче наведено оптимізовані версії функцій MakeSet , Union і Find(використано (евристику стиснення шляху) та (евристику об'єднання за рангом)(в наведеному нижче псевдокоді рангову евристику реалізовано на основі глибини дерев)).
function MakeSet(x) is x.parent := x x.rank := 1 function Union(x, y) is xRoot := Find(x) yRoot := Find(y) if xRoot.rank > yRoot.rank then yRoot.parent := xRoot else if xRoot.rank < yRoot.rank then xRoot.parent := yRoot else if xRoot.rank == yRoot.rank then yRoot.parent := xRoot xRoot.rank := xRoot.rank + 1 function Find(x) is if x.parent != x then x.parent := Find(x.parent) return x.parent
Приклад реалізації мовою С++
#include <iostream> #include <vector> using namespace std; const int N = 100001; // N - максимальна кількість вершин у дереві vector < int > g[N], q[N]; int ancestor[N], parent[N], r[N]; bool visited[N]; void MakeSet(int x) { parent[x] = x; r[x] = 1; } int FindSet(int x ) { if (x == parent[x]) return x; return parent[x] = FindSet(parent[x]); } void Union(int x, int y) { int xRoot = FindSet(x), int yRoot = FindSet(y); if (r[xRoot] < r[yRoot]) swap(xRoot, yRoot); parent[yRoot] = xRoot; r[xRoot] += r[yRoot]; } void TarjanLCA(int v , int p) { MakeSet(v); ancestor[v] = v; for (int i = 0; i < g[v].size(); i++) if (g[v][i] != p ) { TarjanLCA(g[v][i] , v); Union(g[v][i], v); ancestor[FindSet(v)] = v; } visited[v] = true; for (int i = 0; i < q[v].size(); i++) if (visited[q[v][i]]) cout << "Tarjan's Lowest Common Ancestor of " << v << " and " << q[v][i] << " is " << ancestor[FindSet(q[v][i])] << '/n'; } int main() { // Тут зчитуємо структуру графу та запити (звідки-небудь, наприклад, з файлу). TarjanLCA(1 , -1); //вважаємо , що коренем дерева є вершина під номером 1 }
Оцінка складності алгоритму
Оцінка складності алгоритму складається із декількох частин.
- Обхід у глибину виконується за
.
- Операції по об'єднанню множин, які в сумі працюють за
, де
— обернена функція Акермана, яка зростає дуже повільно, настільки повільно, що для всіх розумних обмежень вона не перевершує 4 (приблизно для
). Саме тому про асимптотику роботи системи неперетинних множин доречно говорити «майже константний час роботи» —
. Кожний запит буде оброблений рівно один раз, тому можна вважати, що всі запити обробляються сумарно за
.
- Для кожного запиту перевірка умови і визначення результату для всіх розумних
виконується за
.
Отже, складність алгоритму — , що при достатньо великих
складає
на один запит.
Література
- Наименьший общий предок. Нахождение за O(1) в оффлайн (алгоритм Тарьяна)(рос.)
- Алгоритм Тарьяна поиска LCA за O(1) в оффлайн (рос.)
- Tarjan's off-line lowest common ancestors algorithm (англ.)
- Gabow, H. N.; Tarjan, R. E. (1983), A linear-time algorithm for a special case of disjoint set union, Proceedings of the 15th ACM Symposium on Theory of Computing (STOC), с. 246—251, doi:10.1145/800061.808753.
- Tarjan, R. E. (1979), Applications of path compression on balanced trees, , 26 (4): 690—715, doi:10.1145/322154.322161.
Див. також
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Oflajnovij algoritm Tardzhana dlya poshuku najmenshogo spilnogo predka algoritm dlya znahodzhennya najmenshogo spilnogo predka pari vuzliv u derevi Vin nazvanij na chest Roberta Andre Tardzhana yakij vidkriv cej algoritm u 1979 roci Algoritm Tardzhana ne ye algoritmom realnogo chasu tobto vin vimagaye shob usi pari vuzliv dlya yakih potribno znajti najmenshij spilnij predok buli vkazani zazdalegid Formalne viznachennya zavdannyaDano derevo G displaystyle G z n displaystyle n vershinami i dano m displaystyle m zapitiv vidu ai displaystyle a i bi displaystyle b i potribno dlya kozhnogo zapitu ai displaystyle a i bi displaystyle b i znajti najmenshogo spilnogo predka tobto taku vershinu ci displaystyle c i yaka najbilsh viddalena vid korenya dereva i pri comu ye predkom dlya oboh vershin ai displaystyle a i ta bi displaystyle b i AlgoritmOpis Osnovoyu dlya algoritmu ye struktura danih sistema neperetinnih mnozhin yaka i bula vinajdena Tardzhanom Algoritm faktichno yavlyaye soboyu obhid u glibinu iz korenya dereva v procesi yakogo postupovo znahodyatsya vidpovidi na zapiti A same vidpovid na zapit znahoditsya koli obhid u glibinu obroblyaye vershinu v displaystyle v a vershina u displaystyle u vzhe bula vidvidana abo navpaki Pidvisimo nashe derevo za bud yaku vershinu i zapustimo obhid u glibinu z neyi Nehaj obhid dereva u glibinu znahoditsya v deyakij vershini v displaystyle v Pomistimo yiyi v okremij klas v strukturi neperetinnih mnozhin ancestor v v displaystyle ancestor v v Yak zavzhdi v obhodi u glibinu perebirayemo usi vihidni rebra v to displaystyle v to Dlya kozhnogo takogo to displaystyle to zapuskayemo obhid u glibinu iz ciyeyi vershini a potim dodayemo cyu vershinu razom z yiyi pidderevom v klas vershini v displaystyle v Ce realizuyetsya operaciyami strukturi danih sistema neperetinnih mnozhin prisvoyuvannyam ancestor v displaystyle ancestor v dlya predstavnika mnozhini tak yak pislya ob yednannya predstavnik klasu mig zminitisya Pislya obrobki vsih reber mi perebirayemo vsi zapiti vidu v u displaystyle v u i yaksho vershina u displaystyle u bula poznachena yak vidvidana obhodom u glibinu to vidpoviddyu na cej zapit bude vershina LCA v u ancestor FindSet u displaystyle LCA v u ancestor FindSet u Ochevidno sho dlya kozhnogo zapitu cya umova sho odna vershina zapitu obroblyuyetsya obhodom u glibinu a druga bula vidvidana ranishe vipovnitsya rivno odin raz Psevdokod Psevdokod nizhche viznachaye najmenshij spilnij predok dlya kozhnoyi pari iz P displaystyle P zadano korin dereva u yakomu diti vuzla n displaystyle n zberigayutsya u mnozhini n children displaystyle n children Dlya cogo algoritmu mnozhina P displaystyle P povinna buti vkazana zazdalegid V proceduri vikoristovuyutsya MakeSet Find ta Union funkciyi sistemi neperetinnih mnozhin MakeSet u displaystyle MakeSet u rozmishuye element u displaystyle u v novu mnozhinu sho skladayetsya z odnogo nogo Find u displaystyle Find u povertaye predstavnika mnozhini u yakij mistitsya u displaystyle u Union u v displaystyle Union u v stvoryuye novu mnozhinu yaka ye ob yednannyam mnozhin yaki mistyat u displaystyle u i v displaystyle v function TarjanOLCA u is MakeSet u u ancestor u for each v in u children do TarjanOLCA v Union u v Find u ancestor u u color black for each v such that u v in P do if v color black then print Tarjan s Lowest Common Ancestor of u and v is Find v ancestor Nizhche navedeno optimizovani versiyi funkcij MakeSet Union i Find vikoristano evristiku stisnennya shlyahu ta evristiku ob yednannya za rangom v navedenomu nizhche psevdokodi rangovu evristiku realizovano na osnovi glibini derev function MakeSet x is x parent x x rank 1 function Union x y is xRoot Find x yRoot Find y if xRoot rank gt yRoot rank then yRoot parent xRoot else if xRoot rank lt yRoot rank then xRoot parent yRoot else if xRoot rank yRoot rank then yRoot parent xRoot xRoot rank xRoot rank 1 function Find x is if x parent x then x parent Find x parent return x parent Priklad realizaciyi movoyu S include lt iostream gt include lt vector gt using namespace std const int N 100001 N maksimalna kilkist vershin u derevi vector lt int gt g N q N int ancestor N parent N r N bool visited N void MakeSet int x parent x x r x 1 int FindSet int x if x parent x return x return parent x FindSet parent x void Union int x int y int xRoot FindSet x int yRoot FindSet y if r xRoot lt r yRoot swap xRoot yRoot parent yRoot xRoot r xRoot r yRoot void TarjanLCA int v int p MakeSet v ancestor v v for int i 0 i lt g v size i if g v i p TarjanLCA g v i v Union g v i v ancestor FindSet v v visited v true for int i 0 i lt q v size i if visited q v i cout lt lt Tarjan s Lowest Common Ancestor of lt lt v lt lt and lt lt q v i lt lt is lt lt ancestor FindSet q v i lt lt n int main Tut zchituyemo strukturu grafu ta zapiti zvidki nebud napriklad z fajlu TarjanLCA 1 1 vvazhayemo sho korenem dereva ye vershina pid nomerom 1 Ocinka skladnosti algoritmu Ocinka skladnosti algoritmu skladayetsya iz dekilkoh chastin Obhid u glibinu vikonuyetsya za O n displaystyle O n Operaciyi po ob yednannyu mnozhin yaki v sumi pracyuyut za O na n displaystyle O n alpha n de a n displaystyle alpha n obernena funkciya Akermana yaka zrostaye duzhe povilno nastilki povilno sho dlya vsih rozumnih obmezhen vona ne perevershuye 4 priblizno dlya n lt 10600 displaystyle n lt 10 600 Same tomu pro asimptotiku roboti sistemi neperetinnih mnozhin dorechno govoriti majzhe konstantnij chas roboti O n displaystyle O n Kozhnij zapit bude obroblenij rivno odin raz tomu mozhna vvazhati sho vsi zapiti obroblyayutsya sumarno za O m displaystyle O m Dlya kozhnogo zapitu perevirka umovi i viznachennya rezultatu dlya vsih rozumnih n displaystyle n vikonuyetsya za O 1 displaystyle O 1 Otzhe skladnist algoritmu O n m displaystyle O n m sho pri dostatno velikih m displaystyle m skladaye O 1 displaystyle O 1 na odin zapit Portal Programuvannya LiteraturaNaimenshij obshij predok Nahozhdenie za O 1 v offlajn algoritm Taryana ros Algoritm Taryana poiska LCA za O 1 v offlajn ros Tarjan s off line lowest common ancestors algorithm angl Gabow H N Tarjan R E 1983 A linear time algorithm for a special case of disjoint set union Proceedings of the 15th ACM Symposium on Theory of Computing STOC s 246 251 doi 10 1145 800061 808753 Tarjan R E 1979 Applications of path compression on balanced trees 26 4 690 715 doi 10 1145 322154 322161 Div takozhAlgoritm Tar yana Teoriya grafiv Derevo teoriya grafiv