しかし、実装すると、同じ機能と動作の多くを共有しているように見えます。
素集合の各要素は、グラフの頂点と見なすことができます。Union-Find のセットを表すグラフのエッジを使用します。
http://algs4.cs.princeton.edu/15uf/およびhttp://algs4.cs.princeton.edu/42digraph/を確認した後
どちらも次のような質問に答えることができると思います。
- これらの 2 つの要素/頂点は接続されていますか?
- サイクルはありますか？
それで、私が見ていない2つの間に大きな違いはありますか? いつどちらを使用するかを選択する必要がありますか?
グラフ アルゴリズムが Union-Find 構造を内部的に使用できることがわかります http://algs4.cs.princeton.edu/43mst/KruskalMST.java.html
実装の詳細ですが、Union-Find の方が高速である場合、深さ優先検索を使用してサイクルをテストするのはなぜですか? http://algs4.cs.princeton.edu/44sp/DirectedCycle.java.html