algorithm - ユニオン検索アルゴリズムを使用して接続されている場合、2 つのノード間のパスを見つけることができますか?

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

ユニオン/検索を実装するアルゴリズムは多数ありますが、あなたの質問からは、ばらばらなセット フォレストの実装について言及しているようです。したがって、この特定の実装に焦点を当てます。

結合操作と検索操作のパフォーマンスを向上させるために、互いに素なセット フォレストは、パス圧縮などのさまざまなヒューリスティックを適用します。これらのヒューリスティックは、漸近的な複雑さの結合と発見を改善しますが、その結果、元のグラフ構造を再構築することはできなくなります。このため、2 つの頂点間のパスを見つけることができません。結局のところ、アルゴリズムはこの特定の問題を解決することを目的としています-ユニオンと検索を実行できるようにします。

ただし、他のユニオン/検索実装を使用できます。たとえば、Disjoint セット フォレストと同じ考え方を使用できますが、パス圧縮は使用できません (ランクによるユニオンを引き続き使用できます)。もちろん、これによりユニオンと検索の漸近的な複雑さが増しますが、グラフ構造も保持されるため、頂点間のパスを見つけることができます。