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

Офлайновий алгоритм Тарджана для пошуку найменшого спільного предка — алгоритм для знаходження найменшого спільного предка пари вузлів у дереві. Він названий на честь Роберта Андре Тарджана, який відкрив цей алгоритм у 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. Journal of the ACM 26 (4): 690–715. doi:10.1145/322154.322161..

Див. також

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.