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

Question

假设我有一棵无向树，我需要在两个节点之间找到一条路径(唯一路径)。

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

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

谢谢

Answer 1

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

更新

当您更新问题以指定无向 树时，以上内容无效。一种简单的方法是简单地从节点 #1 开始执行深度优先遍历，最终您将到达节点 #2。这是树的大小的O(n)。假设有一个完全通用的树，我不确定是否有比这更快的方法。