問題タブ [union-find]

私はunion-findアルゴリズムを扱っています。私のプログラムの最初の部分では、アルゴリズムは big set の分割を計算しEます。

その後S、特定の node を含むset のすべてのメンバーを取得したいと考えていますx。

E今までは単純に、 setのすべての要素のメンバーシップをテストしていましたS。しかし、昨日、「アルゴリズムの紹介」(CLRS、第 3 版、例 21.3-4) を読んでいて、演習で次のことがわかりました。

PRINT-SET(x)ノードが与えられ、のセットのxすべてのメンバーを任意の順序で出力する操作 を追加したいとします。x互いに素な集合の森の各ノードに単一の属性を追加する方法を示して、の集合PRINT-SET(x)のメンバーの数に比例して時間がかかりx、他の操作の漸近的な実行時間は変更されないようにします。

「セットのメンバー数の線形x」は、私の問題を大きく改善するでしょう! だから、私はこの演習を解決しようとしています...そしていくつかの失敗した試みの後、スタックオーバーフローで助けを求めています!

グラフ内の互いに素な集合の数を見つけてから、グラフのGいくつかの頂点を削除してグラフGを作成しますG'.へ？G'G'G

今週の日曜日に試験があるんだけど、自分がやっていることは正しいかどうかを確認したいだけなんだ (試験は私を懐疑的にするんだよね)

アルゴリズムの仕組みは次のとおりです。

これは質問です：

n 個の要素の集合から素集合に対する Union-Find 問題のために開発されたアルゴリズムを思い出してください。Find はパス圧縮を使用し、Union はランキングを使用します。また、同じランクの 2 つのツリーの和集合は、2 番目の引数に関連付けられたルートを新しいルートとして選択します。セット S = {1, 2, ..., 10} と 10 個の互いに素な部分集合 (それぞれが 1 つの要素を含む) から始めます。を。
Union(1,2)、Union(3,4)、Union(5,6)、Union(1,5)、Union(1,3)を実行した後、ツリーの最終セットを描画します。

そして、これは質問に対する私の解決策です：

このアルゴリズムに関するヒントや提案があれば幸いです。

ありがとう！

ここから、ランクとパスの圧縮によるユニオンを使用した UnionFind の実装を見ていますhttp://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests (CLRS とほぼ同じ擬似コードです)パス圧縮がランクを変更しない理由を理解していません。ルートからの最長パスのエンドポイントを呼び出すfindと、ランクが下がり、そうでない場合、次のunion操作で間違ったルートが選択されます。

これは、私が答えようとしているインタビューの質問です。

メンバーを含むソーシャル ネットワークと、メンバーのペアが友情を形成した時間のタイムスタンプをN含むログ ファイルが与えられた場合M、すべてのメンバーが接続された最も早い時間を決定するアルゴリズムを設計します (つまり、すべてのメンバーは友人の友人の友人です)。 ..友人の）。ログファイルはタイムスタンプでソートされており、友情は同値関係であると仮定します。アルゴリズムの実行時間はM log Nかそれ以上で、 に比例して余分なスペースを使用する必要がありますN。

最初に思ったのは「これは無理だ！」

しかし、このソーシャル ネットワークをデータ構造として表現するにはどうすればよいかを考えました。Union-find は、使用できるデータ構造です。ここで、すべてのメンバーが接続されているとはどういう意味かを理解しなければなりません。実際のデータ構造と、すべてのメンバーが互いに友達になったときの様子を表示するにはどうすればよいですか?

システムが完全に接続される方法を視覚的または概念的に理解できるまで、そのイベントに対応するタイムスタンプを見つける方法を理解し始めることができないと思います。

通常、union find を使用するときは、1 次元配列を作成し、各インデックスの値を配列内の位置で初期化します。したがって、5 要素の配列の場合、各要素はインデックス ( ) と同じ値になります0-4。

複数の次元を持つユニオン検索データ構造を使用すると、さらに難しくなります。10x10 サイトのグリッドがあるとします。各サイトは最初はオフになっています (多次元配列、各インデックスは value です-1)。私の実装では、配列の次元を指定してサイトを有効にする方法を提供しています。open(4, 3)4 行目に移動し、グリッドの 3 番目のサイトをオンにします。このサイトをオンにした場合、インデックスにどのような値をどのように与えるでしょうか?

最初のサイトとの相対的な位置に独自の価値を与えることを考えていました。そのため、position のサイトに(4, 3)は値 43 が与えられます (下に 10 サイトの 4 行 + 右に 3 つのサイト)。ただし、これには、各サイトを調べて各要素を数えて、格納される値を取得する必要がありますO(n)。4andを文字列に変換し3て結合することもできますが、これは講義の演習であり、彼らが望んでいることではないと思います。

さらに、グリッド上の 2 つのサイトを接続すると、同じ問題が発生します。インデックスを見つけるためにほとんどの配列を調べずに、接続を表す値を決定するにはどうすればよいですか?

私が試みていることを行うためのより良い方法はありますか?

クラスカルのユニオン検索アルゴリズムを実装しようとしています。私はこの疑似コードを使用していますが、以下のユニオン部分のステップ 2 (再帰呼び出しではない) を理解していないか、私が近いかどうかさえわかりません。この方法がうまくいかない場合は、理解できる限り、どの実装でも使用できます。事前に感謝します。U と V は私のエッジ ノードで、今のところ int です。

ステップ2がわかりません。これまでのコードは次のとおりです。

Union の機能をサポートするばらばらのセットを検討しています。

木の高さを減らすテクニック：

常に小さいツリーを大きいツリーにマージします。つまり、小さいツリーのルートが大きいツリーのルートを指すようにします。

より多くのノードがある場合、ツリーは他のツリーよりも大きくなります。

各ノードは、フィールドを持つ構造体です。要素に関する情報、親ノードへのポインタ「親」、およびノー​​ドがルートである場合にのみ使用され、ノードの数を含むカウンター「カウント」です。アップツリー。

次のアルゴリズムは、2 つのアップ ツリーをマージします。

最大で k 個の素集合が存在する可能性がある、和集合を使用した素集合の実装を考えてみましょう。この実装では、ハッシュ テーブル A[0.. max-1] を使用します。このテーブルには、順序付けられた二重ハッシュ法に基づいてキーが格納されます。h1 と h2 をそれぞれ 1 次ハッシュ関数と 2 次ハッシュ関数とします。A には、上記のすべてのツリーのノードのキーと、それぞれに対応するノードへのポインターが含まれています。パラメータとして 2 つのノードのキーを取り、ノードが属するアップ ツリーをマージするアルゴリズムを書きたいです (ノードは任意のアップ ツリーに属することができますが、同時にその場合は適切なメッセージが表示されます)。 . 合流時には、パスの圧縮と高さの削減の手法を適用する必要があります。

どうすればこれを行うことができるか、ヒントを教えていただけますか?

次の配列があるとします。

最初は、ノードは次のようになります。

次に、k1=100、k2=5 の場合、アルゴリズムを適用した後、これが得られるでしょうか?

次に、k1=59、k2=5 の場合、次のようになります。

右？次に、パス圧縮を適用して、これを開始します。

したがって、parent=F、tmp->parent=B、tmp=F となります。

どうやって続けますか？

k1=14、k2=59 とすると、次のようになります。