Cómo encontrar la ruta de longitud máxima en un árbol binario T

El camino de longitud máxima en un árbol también se conoce como su diámetro .

Uno de mis algoritmos favoritos le permite encontrar el diámetro de un árbol general, binario o no, y es increíblemente simple y elegante. Tampoco tiene que preocuparse por la eficiencia, ya que se ejecuta en tiempo lineal [matemático] O (N) [/ matemático], ¡lo cual es óptimo!

¿Entonces, cómo funciona?

• Cómo verificar si un árbol no binario está equilibrado en altura
• ¿Cómo saben los codificadores cómo codificar e implementar un algoritmo instintivamente?
• ¿Cuándo deberíamos considerar el uso de algoritmos recursivos al escribir un programa? Discuta en términos de ventajas y desventajas.
• ¿Cuáles son las amplias variedades en programación dinámica que se preguntan con frecuencia en los concursos de codificación?
• ¿Qué algoritmo se usa para contar la cantidad de personas en un video?

1. Elija un nodo arbitrario [math] v [/ math] y arraigue el árbol en ese nodo.
2. Ejecute una búsqueda de profundidad primero desde [math] v [/ math], para encontrar el nodo [math] u [/ math] que tiene la mayor distancia desde la raíz.
3. Reroot el árbol en [math] u [/ math].
4. Ejecute otra búsqueda de profundidad primero desde [math] u [/ math], y nuevamente, encuentre el nodo [math] w [/ math] que está más alejado de [math] u [/ math].
5. La ruta [math] u [/ math] – [math] w [/ math] es un diámetro del árbol.

¡Eso es! Simple, eficiente y fácil de codificar. Ahora, espera, porque sé que probablemente eres escéptico. ¿Por qué es correcto este algoritmo? Una prueba se puede encontrar aquí.

Finalmente, aquí hay una implementación de muestra en C ++, que se lee en el árbol en formato de lista de borde de la entrada estándar:

#include
#include
usando el espacio de nombres estándar;

#define MAXN 100013
int N;
vector adj [MAXN];
int parent [MAXN];
int d [MAXN];

dfs nulo (int n, int p = -1) {
padre [n] = p;
d [n] = (n == p? 0: 1) + d [p];
para (int v: adj [n]) {
si (v! = p) {
dfs (v, n);
}
}
}

int main () {
cin >> N;
para (int i = 0; i <N – 1; i ++) {
int a, b;
cin >> a >> b;
una-; si-;
adj [a] .push_back (b);
adj [b] .push_back (a);
}

dfs (0, 0);

int f = 0;
para (int i = 0; i <N; i ++) {
if (d [i]> d [f]) ​​{
f = i;
}
}

d [f] = 0;
dfs (f, f);

para (int i = 0; i <N; i ++) {
if (d [i]> d [f]) ​​{
f = i;
}
}

cout << d [f] << endl;
devuelve 0;
}