Disjointセットを使用してJavaでクラスカル法を実装する場合、パス圧縮を個別の関数として呼び出す必要がありますか、それともfind()関数の不可欠な部分にする必要がありますか?
素find
集合フォレストで操作を呼び出すときはいつでも、パス圧縮およびランクごとの和集合などの他の最適化を適用する必要があります。
一つの方法は、これを見るために:クラスカル法の観点から、あなただけ呼び出すことができるようにする必要があるfind
とunion
し、それらが正常に動作しています。正しく作成および動作する方法の詳細について心配する必要はありません。すべてが迅速に実行されるようにするのは、互いに素なフォレストの責任です。したがって、への呼び出しは、圧縮が発生していることを確認できる場所です。find
union
find
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加