Algoritmo per trovare il percorso in un albero non indirizzato

Question

Supponiamo che venga fornito un albero non orientato e che sia necessario trovare un percorso (l'unico percorso) tra due nodi.

Qual è il miglior algoritmo per farlo. Probabilmente potrei usare l'algoritmo di Dijkstra ma probabilmente c'è qualcosa di meglio per gli alberi.

C++ esempio potrebbe essere utile ma non necessario

si

Answer 1

Supponendo di avere

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

allora cosa si potrebbe fare è attraversare tutto l'albero a partire dalle radici mantenere l'intera catena durante l'attraversamento. Se trovi per es. Node1 quindi si salva la catena di corrente, se trovate node2 allora si controlla l'incrocio ... nel codice (il fitness):

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

Supponendo che ogni nodo ha un puntatore al suo genitore Grazie, poi semplicemente back-traccia l'albero verso la radice di ogni inizio nodo. Alla fine, i due percorsi devono intersecarsi. Il test per l'intersezione potrebbe essere semplice come mantenere un std::map di indirizzi di nodo.

UPDATE

Come hai aggiornato la tua domanda per specificare non orientati alberi, allora quanto sopra non è valida. Un semplice approccio è semplicemente quello di eseguire una traversata in profondità a partire dal nodo n. 1, alla fine si arriva al nodo n. 2. Questo è O (n) nella dimensione dell'albero. Non sono sicuro che ci sarà un approccio più veloce di quello, assumendo un albero completamente generale.

Answer 3

Larghezza-prima ricerca e profondità prima ricerca sono più efficaci poi Dijkstra di algoritmo.