Determina la distanza tra due nodi casuali in un albero

Question

Dato un albero generale, voglio la distanza tra due nodi v e w.

Wikipedia states the following:

Calcolo dei bassi antenati comuni può essere utile, per esempio, come parte di una procedura per determinare la distanza tra coppie di nodi di un albero: la distanza da v di w può essere calcolato come la distanza dalla radice a v, più la distanza dalla radice a w, meno il doppio della distanza dalla radice al loro più basso antenato comune.

Diciamo d(x) indica la distanza di nodo x dalla radice che abbiamo impostato a 1. d(x,y) indica la distanza tra due vertici x e . lca(x,y) indica il più basso antenato comune della coppia di vertici x e .

Così se abbiamo 4 e 8, lca(4,8) = 2 quindi, secondo la descrizione di cui sopra, d(4,8) = d(4) + d(8) - 2 * d(lca(4,8)) = 2 + 3 - 2 * 1 = 3. Ottimo, ha funzionato!

Tuttavia, nel caso indicato in precedenza sembra sicuro per la coppia vertice (8,3) (lca(8,3) = 2) d(8,3) = d(8) + d(3) - 2 * d(2) = 3 + 1 - 2 * 1 = 2. Ciò non è corretto tuttavia, la distanza d(8,3) = 4 come si può vedere sul grafico. L'algoritmo sembra fallire per tutto ciò che attraversa la radice definita.

Cosa mi manca?

Answer 1

Si è perso il numero lca(8,3) = 1 e non = 2. Da qui il d(1) == 0 che lo rende:

d(8,3) = d(8) + d(3) - 2 * d(1) = 3 + 1 - 2 * 0 = 4 

Answer 2

Per la 2 nodo appropriato, vale a dire l'uno uno a destra, d(lca(8,2)) == 0, non 1 come lo avete nel vostro derivazione. La distanza dalla radice - che in questo caso è lca - a se stessa è zero. Così

d(8,2) = d(8) + d(2) - 2 * d(lca(8,2)) = 3 + 1 - 2 * 0 = 4 

Il fatto di avere due nodi etichettati 2 è probabilmente cose confuse.

Edit: Il post è stato modificato in modo tale che un nodo originariamente etichettato 2 è ora contrassegnata 3. In questo caso, la derivazione è ora corretta ma la dichiarazione

the distance d(8,2) = 4 as can be seen on the graph 

è corretto, d (8 , 2) = 2.