algorithm - 如果使用联合查找算法连接两个节点，我们能否找到它们之间的路径？

Question

    I studied the union find algo and found it is very useful in following ways.

    to find out if 2 node are connected or not
    to compress the path. (save space)

    if the problem is to find if 2 node connected or not , then we can use union
 find.But if we have to find out the path between these 2 node, 
then how can we use the data structure which is use to find 
union find ( data structure  use is - it store root element in 
arrays of node. form kind of tree)?

    I tried a lot and found that we have to use graph to find out the path\
between node and can not use union find data structure .

    any other views on it.

Answer 1

有许多算法可以实现联合/查找，但从您的问题看来，您指的是不相交的集合森林实现。因此，我将专注于这个特定的实现。

为了提高联合和查找操作的性能，不相交集森林应用了不同的启发式方法，例如路径压缩。这些启发式方法改进了渐近复杂度并集和查找，但结果您无法再重建原始图结构。因此，您将无法找到两个顶点之间的路径。毕竟该算法旨在解决这个特定问题 - 能够执行联合和查找。

但是，您可以使用其他一些联合/查找实现。例如，您可以使用与不相交集森林相同的想法，但没有路径压缩（您仍然可以按等级使用联合）。这当然会增加 union 和 find 的渐近复杂度，但也会保留图结构，因此您将能够找到顶点之间的路径。