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

Офлайновий алгоритм Тарджана для пошуку найменшого спільного предка — алгоритм для знаходження найменшого спільного предка пари вузлів у дереві. Він названий на честь Роберта Андре Тарджана, який відкрив цей алгоритм у 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)$ .