In der Informatik Tarjan offline ist kleinster Algorithmus der gemeinsamen Ahnen (genauer sollte am wenigsten wirklich am niedrigsten sein), ein Algorithmus, um niedrigste gemeinsame Ahnen für Paare von Knoten in einem Baum zu schätzen, gestützt auf der Vereinigung - finden Datenstruktur. Der niedrigste gemeinsame Ahne von zwei Knoten d und e in einem eingewurzelten Baum T ist der Knoten g, der ein Vorfahr sowohl von d als auch von e ist und das die größte Tiefe in T hat. Es wird nach Robert Tarjan genannt, der die Technik 1979 entdeckt hat. Der Algorithmus von Tarjan ist off-line; d. h. verschieden von anderen niedrigsten Algorithmen des gemeinsamen Ahnen verlangt es, dass alle Paare von Knoten, für die der niedrigste gemeinsame Ahne gewünscht wird, im Voraus angegeben werden müssen. Die einfachste Version des Algorithmus verwendet die Vereinigung - finden Datenstruktur, die verschieden von anderen niedrigsten Datenstrukturen des gemeinsamen Ahnen mehr nehmen kann als unveränderliche Zeit pro Operation, wenn die Zahl von Paaren von Knoten im Umfang der Zahl von Knoten ähnlich ist. Eine spätere Verbesserung durch Geschwindigkeiten der Algorithmus bis zur geradlinigen Zeit.

Pseudocode

Der Pseudocode bestimmt unten den niedrigsten gemeinsamen Ahnen jedes Paares in P, in Anbetracht der Wurzel r von einem Baum, in dem die Kinder des Knotens n im Satz n.children sind. Für diesen Off-Linealgorithmus muss der Satz P im Voraus angegeben werden. Es verwendet MakeSet, Finden Sie und Vereinigungsfunktionen eines Waldes des zusammenhanglosen Satzes. MakeSet (u) entfernt u zu einem Singleton-Satz, Finden Sie (u)-Umsatz den Standardvertreter des Satzes, der u enthält, und Vereinigung (u, v) verschmilzt den Satz, der u mit dem Satz enthält, der v enthält.

TarjanOLCA(r) wird zuerst auf der Wurzel r genannt.

fungieren Sie TarjanOLCA (u)

MakeSet (u);

u.ancestor: = u;

weil jeder v in u.children tut

TarjanOLCA (v);

Vereinigung (u, v);

Finden Sie (u).ancestor: = u;

u.colour: = schwarz;

für jeden solchen v, die {u, v} in P tun

wenn v.colour == schwarzer

drucken Sie "Kleinsten Gemeinsamen Ahnen von Tarjan" + u +

"und" + v + "ist" + Finden (v).ancestor +".";

Jeder Knoten ist am Anfang weiß, und wird schwarz danach gefärbt, und alle seine Kinder sind besucht worden. Der niedrigste gemeinsame Ahne des Paares {u, v} ist verfügbar, wie (v) Finden, wird.ancestor sofort (und nur sofort) danach u schwarz gefärbt, zur Verfügung gestellter v ist bereits schwarz. Sonst wird es später verfügbar sein, wie (u).ancestor sofort Finden, nachdem v schwarz gefärbt wird.

Für die Verweisung, hier sind optimierte Versionen von MakeSet, Finden und Vereinigung für einen Wald des zusammenhanglosen Satzes:

fungieren Sie MakeSet (x)

x.parent: = x

x.rank: = 0

fungieren Sie Vereinigung (x, y)

xRoot: = Finden (x)

yRoot: = Finden (y)

wenn xRoot.rank> yRoot.rank

yRoot.parent: = xRoot

sonst, wenn xRoot.rank