問題タブ [disjoint-sets]

最小スパニング ツリーを見つけるプログラムを作成しようとしています。しかし、このアルゴリズムで私が抱えている問題の 1 つは、回路のテストです。Javaでこれを行う最良の方法は何でしょうか。

ここに私のコードがあります

C++ アプリでDisjoint セットを処理するクラスのセットがあります。これらのクラスのデストラクタを実装するのに苦労しています。誰でもそれについて私を助けることができますか?

これらが基本的に行うことは次nodeのNodeAddress[]とおりnodeですval。すべてのノードには、互いに素なセットの先頭と末尾のItemプレースホルダーであるへのポインターがあります。hdtl

変数の可視性 (パブリック アクセス)、定数サイズのバッファーなど、いくつかの問題があることを認識していることを述べたいと思いますNodeAddressが、ここではメモリの割り当て解除に焦点を当てたいと思います。

はい、私はポインタでそれをしたい（必要です）（STLなし）。提案や質問がある場合は、お気軽にコメントしてください。

これはコードです：

ヘッダ

ソース

*編集：* 私が持っているが機能していないものがあります

Pythonで素集合システムを実装していますが、壁にぶつかりました。システムにツリー実装を使用しており、システムにFind（）、Merge（）、およびCreate（）関数を実装しています。

効率を上げるためにランクシステムとパス圧縮を実装しています。

問題は、これらの関数が互いに素なセットのセットをパラメーターとして受け取らなければならないため、トラバースが困難になることです。

Create関数は値のリストを受け取り、適切なデータを含む単一のノードのリストを返します。

マージ関数はこれに似ていると思いますが、

ただし、ノードのリストと値（ノードだけでなく）をパラメーターとして受け取る必要があるため、Find（）関数を実装する方法がわかりません。Find（set、value）がプロトタイプになります。

ノードがFind（x）のパラメーターとして使用される場合にパス圧縮を実装する方法を理解していますが、このメソッドは私を失望させます。

どんな助けでも大歓迎です。ありがとうございました。

明確にするために編集。

私はグラフ理論に不慣れで、これまでグラフ理論で BFS と素集合のみを学んできました。特定の無向の接続グラフにサイクルがある場合、 BFS を使用してそれを見つけることができますか? 私の意図は、サイクル内のすべての頂点を印刷することです。前もって感謝します。

私はフリーベースのコタイプを見つけようとしています。つまり、「互換性のある」タイプが見つかった場合、次のようになります。

/ people / personで始まるとすると、ミュージシャン（/ music / group_member）である可能性がありますが、音楽アルバム（/ music / album）ではない可能性があります。フリーベースにフクロウの「disjointWith」のようなものがあるかどうかはわかりません。タイプ、とにかくMQLクックブックでは、このトリックを使用することを提案しています。

この例のクエリは、特定のタイプのすべてのインスタンスを取得し、次にすべてのインスタンスのすべてのタイプを取得して、それらを一意にします...これは賢いですが、クエリはタイムアウトになります...別の方法はありますか？私にとっては、静的なリスト/結果でも問題ありません。ライブクエリは必要ありません...結果は同じだと思います...

編集： 互換性のないタイプタイプは有用であり、disjointWithに似ているようで、提案とともに使用することもできます...

ありがとう！ルカ

スーパークラス、サブクラスの関係のマッピング

参加制約 - 部分的に素の制約 - 素

外部キーを子から親にマップする必要がありますか? そうしないと、なぜですか？

私は現在、都市と橋を扱う割り当てのコードを書いています。次のような尊敬される地区の都市と橋を印刷する必要があります。

プログラムを実行すると、次のようにソートされます。

ここで、cin を介してこれらの入力を読み取ります。1 2 5 などのすべての可能なパスを配列に格納し、プログラムで並べ替えて整理したいと考えています。問題は、ユーザーからのパスが 500,000 を超える可能性があることです。500k の動的配列を作成したいと考えています。これにより、メモリに関して深刻な問題が発生しますか?

kruskalのアルゴリズムや素集合など、これを解決する他の可能な方法を見てきました（最も役立つと思います）。ばらばらなセットのコーディングを理解するのに非常に苦労しています。もっと慣れ親しんだ方法を試してみました。

値を保存し、それらを比較および整理する場所に関するヘルプは素晴らしいでしょう。これに関する情報を読んだ場所へのリンクが役立ちます。ここ数日、たくさん読んだ。あまり役に立ちませんでした。

すべてを要約すると、私の質問は次のとおりです。

• 500k の動的配列は、メモリに関して深刻な問題を引き起こしますか?
• 値を保存し、パスを指定してそれらを比較および整理する場所は?

互いに素な各セットメンバーの要素数を数えるのに少し問題があります。たとえば、誰かが次のように入力した場合：

注：最初の数値=ソース頂点、2番目の数値=宛先頂点、3番目の数値=長さ

0 2 1

4 8 7

5 8 6

1 2 5

2 3 17

セットのカウントとして2があります

4 8 7

5 8 6

両方が2つと3つの（それぞれの）要素によって接続されているため、セットのカウントとして3。

0 2 1

1 2 5

2 3 17

互いに素な各セットの要素数のカウントを整数配列に格納して、互いに素なセットのカウントにアクセスできるようにすることを考えました。以下は、要素を見つけてそれらを同じセットに結合するための私の実装です。また、すべてのセットでルートを見つける機能もあります。

カウンターをどこで/いつインクリメントして維持するかがわかりません。どんな助けでもいただければ幸いです。ありがとう！

本当に大きなデータ (2 ^ 32 を超える要素と 2 ^ 32 を超えるペアを結合するなど) 用の拡張された Disjoint-sets アルゴリズムはありますか?

明らかに最大の問題は、そのような大きな配列を作成できないことです。そのため、タスクを達成するためのより良いアルゴリズムまたはより良いデータ構造があるかどうか疑問に思っていますか?

私はNノードとN-1エッジで、基本的に無向非循環MSTでした。基本的に、ばらばらなノードのセットの数を数えたいと思います。2 つのノードが同じ親を持ち、ノードの次数が同じ場合、2 つのノードはセットに属します。たとえば。指定されたツリーで。{3,4} は同じセットに属します。なぜならparent[3]=1、 andparent[4]=1およびdegree[3]=degree[4]=1 ; {5} と {2} も非素集合 を形成するからdegree[5]=2 and degree[2]=3です。素集合の総数を数えなければなりません。私は次のような構造でやろうとしています:

しかし、p_data配列が非常に大きいことを示しています。ですから、助けてください。上記で定義された素集合の総数を数えるには、どのようなデータ構造またはロジックに従う必要がありますか。

ここに画像を投稿できません: この画像を参照してください: http://postimage.org/image/sw2nrciib/

実行できるディスジョイントセットの数を誰か教えてください