Ścieżka odnajdywania algorytmu w nienazwanym drzewie

Question

Załóżmy, że dostałem nieukierunkowane drzewo i potrzebuję znaleźć ścieżkę (jedyną ścieżkę) między dwoma węzłami.

Jaki jest najlepszy algorytm do tego. Prawdopodobnie mógłbym użyć algorytmu Dijkstry, ale prawdopodobnie coś lepszego dla drzew.

C++ Przykładem może być pomocne, ale nie jest to konieczne

Dziękuję

Answer 1

Przypuśćmy masz

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

następnie co można zrobić przemierza całe drzewo zaczynając od korzenia utrzymując cały łańcuch podczas przechodzenia. Jeśli znajdziesz np. node1 następnie zapisać bieżący łańcuch, jeśli okaże node2 następnie sprawdzić na skrzyżowaniu ... w kodzie (NIETESTOWANY):

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

Zakładając, każdy węzeł ma wskaźnik do jego rodzica, a potem po prostu śledzić back-up drzewa w kierunku korzenia z każdym uruchomieniu węzła. W końcu obie ścieżki muszą się przecinać. Testowanie dla przecięcia może być tak proste, jak utrzymanie adresów węzłów.

UPDATE

Jak już zaktualizowane pytanie określić nieukierunkowane drzew, to powyższe nie jest ważna. Prostym podejściem jest po prostu wykonanie przejścia od początku do głębi, zaczynając od Węzła # 1, w końcu trafisz Węzeł nr 2. Jest to O (n) w rozmiarze drzewa. Nie jestem pewien, czy będzie szybsze podejście, zakładając zupełnie ogólne drzewo.

Answer 3

Szerokość pierwszego wyszukiwania i głębokość pierwszego wyszukiwania są bardziej skuteczne wtedy Dijkstry algorytm.