algorithm - 从最小生成树计算两个顶点之间的子路径

Question

我有一个给定图表的最小生成树（MST）。我正在尝试为任何两个顶点计算唯一的子路径（它应该是 MST 的一部分，而不是图形），但我很难找到一种有效的方法。

到目前为止，我已经使用 Kruskal 的算法（使用不相交数据结构）来计算 MST（例如：10 个顶点 A 到 J）.. 但是现在我想计算 C 到 E.. 或 J 到 C 之间的子路径（假设图是无向的）。

任何建议，将不胜感激。

Answer 1

如果您只需要其中一个路径，则在树上执行 DFS 可能是最简单的解决方案，具体取决于您存储树的方式。如果它是一个正确的图，那么进行 DFS 很容易，但是，如果您只存储父指针，则可能更容易找到两个节点的最不共同的祖先。

为此，您可以从两个节点 u,v 走到根 r，然后比较 r->u 和 r->v 路径。它们不同的第一个节点是最不共同的祖先。

通过线性预处理，您可以在恒定时间内回答最不常见的祖先查询。如果您想经常查找节点对之间的路径，您可能需要考虑实现该数据结构。我认为这篇论文很好地解释了它。