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

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

Отже, складність алгоритму , що при достатньо великих складає на один запит.

Література

Див. також

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