I try to code in c++ a component labelling code uses two pass algorithm with 4-connectivity. You might want to see https://en.wikipedia.org/wiki/Connected-component_labeling. In that algorithm there is a data structure named as union-find. I cannot get the structure of that and cannot code it since I cannot understand how the algorithm is using that structure. Do you know how to use union-find in that algorithm or at least Is there any native library in C++ environment or do you know any source to understand that structure. Maybe an animation might be useful.
1
-
This can be found at stackoverflow.com/questions/14347065/…mmgp– mmgp2013-01-25 05:04:26 +00:00Commented Jan 25, 2013 at 5:04
Add a comment
|
2 Answers
The data structure of Union-Find is also called a "disjoint-set". You can actually find some more descriptions and information of disjoint-set on its Wikipedia page (http://en.wikipedia.org/wiki/Disjoint-set_data_structure). A more detailed introduction to disjoint-set data structures call be found in the book "Introduction to Algorithms" Chapter 21 (as also shown in Reference 1 of the Wikipedia page.)
Usually when we talk about disjoint-set data structures, we are talking about a specific implementation called "disjoint-set forest". What is good about this specific implementation is that: 1) it is really easy to implement 2) has a perfect time complexity (almost constant).
You can also find some pseudocode of how to implement disjoint-set forest in the Wikipedia page or in Chapter 21 of the book I've mentioned.
1 Comment
Potatoswatter
You can add hyperlinks with the globe/arrow button in the markup toolbar.
