Trayectoria más larga en un árbol no dirigido con un solo recorrido

44

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 .vv
  • 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.v

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).

Emmy
fuente
2
Lo que buscas también se llama diámetro del árbol. (En los árboles, "la ruta más corta más larga" y la "ruta más larga" son lo mismo, ya que solo hay una ruta que conecta dos nodos).
Rafael

Respuestas:

22

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:vu1,,uk

  • El camino más largo en encuentra en uno de los subárboles T u 1 , ... , T u k .TvTu1,,Tuk
  • La ruta más larga en contiene v .Tvv

vH(k)+H(k1)+2k>1H(k)+1k=1H={h(Tui)i=1,,k}

En pseudocódigo, el algoritmo se ve así:

procedure longestPathLength(T : Tree) = helper(T)[2]

/* Recursive helper function that returns (h,p)
 * where h is the height of T and p the length
 * of the longest path of T (its diameter) */
procedure helper(T : Tree) : (int, int) = {
  if ( T.children.isEmpty ) {
    return (0,0)
  }
  else {
    // Calculate heights and longest path lengths of children
    recursive = T.children.map { c => helper(c) }
    heights = recursive.map { p => p[1] }
    paths = recursive.map { p => p[2] }

    // Find the two largest subtree heights
    height1 = heights.max
    if (heights.length == 1) {
      height2 = -1
    } else {
      height2 = (heights.remove(height1)).max
    }

    // Determine length of longest path (see above)        
    longest = max(paths.max, height1 + height2 + 2)

    return (height1 + 1, longest)
  }
}

  1. A(k)kA
Rafael
fuente
@JeffE Con ​​respecto al segundo comentario: De hecho, y esto se soluciona en la última fila: height1 + height2es la longitud de este camino. Si de hecho es el camino más largo, es elegido por max. 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.
Raphael
@JeffE Con ​​respecto al primer comentario, el cálculo de height2explícitamente se elimina height1de la consideración, entonces, ¿cómo puede elegir el mismo hijo dos veces? Eso, también, ha sido explicado en el texto introductorio.
Raphael
1
Aparentemente, hablamos diferentes dialectos de pseudocódigo, porque me cuesta entender el tuyo. Sería útil agregar una declaración explícita en inglés que longestPathHeight(T)devuelva un par (h,d), donde hes la altura Ty del diámetro de T. (¿Correcto?)
JeffE
@JeffE Derecha; Pensé que eso estaba claro por el código, dada la explicación, pero aparentemente mi extrapolación de "claro" para otros paradigmas de pseudocódigo fue insuficiente (el mío es escalaco, supongo). Perdón por la confusión, estoy aclarando el código (con suerte).
Raphael
8

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

  1. mentir completamente en el subárbol izquierdo o
  2. mentir completamente en el subárbol derecho o
  3. puede extenderse a través de la raíz

Lo que significa que el diámetro puede derivarse idealmente por

  1. el diámetro del árbol izquierdo o
  2. el diámetro del árbol derecho o
  3. la altura del subárbol izquierdo + la altura del subárbol derecho + 1 (1 para agregar el nodo raíz cuando el diámetro se extiende por el nodo raíz)

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:

  1. La altura de su hijo izquierdo,
  2. La altura de su hijo derecho y
  3. La distancia más lejana entre sus nodos de hoja.

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

  1. Inicialice todas las hojas con leftHeight y rightHeight como 1.
  2. Inicialice todas las hojas con maxDistance como 0, señalamos que si cualquiera de leftHeight o rightHeight es 1, hacemos maxDistance = 0
  3. Mueva hacia arriba de a uno por vez y calcule los valores para el padre inmediato. Sería fácil porque ahora conocemos estos valores para los niños.
  4. En un nodo dado,

    • asigne leftHeight como máximo de (leftHeight o rightHeight de su hijo izquierdo).
    • asigne el rightHeight como máximo de (leftHeight o rightHeight de su hijo derecho).
    • si alguno de estos valores (leftHeight o rightHeight) es 1, haga maxDistance como cero.
    • si ambos valores son mayores que cero, haga maxDistance como leftHeight + rightHeight - 1
  5. Mantenga maxDistance en una variable temporal y si en el paso 4 maxDistance es mayor que el valor actual de la variable, reemplácelo con el nuevo valor maxDistance.
  6. Al final del algoritmo, el valor en maxDistance es el diámetro.
dharam
fuente
1
¿Qué agrega esto a mi respuesta anterior, además de ser menos general (solo se trata de árboles binarios)?
Raphael
99
Esta respuesta es más legible y más fácil de entender en mi opinión (su pseudocódigo es muy confuso).
reggaeguitar
-3

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.

 int getDiam(int root, vector<vector<int>>& adj_list, int& height, vector<int>& path, vector<int>& diam) {
    visited[root] = true;
    int m1 = -1;
    int m2 = -1;
    int max_diam = -1;
    vector<int> best1 = vector<int>();
    vector<int> best2 = vector<int>();
    vector<int> diam_path = vector<int>();
    for(auto n : adj_list[root]) {
        if(!visited[n]) {
            visited[n] = true;
            int _height = 0;
            vector<int> path1;
            vector<int> path2;
            int _diam = getDiam(n, adj_list, _height, path1, path2);
            if(_diam > max_diam) {
                max_diam = _diam;
                diam_path = path2;
            }
            if(_height > m1) {
                m2 = m1;
                m1 = _height;
                best2 = best1;
                best1 = path1;
            }
            else if(_height > m2) {
                m2 = _height;
                best2 = path1;
            }
        }
    }

    height = m1 + 1;

    path.insert( path.end(), best1.begin(), best1.end() );
    path.push_back(root);

    if(m1 + m2 + 2 > max_diam) {
        diam = path;
        std::reverse(best2.begin(), best2.end());
        diam.insert( diam.end(), best2.begin(), best2.end() );
    }
    else{
        diam = diam_path;
    }


    return max(m1 + m2 + 2, max_diam);
}
Trevor Van Loon
fuente
2
Este no es un sitio de codificación. Desalentamos las respuestas que consisten principalmente en un bloque de código. En cambio, queremos respuestas que expliquen las ideas detrás del algoritmo y proporcionen un seudocódigo conciso (que no requiera el conocimiento de ningún lenguaje de programación en particular para entenderlo). ¿Cómo calcula la ruta más larga que comienza en un nodo particular en el árbol? (especialmente porque el camino más largo puede comenzar subiendo el árbol DFS, es decir, de regreso hacia la raíz)
DW