算法在无向树中查找路径

Question

假设我被赋予了一个无向树,我需要在两个节点之间找到一条路径(唯一的路径).

什么是最好的算法.我可能会使用Dijkstra的算法,但树木可能更好.

C++示例将有所帮助,但不是必需的

谢谢

Answer 1

假设每个节点都有一个指向其父节点的指针,那么只需从每个起始节点向后追溯树.最终,两条路径必须相交.测试交集可以像维护std::map节点地址一样简单.

UPDATE

当您更新问题以指定无向树时,上述内容无效.一个简单的方法就是从节点#1开始执行深度优先遍历,最终你会遇到节点#2.这是树的大小的O(n).假设一棵完全普通的树,我不确定会有更快的方法.

Answer 2

假设你有

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

那么可以做的就是从根开始遍历整个树，并在遍历过程中保持整个链。如果你找到例如node1，那么你保存当前链，如果你找到node2，那么你在代码中检查交集（未经测试）：

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