Алгоритм поиска пути в неориентированном дереве

Question

Предположим, мне дано неориентированное дерево, и мне нужно найти путь (единственный путь) между двумя узлами.

Какой лучший алгоритм для этого. Возможно, я мог бы использовать алгоритм Дейкстры, но, возможно, что-то лучше для деревьев.

C ++ пример был бы полезен, но не обязателен

Спасибо

Answer 1

Предполагая, что у каждого узла есть указатель на своего родителя, просто верните дерево в обратном направлении к корню от каждого начального узла.В конце концов, два пути должны пересекаться.Тестирование на пересечение может быть таким же простым, как поддержание std::map адресов узлов.

ОБНОВЛЕНИЕ

Поскольку вы обновили свой вопрос, указав Ненаправленный деревьев, то вышеприведенное недействительно.Простой подход - просто выполнить обход в глубину, начиная с узла № 1, в конце концов вы попадете на узел № 2.Это O (n) в размере дерева.Я не уверен, что будет более быстрый подход, если предположить, что это абсолютно общее дерево.

Answer 2

Поиск в ширину и поиск в глубину более эффективны, чем алгоритм Дейкстры.

Answer 3

Предположим, у вас есть

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

, тогда можно было бы пройти по всему дереву, начиная с корня, сохраняя всю цепочку во время обхода.Если вы найдете, например, node1, то сохраните текущую цепочку, если вы найдете node2, то вы проверяете пересечение ... в коде ( UNTESTED ):

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;
}