アルゴリズムが無向木のパスを見つける

Question

無向ツリーが与えられ、2つのノード間のパス（唯一のパス）を見つける必要があるとします。

私はおそらくダイクストラのアルゴリズムを使用することができますが、おそらくツリーの方が良いでしょう。

C++の例では、必要に役立つことはありませんでしょう

は

Answer 1

仮にあなたが持っている

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

その後、何横断中に、チェーン全体を維持するルートで始まるツリー全体をトラバースされて行うことができます。たとえば、

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

は、単にバックトラック各開始ノードからルートへのツリーを、各ノードがその親へのポインタを持っていると仮定していただきありがとうございます。最終的には、2つのパスが交差する必要があります。交差点のテストは、ノードアドレスのstd::mapを維持するのと同じくらい簡単です。

UPDATEあなたは無向樹木を指定するには、あなたの質問を更新してきたように

は、その後、上記有効ではありません。簡単なアプローチは、ノード＃1で深さ優先のトラバーサルを開始するだけです。結果的にノード＃2に到達します。これは、木のサイズでO（n）です。私は完全に一般的なツリーを仮定して、それより速いアプローチになるだろうと確信していません。

Answer 3

幅優先探索と深さ優先探索あり、その後、より効果的なダイクストラ：ノード1は、その後、あなたはその後、ノード2を見つけた場合は、コード内交差点...（未テスト）をチェックし、現在のチェーンを保存しますアルゴリズム。