algorithm - 两个不相交集之间的路径(路径算法)

Question

我有以下问题。我在图中有两组不相交的顶点，我想知道这两组之间是否存在路径。

我只需要知道这样一条路径存在即可。

我在某处读到这可以使用 union-find 数据结构来解决，但我找不到适合我需要的算法

非常感谢任何帮助。

Answer 1

使用 Union-Find data structure 可以有效地解决问题.

用A和B表示两组顶点，并初始化一个Union-Find数据结构，使得图的每个顶点v属于自己的集合。

令a1 为A 的任意顶点。对 A 中的每个顶点 a 执行 UNION(FIND(a1), FIND(a))(除了 a1 这将成为集合的代表)。然后对 B 中的顶点做同样的事情:令 b1 为 B 的任意顶点并执行 UNION(FIND(b1) , FIND(b)) 为 B 的每个顶点 b。

现在 FIND(a1) 准确返回属于 A 的顶点集，FIND(b1) 准确返回属于 A 的顶点集B。特别是，如果 A 和 B 彼此相交，则 FIND(a1)=FIND(b1)。对于图中的每条边 (u,v)，执行 UNION(FIND(u), FIND(v))。

A 和 B 之间存在一条路径当且仅当在上述过程中您已经将 a1 的集合与集合合并b1。

您完成的 UNION/FIND 操作的数量最多为 O(|E|+|A|+|B|)。因此，算法的运行时间为 O(alpha(n)*(|E|+|A|+|B|)) 其中 alpha(n) 是Inverse Ackerman function .逆阿克曼函数增长非常缓慢，是每个 UNION 或 FIND 操作运行时间的上限。