Back

ⓘ Тарјанов алгоритам за најниже заједничке претке




                                     

ⓘ Тарјанов алгоритам за најниже заједничке претке

У рачунарству, Тарјанов алгоритам за најниже заједничке претке је алгоритам који рачуна најниже заједничке претке за пар чворова у стаблу, заснован на структури података дисјунктни сет. Најниже заједнички предак два чвора д и е у кореном стаблу Т је чвор г који је предат и д и е и који има највећу дубини у Т. Алгоритам је назван по Роберту Тарјану, који је открио ову технику 1979. Тарјанов алгоритам је offline алгоритам; за разлику од осталих алгоритама који траже најнижег заједничког претка, овај алгоритам захтева да сви парови чворова за које се тражи најнижи заједничи предак морају бити наведени унапред. Најједноставнија верзија овог алгоритма користи структиру података дисјунктни сет, која за разлику од осталих структура података за најнижег заједничког претка може да траје више од константног времена по операцији када је број парова чворова сличан по величини броју чворова. Године 1983. Габов и Тарјан су успели да убрзају алгоритам до брзине која је еквивалентна субекспоненцијалном времену.

                                     

1. Псеудокод

Псеудокод испод одређује најнижег заједничког претка за сваки пар у P, ако је корен стабла r у којем се деца чвора n налазе у n.children. За овај offline алгоритам, сет P мора да буде наведен унапред.

function TarjanOLCAu MakeSetu; u.ancestor:= u; for each v in u.children do TarjanOLCAv; Unionu,v; Findu.ancestor:= u; u.colour:= black; for each v such that {u,v} in P do if v.colour == black print "Tarjans Lowest Common Ancestor of + u + and + v + is + Findv.ancestor + ".";

Сваки чвор је иницијално бео, и боји се црно пошто су он и сва његова директна деца посећени. Најнижи заједнички предак једног пара је одмах доступан и само одмах пошто су оба чвора обојена у црно. У супротном биће доступан касније одмах пошто је други чвор обојен у црно.

За даље, ево примера оптимизованих MakeSet, Find, and Union за један дисјунктни-сет структура података.

function MakeSetx x.parent:= x x.rank:= 0 function Unionx, y xRoot:= Findx yRoot:= Findy 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 function Findx if x.parent == x return x else x.parent:= Findx.parent return x.parent