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. .
