Puede resolver este problema utilizando dos enfoques:>
- Usando BFS -> Suponga que tiene que encontrar la distancia entre el nodo A y el nodo B en un árbol. Simplemente puede ejecutar BFS en B y mantener un recuento del número de niveles que atravesó para llegar a A. Complejidad de tiempo: O (n) donde n es el número de vértices.
- Usando el ancestro común más bajo -> Ahora este enfoque requiere que viaje hacia arriba en un nivel desde el nodo A y el nodo B hasta obtener un ancestro común. (Siempre tendrá un ancestro común para cualquiera de los dos nodos. La raíz definitivamente sería un ancestro común de cualquiera de los 2 nodos). Aquí estamos hablando del más bajo entre los ancestros comunes en el árbol. Así es como los encuentras:
- Realice un recorrido BFS desde la raíz y asigne información de nivel y principal para cada nodo. (Puede mantener el padre de la raíz como NULL)
- Una vez que haya sido consultado con los dos nodos, obtenga los niveles de ellos.
- Ahora encuentre el que tenga un nivel más alto. Digamos que el nodo A, tiene el nivel más alto entre los dos. Avanza en el nivel superior desde A. (¿Cómo? Al usar el padre de A, subirás un nivel). Sigue subiendo un nivel hasta que te vuelvas igual al nivel de B. Deje que este nodo sea A ‘ .
- Siga viajando un nivel hacia arriba desde ambos nodos (Nodo B y Nodo A ‘ ) hasta llegar a un nodo común. Este nodo es el ancestro común más bajo.
- Mantenga un recuento de la distancia que atravesó desde el nodo A y el nodo B para llegar al ancestro común más bajo. Agrega los dos. Ahora tienes la distancia entre A y B.
- Complejidad de tiempo -> O (altura), en un promedio O (logn) para cada consulta. Tenga en cuenta la complejidad temporal de BFS al comienzo de este método. Tiene que hacerse solo una vez y no para cada consulta.
Entonces, para q consultas. El enfoque 1 da la complejidad temporal de O (qn) en promedio. Pero, el Enfoque 2 da O (n + qlogn) en promedio. Por lo tanto, usar el Enfoque 2 sería el método más eficiente.
Para 1000 consultas y 10,000 nodos. El tiempo de ejecución del enfoque 1 sería aproximadamente 100 veces más que el tiempo de ejecución del enfoque 2.
- ¿Todos los NP-HARD que son decidibles también son NP-Complete?
- ¿Cuántas matemáticas necesito para aprender sobre estructuras de datos y algoritmos?
- ¿Cuáles son los diferentes usos de la estructura de datos Trie?
- Cómo encontrar un segmento en una matriz con un número máximo de elementos con suma S
- Cómo hacer un diagrama de flujo y un algoritmo para convertir números binarios a decimales
Y el enfoque 2 debería pasar bien dentro de 0.1 segundos en un compilador contemporáneo. Buena suerte !!
