Union-Find アルゴリズムでのレベル マージとパス圧縮

union-find セット (または素セット) と呼ばれるアルゴリズムは、個別のセットを維持し、セットのメンバーシップを確認し、セットを結合する操作を提供します。これは、要素間の現在の接続情報を維持するために重要な結合および検索操作を専門的に処理します。

＃＃＃文法＃＃＃

わかりやすくするために、まず、次のコード例で使用しようとしているメソッドの構文を理解しましょう。

リーリー ＃＃＃アルゴリズム＃＃＃

結合検索アルゴリズムは、結合と検索という 2 つの基本操作で構成されます。和集合演算は 2 つの集合を結合し、検索演算は集合の代表要素を決定します。共用体検索操作を繰り返し適用することで、効率的な共用体検索データ構造を構築できます。

レベルごとに統合

レベルによる結合手法は、小さなツリーが常に大きなツリーのルートに接続されるようにすることで、結合操作を最適化するために使用されます。このアプローチにより、ツリーのバランスが崩れすぎて検索操作が非効率になることが防止されます。

レベルによる結合のアルゴリズムは次のとおりです -

要素 x と y を含むセットの代表 (ルート要素) を見つけます。

• 代表者が同じ場合は戻ってください。

• x の代表のレベルが y の代表のレベルより大きい場合、y の代表が x の代表を指すようにし、x の代表のレベルを更新します。

• それ以外の場合は、x の代表者が y の代表者を指すようにし、必要に応じて y の代表者のランキングを更新します。

• パス圧縮

パス圧縮は、クエリ データ構造内のツリーの高さを減らすもう 1 つの最適化手法です。その目的は、シーク操作中にパスを平坦化し、後続の操作でより短いパスを提供することです。

パス圧縮のアルゴリズムは次のとおりです -

• 要素 x を含む集合の代表 (ルート要素) を見つけます。

• x からその代表までのパスをたどるとき、訪問した各要素が代表を直接指すようにします。

• ＃＃＃方法＃＃＃

  ランク単位の結合とパス圧縮の基本概念を理解したところで、C で結合検索アルゴリズムを実装する 2 つの異なる方法について説明します。

方法 1: 配列ベースの実装

このアプローチでは、各コレクションを配列として表します。各インデックスの値は、要素の親要素を表します。最初は、各要素はそれ自体の親であり、それがそのコレクションの代表であることを示します。

＃＃＃アルゴリズム＃＃＃

親配列の初期化プロセスを開始しましょう。各要素には独自の親要素が割り当てられます。

パス圧縮を使用して検索操作を実装します。

• Union by Rank を使用してユニオン操作を実装します。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

  方法 2: ツリーベースの実装

調査対象のコレクションを説明するために、ツリーベースのアプローチを使用しました。グループ内の各項目はそれぞれの親ノードに関連付けられており、その特定のコレクションを表すルート ノードを指定します。
• ＃＃＃アルゴリズム＃＃＃

各要素が独自の親要素となる親配列を初期化します。

パス圧縮と再帰的ツリー走査を使用して、検索操作を実装します。

Union by Rank を使用してユニオン操作を実装します。

完全な実行可能コード

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃
つまり、階層結合とパス圧縮は結合検索アルゴリズムの主要なテクノロジです。これらはユニオン操作とルックアップ操作をそれぞれ最適化し、パフォーマンスの向上と効率的な接続情報管理を実現します。これらの手法を C で実装することにより、セット、接続性、グラフに関連する問題を効率的に解決できます。

• 要約すると、構文とステップバイステップのアルゴリズムを紹介し、実際の C 実行可能コード例を 2 つ提供しました。ランクごとの和集合とパス圧縮を理解して適用することで、アルゴリズム スキルを向上させ、複雑な問題をより効率的に解決できます。

以上がUnion-Find アルゴリズムでのレベル マージとパス圧縮の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。