Algorytm najniższego wspólnego przodka Tarjana offline

Nie mylić z algorytmem silnie połączonych komponentów Tarjana .

W informatyce algorytm Tarjana dotyczący najniższych wspólnych przodków w trybie offline jest algorytmem obliczania najniższych wspólnych przodków dla par węzłów w drzewie, w oparciu o strukturę danych znajdowania związków . Najniższy wspólny przodek dwóch węzłów d i e w zakorzenionym drzewie T to węzeł g , który jest przodkiem obu wierzchołków d i e i który ma największą głębokość w T . Nosi imię Robert Tarjan , który odkrył tę technikę w 1979 roku. Algorytm Tarjana jest algorytmem offline; to znaczy, w przeciwieństwie do innych algorytmów najniższego wspólnego przodka, wymaga wcześniejszego określenia wszystkich par węzłów, dla których pożądany jest najniższy wspólny przodek. Najprostsza wersja algorytmu wykorzystuje strukturę danych typu Union-Find, która w przeciwieństwie do innych struktur danych o najniższym wspólnym przodku może zająć więcej niż stały czas na operację, gdy liczba par węzłów jest podobna pod względem wielkości do liczby węzłów. Późniejsze udoskonalenie Gabowa i Tarjana (1983) przyspiesza algorytm do czasu liniowego .

Pseudo kod

Poniższy pseudokod określa najniższego wspólnego przodka każdej pary w P , biorąc pod uwagę korzeń r drzewa, w którym dzieci węzła n należą do zbioru n.dzieci . Dla tego algorytmu offline zestaw P musi być określony z góry. Wykorzystuje funkcje MakeSet , Find i Union rozłącznego lasu . MakeSet(u) usuwa u do zbioru pojedynczego, Find(u) zwraca standardowego przedstawiciela zbioru zawierającego u , a Union(u,v) łączy zbiór zawierający u ze zbiorem zawierającym v . TarjanOLCA( r ) jest najpierw wywoływana w katalogu głównym r .

         funkcja  TarjanOLCA(u)  to  MakeSet(u) u.ancestor := u  dla każdego  v  in  u.children  do  TarjanOLCA(v) Union(u, v) Find(u).ancestor := u u.color := black  for każdy  v  taki, że  {u, v}  w  P  robi  , jeśli  v.kolor == czarny  , a następnie  wypisuje „Najniższy wspólny przodek Tarjana z „ + u + ” i „ + v + ” to „ + Znajdź (v). przodek + ”. " 

Każdy węzeł jest początkowo biały, a po odwiedzeniu go i wszystkich jego elementów podrzędnych jest kolorowany na czarno.

Dla każdej pary węzłów {u,v} do zbadania:

• Kiedy v jest już czarne (tj. gdy v występuje przed u w przechodzeniu przez drzewo po zamówieniu): Po tym, jak u jest koloru czarnego, najniższy wspólny przodek tej pary jest dostępny jako Find(v).ancestor , ale tylko wtedy, gdy LCA u i v nie jest w kolorze czarnym.
• W przeciwnym razie: Gdy v zostanie pokolorowane na czarno, LCA będzie dostępne jako Find(u).ancestor , podczas gdy LCA nie zostanie pokolorowane na czarno.

Dla porównania, oto zoptymalizowane wersje MakeSet , Find i Union dla rozłącznego lasu :

     funkcja  MakeSet(x)  to  x.parent := x x.rank := 1  funkcja  Suma(x, y)  to  xRoot := Znajdź(x) yRoot := Znajdź(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  funkcja  Znajdź (x)  jest  jeśli  x.parent != x  następnie  x.parent := Znajdź(x.parent)  return  x.parent 

• Gabow, HN ; Tarjan, RE (1983), „Algorytm czasu liniowego dla szczególnego przypadku rozłącznej unii zbiorów”, Proceedings of the 15th ACM Symposium on Theory of Computing (STOC) , s. 246–251, doi : 10.1145 / 800061.808753 .

• Tarjan, RE (1979), „Zastosowania kompresji ścieżki na zrównoważonych drzewach”, Journal of the ACM , 26 (4): 690–715, doi : 10.1145/322154.322161 .