コンポーネントのラベル付けコードを c++ でコーディングしようとしましたが、4 接続の 2 パス アルゴリズムを使用しています。https://en.wikipedia.org/wiki/Connected-component_labelingを参照してください。そのアルゴリズムには、union-find という名前のデータ構造があります。アルゴリズムがその構造をどのように使用しているかを理解できないため、その構造を取得できず、コーディングできません。そのアルゴリズムで union-find を使用する方法を知っていますか、または少なくとも C++ 環境にネイティブ ライブラリはありますか、またはその構造を理解するためのソースを知っていますか。アニメーションが役に立つかもしれません。
質問する
1155 次
2 に答える
1
Union-Find のデータ構造は、「ディスジョイント セット」とも呼ばれます。ウィキペディアのページ ( http://en.wikipedia.org/wiki/Disjoint-set_data_structure )で、disjoint-set の詳細と情報を実際に見つけることができます。素集合データ構造呼び出しのより詳細な紹介は、本「アルゴリズム入門」第 21 章にあります (Wikipedia ページの参照 1 にも示されています)。
通常、ばらばらな集合のデータ構造について話すときは、「ばらばらな集合の森」と呼ばれる特定の実装について話している。この特定の実装の優れている点は、1) 実装が非常に簡単である、2) 時間の複雑さが完全である (ほぼ一定) ことです。
また、ウィキペディアのページまたは私が言及した本の第 21 章で、互いに素な集合のフォレストを実装する方法の擬似コードを見つけることができます。
于 2012-07-22T02:42:46.100 に答える
0
参照： http： //berkeley.intel-research.net/arahimi/connected/およびhttp://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=5F7A5FE1F4DCBA968A0B0E99B0593F71?doi=10.1.1.2.5996&rep=rep1&type=pdf
于 2012-07-22T01:14:04.600 に答える