Algoritmo di Tarjan del più basso antenato comune offline
{{NN|informatica|aprile 2022}}

In [[informatica]], l''''algoritmo di Tarjan del più basso antenato comune offline''' è un [[algoritmo]] per il calcolo del [[più basso antenato comune]] per una coppia di nodi in un albero, basata sulla struttura dati [[Mfset|union-find]]. Il più basso antenato comune di due nodi ''d'' ed ''e'' in un [[Albero (grafo)|albero]] ''T'' è il nodo ''g'' antenato sia di ''d'' che di ''e'' che possiede la profondità maggiore in ''T''. L'algoritmo prende il nome da [[Robert Tarjan]], che sviluppò la tecnica nel 1979. Quello di Tarjan è un algoritmo offline; ovvero, a differenza degli altri algoritmi del più basso antenato comune, richiede di specificare in anticipo tutte le coppie di nodi per cui si vuole individuare il più basso antenato comune. La versione più semplice dell'algoritmo utilizza la struttura dati [[Mfset|union-find]] che, a differenza delle strutture dati usate in altri algoritmi per il più basso antenato comune, può richiedere più di tempo costante per ogni operazione quando il numero delle paia di nodi ha un ordine di grandezza simile a quello dei nodi. Una modifica successiva di Gaboow e Tarjan velocizza l'algoritmo ad un [[Complessità temporale#Tempo lineare|tempo lineare]].

== Pseudocodice ==
Il seguente pseudocodice determina il più basso antenato comune di ciascuna coppia in ''P'', data la radice ''r'' di un albero nel quale i figli del nodo ''n'' sono nel set ''n.children''. Per questo algoritmo offline, il set ''P'' deve essere specificato in anticipo. Utilizza le funzioni ''MakeSet'', ''Find'' e ''Union'' di una [[Mfset|disjoint-set forest]]. ''MakeSet(u)'' rimuove ''u'' da un [[singoletto|insieme singoletto]], ''Find(u)'' mostra i rappresentanti standard dell'insieme contenente ''u'', e ''Union(u,v)'' unisce l'insieme contenente ''u'' con quello contenente ''v''. TarjanOLCA(''r'') è chiamato inizialmente sulla radice ''r''.
  '''function''' TarjanOLCA(u)
      MakeSet(u);
      u.ancestor := u;
      '''for each''' v '''in''' u.children '''do'''
          TarjanOLCA(v);
          Union(u,v);
          Find(u).ancestor := u;
      u.color := black;
      '''for each''' v '''such that''' {u,v} '''in''' P '''do'''
          '''if''' v.color == black
              print "Tarjan's Lowest Common Ancestor of " + u +
                    " and " + v + " is " + Find(v).ancestor + ".";
Ciascun nodo inizialmente è bianco, e viene colorato di nero dopo che esso e tutti i suoi figli sono stati visitati. Il più basso antenato comune ''{u,v}'' è disponibile come ''Find(v).ancestor'' immediatamente (e solo immediatamente) dopo che ''u'' è stato colorato di nero, a patto che ''v'' sia già nero. Altrimenti, sarà disponibile successivamente con ''Find(u).ancestor'', subito dopo che ''v'' è stato colorato di nero.

Qui di seguito sono mostrate delle versioni ottimizzate di ''MakeSet'', ''Find'', and ''Union'' per una [[Mfset|disjoint-set forest]]:
  '''function''' MakeSet(x)
      x.parent := x
      x.rank   := 1
  
  '''function''' 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.rank == yRoot.rank
          yRoot.parent := xRoot
          xRoot.rank := xRoot.rank + 1
   
  '''function''' Find(x)
      '''if''' x.parent != x
         x.parent := Find(x.parent)
      '''return''' x.parent

== Bibliografia ==
* {{Cita pubblicazione|cognome1=Gabow|nome1=H. N.|cognome2=Tarjan|nome2=R. E.|wkautore2=Robert Tarjan|contributo=A linear-time algorithm for a special case of disjoint set union|titolo=Proceedings of the 15th ACM Symposium on Theory of Computing (STOC)|anno=1983|pp=246–251|doi=10.1145/800061.808753}}
* {{Cita pubblicazione|cognome=Tarjan|wkautore=Robert Tarjan|titolo=Applications of path compression on balanced trees|rivista=[[Journal of the ACM]]|volume=26|numero=4|anno=1979|pp=690–715|doi=10.1145/322154.322161|nome=R. E.}}

{{Portale|Informatica}}
[[Categoria:Algoritmi sui grafi|Tarjan]]