Ruta de búsqueda de algoritmo en un árbol no dirigido

Question

Supongamos que se me ha asignado un árbol no dirigido y necesito encontrar una ruta (la única ruta) entre dos nodos.

Cuál es el mejor algoritmo para hacerlo. Probablemente podría usar un algoritmo de Dijkstra, pero probablemente haya algo mejor para los árboles.

ejemplo C++ sería útil pero no necesario

Gracias

Answer 1

Suponiendo que usted tiene

struct Node 
{ 
    std::vector<Node *> children; 
}; 

entonces lo que se podría hacer es recorrer todo el árbol a partir de las raíces de mantenimiento de toda la cadena durante el recorrido. Si encuentras p. nodo1 a continuación, guardar la cadena actual, si encuentra el nodo 2 y comprueba entonces para la intersección ... en el código (sin probar):

bool findPath(std::vector<Node *>& current_path, // back() is node being visited 
       Node *n1, Node *n2,    // interesting nodes 
       std::vector<Node *>& match,  // if not empty back() is n1/n2 
       std::vector<Node *>& result)  // where to store the result 
{ 
    if (current_path.back() == n1 || current_path.back() == n2) 
    { 
     // This is an interesting node... 
     if (match.size()) 
     { 
      // Now is easy: current_path/match are paths from root to n1/n2 
      ... 
      return true; 
     } 
     else 
     { 
      // This is the first interesting node found 
      match = current_path; 
     } 
    } 
    for (std::vector<Node *>::iterator i=current_path.back().children.begin(), 
             e=current_path.back().children.end(); 
     i != e; ++i) 
    { 
     current_path.push_back(*i); 
     if (findPath(current_path, n1, n2, match, result)) 
      return true; 
     current_path.pop_back(); // *i 
    } 
    return false; 
} 

Answer 2

Suponiendo que cada nodo tiene un puntero a su padre, a continuación, simplemente copia-pista hasta el árbol hacia la raíz de cada nodo de inicio. Eventualmente, los dos caminos deben cruzarse. La prueba de intersección podría ser tan simple como mantener un std::map de direcciones de nodo.

ACTUALIZACIÓN

Como ha informado su pregunta para especificar no dirigidos árboles, a continuación, lo anterior no es válido. Un enfoque simple es simplemente realizar un recorrido transversal en profundidad comenzando en el Nodo n. ° 1, con el tiempo llegarás al n. ° 2. Esto es O (n) en el tamaño del árbol. No estoy seguro de que vaya a haber un enfoque más rápido que eso, asumiendo un árbol completamente general.

Answer 3

primero en amplitud y profundidad de búsqueda-primera búsqueda son más eficaces después de Dijkstra algoritmo.