Algorytm Tarjana znajdowania najniższego wspólnego przodka

Algorytm offline Tarjana znajdowania najniższego wspólnego przodka – algorytm obliczający najniższego wspólnego przodka dla pary węzłów w drzewie, bazujący na strukturze zbiorów rozłącznych.

Najniższym wspólnym przodkiem dwóch wierzchołków d oraz e w ukorzenionym drzewie T jest taki rodzic wierzchołków d oraz e, którego poziom w drzewie T jest największy. Algorytm nosi nazwę Roberta Tarjana, który wymyślił tę technikę w 1979 roku. Algorytm Tarjana zaliczany jest do klasy algorytmów offline, co oznacza, że w przeciwieństwie do innych algorytmów wyznaczania przodka, wymaga podania przed rozpoczęciem działania wszystkich par wierzchołków dla których będzie obliczany najniższy wspólny przodek.

Najprostsza wersja algorytmu używająca struktury "find union", w przeciwieństwie do innych algorytmów wyszukiwania wspólnego przodka może nie działać w stałym czasie dla każdej operacji, gdy liczba par wierzchołków jest bliska liczbie wierzchołków w drzewie. Ostatnie poprawki^[1] przyspieszają czas działania algorytmu do liniowego.

Pseudokod

Poniższy pseudokod wyznacza najniższego wspólnego przodka każdej pary należącej do P. Korzeń drzewa podany jest w zmiennej r, natomiast następniki wierzchołka n znajdują się w zbiorze n.children. Dla poniższego algorytmu offline zbiór P musi być zadany przed rozpoczęciem działania algorytmu. W procedurze używane są procedury MakeSet, Find oraz Union ze zbiorów rozłącznych. MakeSet(u) tworzy singelton z u, Find(u) zwraca reprezentanta zbioru do którego należy u, Union(u,v) łączy zbiory zawierające wierzchołki u oraz v.

TarjanOLCA(r) jest na początku wywoływany z parametrem równych korzeniowi r.

 funkcja TarjanOLCA(u)
     MakeSet(u)
     u.ancestor := u
     dla każdego v należącego do u.children wykonaj
         TarjanOLCA(v)
         Union(u,v)
         Find(u).ancestor := u
     u.color := black;
     dla każdego v takiego, że {u,v} należy do P wykonaj
         if v.colour == black
             zwróć wynik: Find(v).ancestor

Po inicjalizacji każdy wierzchołek jest w kolorze białym i jest kolorowany na czarno w momencie gdy wszystkie jego dzieci zostaną odwiedzone. Najniższy wspólny przodek pary {u,v} może zostać wyznaczony wywołaniem funkcji Find(v).ancestor natychmiast (i tylko wtedy) gdy wierzchołek u jest kolorowany na czarno, a v już został pokolorowany na czarno. W przeciwnym wypadku, będzie dostępny później jako Find(u).ancestor, w momencie pokolorowania v na czarno.

Poniżej znajduje się zoptymalizowana wersja funkcji MakeSet, Find, and Union działających na zbiorach rozłącznych.

 funkcja MakeSet(x)
     x.parent := x
     x.rank   := 0
 
 funkcja Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     if xRoot.rank > yRoot.rank
         yRoot.parent := xRoot
     else if xRoot.rank < yRoot.rank
         xRoot.parent := yRoot
     else if xRoot != yRoot
         yRoot.parent := xRoot
         xRoot.rank := xRoot.rank + 1
  
 funkcja Find(x)
     if x.parent == x
        return x
     else
        x.parent := Find(x.parent)
        return x.parent

Przypisy

↑ H.N. Gabow, R.E. Tarjan A linear-time algorithm for a special case of disjoint set union

Bibliografia

H. N. Gabow, R. E. Tarjan. 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, 1983. DOI: 10.1145/800061.808753. .

Tarjan. Applications of path compression on balanced trees. „Journal of the ACM”. 4 (26), s. 690–715, 1979. DOI: 10.1145/322154.322161. .

[1] H.N. Gabow, R.E. Tarjan A linear-time algorithm for a special case of disjoint set union

[1]