Офлайновий алгоритм Тарджана для пошуку найменшого спільного предка алгоритм для знаходження найменшого спільного предка

Офлайновий алгоритм Тарджана для пошуку найменшого спільного предка — алгоритм для знаходження найменшого спільного предка пари вузлів у дереві. Він названий на честь Роберта Андре Тарджана, який відкрив цей алгоритм у 1979 році. Алгоритм Тарджана не є алгоритмом реального часу, тобто, він вимагає, щоб усі пари вузлів, для яких потрібно знайти найменший спільний предок, були вказані заздалегідь.

Формальне визначення завдання

Дано дерево $G$ з $n$ вершинами і дано $m$ запитів виду ( ${a_{i}}$ , ${b_{i}}$ ), потрібно для кожного запиту ( ${a_{i}}$ , ${b_{i}}$ ) знайти найменшого спільного предка, тобто, таку вершину ${c_{i}}$ , яка найбільш віддалена від кореня дерева і при цьому є предком для обох вершин ${a_{i}}$ та ${b_{i}}$ .

Алгоритм

Опис

Основою для алгоритму є структура даних «система неперетинних множин», яка і була винайдена Тарджаном.

Алгоритм фактично являє собою обхід у глибину із кореня дерева, в процесі якого поступово знаходяться відповіді на запити. А саме, відповідь на запит знаходиться, коли обхід у глибину обробляє вершину $v$ , а вершина $u$ вже була відвідана, або навпаки.

Підвісимо наше дерево за будь-яку вершину, і запустимо обхід у глибину з неї. Нехай обхід дерева у глибину знаходиться в деякій вершині $v$ . Помістимо її в окремий клас в структурі неперетинних множин, $ancestor[v]=v$ . Як завжди, в обході у глибину, перебираємо усі вихідні ребра $(v,to)$ . Для кожного такого $to$ запускаємо обхід у глибину із цієї вершини, а потім додаємо цю вершину разом з її піддеревом в клас вершини $v$ . Це реалізується операціями структури даних «система неперетинних множин», присвоюванням $ancestor=v$ для представника множини (так як після об'єднання представник класу міг змінитися). Після обробки всіх ребер ми перебираємо всі запити виду $(v,u)$ , і якщо вершина $u$ була позначена як відвідана обходом у глибину, то відповіддю на цей запит буде вершина $LCA(v,u)=ancestor[FindSet(u)]$ . Очевидно, що для кожного запиту ця умова (що одна вершина запиту оброблюється обходом у глибину, а друга була відвідана раніше) виповниться рівно один раз.

Псевдокод

Псевдокод нижче визначає найменший спільний предок для кожної пари із $P$ , задано корінь дерева у якому діти вузла $n$ зберігаються у множині $n.children$ . Для цього алгоритму, множина $P$ повинна бути вказана заздалегідь. В процедурі використовуються MakeSet, Find та Union функції системи неперетинних множин. $MakeSet(u)$ розміщує елемент $u$ в нову множину, що складається з одного нього, $Find(u)$ повертає представника множини, у якій міститься $u$ , $Union(u,v)$ створює нову множину, яка є об'єднанням множин, які містять $u$ і $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 + "."

Нижче наведено оптимізовані версії функцій 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  }

Оцінка складності алгоритму

Оцінка складності алгоритму складається із декількох частин.

Обхід у глибину виконується за $O(n)$ .
Операції по об'єднанню множин, які в сумі працюють за $O(n\alpha (n))$ , де $\alpha (n)$ — обернена функція Акермана, яка зростає дуже повільно, настільки повільно, що для всіх розумних обмежень вона не перевершує 4 (приблизно для $n<=10^{600}$ ). Саме тому про асимптотику роботи системи неперетинних множин доречно говорити «майже константний час роботи» — $O(n)$ . Кожний запит буде оброблений рівно один раз, тому можна вважати, що всі запити обробляються сумарно за $O(m)$ .
Для кожного запиту перевірка умови і визначення результату для всіх розумних $n$ виконується за $O(1)$ .

Отже, складність алгоритму — $O(n+m)$ , що при достатньо великих $m$ складає $O(1)$ на один запит.

Література

Наименьший общий предок. Нахождение за 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.