Existe este algoritmo estándar para encontrar la ruta más larga en árboles no dirigidos utilizando dos búsquedas de profundidad:
- Inicie DFS desde un vértice aleatorio y encuentre el vértice más alejado de él; di que es v ′ .
- Ahora comience un DFS desde para encontrar el vértice más alejado de él. Esta ruta es la ruta más larga en el gráfico.
La pregunta es, ¿se puede hacer esto de manera más eficiente? ¿Podemos hacerlo con un solo DFS o BFS?
(Esto puede describirse de manera equivalente como el problema de calcular el diámetro de un árbol no dirigido).
algorithms
graphs
trees
Emmy
fuente
fuente
Respuestas:
Realizamos una búsqueda profunda en orden posterior y agregamos resultados en el camino, es decir, resolvemos el problema de forma recursiva.
Para cada nodo con hijos u 1 , ... , u k (en el árbol de búsqueda) hay dos casos:v u1,…,uk
En pseudocódigo, el algoritmo se ve así:
fuente
height1 + height2
es la longitud de este camino. Si de hecho es el camino más largo, es elegido pormax
. También se explica en el texto anterior, así que no veo tu problema. Seguramente tienes que recurrir para descubrir si es realmente el camino más largo, e incluso si no es así (no es correcto) la recurrencia.height2
explícitamente se eliminaheight1
de la consideración, entonces, ¿cómo puede elegir el mismo hijo dos veces? Eso, también, ha sido explicado en el texto introductorio.longestPathHeight(T)
devuelva un par(h,d)
, dondeh
es la alturaT
yd
el diámetro deT
. (¿Correcto?)Esto se puede resolver de una mejor manera. Además, podemos reducir la complejidad del tiempo a O (n) con una ligera modificación en la estructura de datos y utilizando un enfoque iterativo. Para un análisis detallado y múltiples formas de resolver este problema con varias estructuras de datos.
Aquí hay un resumen de lo que quiero explicar en una publicación mía del blog :
Enfoque recursivo: diámetro del árbol Otra forma de abordar este problema es la siguiente. Como mencionamos anteriormente, el diámetro puede
Lo que significa que el diámetro puede derivarse idealmente por
Y sabemos que el diámetro es el camino más largo, por lo que tomamos el máximo de 1 y 2 en caso de que se encuentre en cualquiera de los lados o tome 3 si se extiende a través de la raíz.
Enfoque iterativo: diámetro del árbol
Tenemos un árbol, necesitamos una metainformación con cada nodo para que cada nodo sepa lo siguiente:
Una vez que cada nodo tiene esta información, necesitamos una variable temporal para realizar un seguimiento de la ruta máxima. Cuando termina el algoritmo, tenemos el valor del diámetro en la variable temporal.
Ahora, necesitamos resolver este problema en un enfoque ascendente, porque no tenemos idea de los tres valores para la raíz. Pero conocemos estos valores para las hojas.
Pasos para resolver
En un nodo dado,
fuente
A continuación se muestra un código que devuelve una ruta de diámetro utilizando solo un recorrido transversal DFS. Requiere espacio adicional para realizar un seguimiento del mejor diámetro visto hasta ahora, así como el camino más largo que comienza en un nodo particular en el árbol. Este es un enfoque de programación dinámica basado en el hecho de que una ruta de diámetro más largo no incluye la raíz o es una combinación de las dos rutas más largas de los vecinos de la raíz. Por lo tanto, necesitamos dos vectores para realizar un seguimiento de esta información.
fuente