查找树中两个给定顶点之间路径的最有效方法
Most efficient way to find path between two given vertices in a tree
我有一棵树。
两个顶点 a,b 作为输入给出，我们需要打印它们之间的路径。
一种方法是从 a 中找到所有路径并打印以 b.Is 结尾的路径 有更好的解决方案吗？
让你的两个节点为A, B。
简单的解决方法就是把它当作任何Path finding problem, and ignore the tree property of the graph. In this case, BFS or Bi Directional BFS会比找到所有路径更高效，并在O(|V|).
中找到最短路径
在这种方法中，您 运行 来自 A/B 的 BFS - 或来自两者的双向 BFS 以获得最短路径。
更复杂的技术包括将树视为有根的，然后您可以首先在树中找到 A 和 B 的 Lowest Common Ancestor。让它成为 S。那么，最短路径就是 A->...->S->...->B.
这可以在 O(h) 时间内完成，其中 h 是树的高度。
我有一棵树。 两个顶点 a,b 作为输入给出，我们需要打印它们之间的路径。 一种方法是从 a 中找到所有路径并打印以 b.Is 结尾的路径 有更好的解决方案吗？
让你的两个节点为A, B。
简单的解决方法就是把它当作任何Path finding problem, and ignore the tree property of the graph. In this case, BFS or Bi Directional BFS会比找到所有路径更高效，并在O(|V|).
在这种方法中，您 运行 来自 A/B 的 BFS - 或来自两者的双向 BFS 以获得最短路径。
更复杂的技术包括将树视为有根的，然后您可以首先在树中找到 A 和 B 的 Lowest Common Ancestor。让它成为 S。那么，最短路径就是 A->...->S->...->B.
这可以在 O(h) 时间内完成，其中 h 是树的高度。