Union-find: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
(7 intermediate revisions by one other user not shown) | |||
Line 1: | Line 1: | ||
{{#ev:youtube|https://youtu.be/wE8Y8TU-iUI|500|right|Chapters | |||
#[00:00] Einführung | |||
#[06:27] Wie funktioniert Union-Find nochmal? | |||
#[07:03] Und wie war das noch mit der asymptotischen Komplexität? | |||
|frame}} | |||
== General information == | == General information == | ||
'''Representation invariant:''' | '''Representation invariant:''' | ||
# There is a natural number <math>N\in\mathbb{N}</math>, which is constant throughout the lifetime of the object. | # There is a nonnegative natural number <math>N\in\mathbb{N}</math>, which is constant throughout the lifetime of the object. | ||
# At any moment, there is a (dynamically changing) partition of <math>S:=\{1,\ldots,N\}</math> into non-empty disjoint subsets. Each element of <math>S</math> belongs to exactly one of these partition sets. | # At any moment, there is a (dynamically changing) partition of <math>S:=\{1,\ldots,N\}</math> into non-empty disjoint subsets. Each element of <math>S</math> belongs to exactly one of these partition sets. | ||
# Each of these subsets <math>S'\subseteq S</math> is represented by an arbitrary particular member of <math>S'</math>, which does not change as long as <math>S'</math> is one of the partition sets. | # Each of these subsets <math>S'\subseteq S</math> is represented by an arbitrary particular member of <math>S'</math>, which does not change as long as <math>S'</math> is one of the partition sets (in other words, as long as <math>S'</math> is not involved in any call of method [[#Unite|unite]]). | ||
'''Constructor:''' | '''Constructor:''' | ||
Receives <math>N</math> as its input and initializes the union-find object such that each <math>i\in\{1,\ldots,N\}</math> is a singleton <math>\{i\}</math>, which is represented by its unique member <math>i</math>. | Receives <math>N</math> as its input and initializes the union-find object such that each <math>i\in\{1,\ldots,N\}</math> is a singleton <math>\{i\}</math>, which is represented by its unique member <math>i</math>. | ||
== | == Find == | ||
'''Input:''' An element <math>i\in\{1,\ldots,N\}</math>. | '''Input:''' An element <math>i\in\{1,\ldots,N\}</math>. | ||
Line 19: | Line 24: | ||
'''Postcondition:''' none. | '''Postcondition:''' none. | ||
== | == Unite == | ||
''Input:''' Two elements, <math>i,j\in\{1,\ldots,N\}</math>. | '''Input:''' Two elements, <math>i,j\in\{1,\ldots,N\}</math>. | ||
'''Output:''' none. | '''Output:''' none. | ||
'''Precondition:''' The elements <math>i</math> and <math>j</math> do not belong to the same subset. In other words, it is find<math>(i)\neq</math>find<math>(j)</math>. | '''Precondition:''' The elements <math>i</math> and <math>j</math> do not belong to the same subset. In other words, it is find<math>(i)\neq</math> find<math>(j)</math>. | ||
'''Postcondition:''' The subsets to which <math>i</math> and <math>j</math> belong are united (the representative of the united set is not specified). | '''Postcondition:''' The subsets to which <math>i</math> and <math>j</math> belong are united (the representative of the united set is not specified). | ||
Line 31: | Line 36: | ||
== Known implementations == | == Known implementations == | ||
# Union-find with lists | # [[Union-find with lists]] |
Latest revision as of 13:58, 20 June 2015
General information
Representation invariant:
- There is a nonnegative natural number
, which is constant throughout the lifetime of the object. - At any moment, there is a (dynamically changing) partition of
into non-empty disjoint subsets. Each element of belongs to exactly one of these partition sets. - Each of these subsets
is represented by an arbitrary particular member of , which does not change as long as is one of the partition sets (in other words, as long as is not involved in any call of method unite).
Constructor:
Receives
Find
Input: An element
Output: The element
Precondition: none.
Postcondition: none.
Unite
Input: Two elements,
Output: none.
Precondition: The elements
Postcondition: The subsets to which