在无向树中寻找路径的算法

Question

假设我有一棵无向树，并且我需要找到两个节点之间的路径（唯一的路径）。

最好的算法是什么？我可能可以使用 Dijkstra 算法，但对于树而言可能有更好的算法。

提供 C++ 示例会很有帮助，但不是必需的。

谢谢。

- YAKOVM

---

你的意思是要找到“唯一”的路径。除非允许路径多次遍历同一节点，否则树中从一个节点到另一个节点只有一条路径（实际上这是树的可能定义之一）。 - 6502

我发布了一个答案，假设您也对部分“向上”的路径感兴趣，即使在您的表示中没有到父节点的链接。这在问题中确实不清楚... - 6502

Answer 1

假设每个节点都有指向其父节点的指针，那么从每个起始节点向根节点回溯即可。最终，这两条路径必须相交。测试是否相交可以简单地维护一个节点地址的std :: map。

更新

由于您更新了问题以指定无向树，则上述方法无效。一种简单的方法是从节点#1开始执行深度优先遍历，最终会到达节点#2。这在树的大小方面是O（n）。假设完全一般的树，我不确定是否会有比这更快的方法。

- Oliver Charlesworth

---

我在谈论无向树。 - YAKOVM

@Yakov：嗯，是的，这显然有所不同！很高兴看到您已经相应地更新了您的问题。 - Oliver Charlesworth

Answer 2

广度优先搜索和深度优先搜索比Dijkstra算法更有效。

- lacungus

---

如果所有边的权重都是1（或更一般的相同），那么Dijkstra算法不就等同于广度优先搜索吗？ - CodesInChaos

不是这样的。如果你使用Dijkstra算法，你必须选择最近的未访问交叉点（这很慢）。因此，复杂度为O（E + V logV），其中E表示边缘，V表示顶点，如果你使用斐波那契堆来提取最小值。如果你使用广度优先搜索，复杂度为O（E+V）= O（V）（它是一棵树，所以E = V-1）。 - lacungus

Answer 3

假设你有

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

- 6502