Đường dẫn tìm kiếm thuật toán trong một cây không bị khai thác

Question

Giả sử tôi được cung cấp một cây không bị gạch và tôi cần tìm một đường dẫn (đường dẫn duy nhất) giữa hai nút.

Thuật toán tốt nhất để làm điều đó. Tôi có thể sử dụng thuật toán Dijkstra nhưng có thể có điều gì đó tốt hơn cho cây cối.

C++ ví dụ sẽ là hữu ích nhưng không cần thiết

Cảm ơn bạn

Answer 1

Giả sử bạn có

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

sau đó có thể làm gì được đi qua toàn bộ cây bắt đầu từ gốc giữ toàn bộ chuỗi trong traversal. Nếu bạn thấy, ví dụ: node1 sau đó bạn lưu các chuỗi hiện tại, nếu bạn thấy node2 sau đó bạn kiểm tra sự giao nhau ... trong mã (chưa được kiểm tra): tìm kiếm tìm kiếm và chiều sâu-đầu tiên

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

Giả sử mỗi nút có một con trỏ đến mẹ của nó, sau đó chỉ cần back-theo dõi lên cây về phía gốc từ mỗi nút bắt đầu. Cuối cùng, hai đường phải giao nhau. Việc kiểm tra giao lộ có thể đơn giản như việc duy trì một địa chỉ nút là std::map.

CẬP NHẬT

Như bạn đã cập nhật câu hỏi của bạn để xác định vô hướng cây, sau đó ở trên không có giá trị. Một cách tiếp cận đơn giản chỉ đơn giản là để thực hiện một traversal chiều sâu đầu tiên bắt đầu từ Node # 1, cuối cùng bạn sẽ nhấn nút # 2. Đây là O (n) với kích thước của cây. Tôi không chắc chắn sẽ có một cách tiếp cận nhanh hơn, giả sử một cây hoàn toàn chung chung.

Answer 3

Chiều rộng đầu tiên có hiệu quả hơn sau đó Dijkstra thuật toán.