Hoshen–Kopelman algorithm: Difference between revisions

Revision as of 07:42, 10 January 2023

Revision as of 07:47, 10 January 2023

Line 19:

== Union-find algorithm ==

This algorithm is a simple method for computing [[equivalence class]]es. Calling the function <code>union(x,y)</code> specifiesreturns that,whether items <code>x</code> and <code>y</code> are members of the same equivalence class. Because equivalence relations are [[Transitive relation|transitive]];, all the items equivalent to <code>x</code> are equivalent to all the items equivalent to <code>y</code>. Thus for any item <code>x</code>, there is a set of items which are all equivalent to <code>x</code> . This set is(called the equivalence class of which <code>x</code> is a member). A second function <code>find(x)</code> returns a representative member of the equivalence class to which <code>x</code> belongs.

== Pseudocode ==