Union-find: Difference between revisions

From Algowiki
Jump to navigation Jump to search
(Created page with "== General information == '''Representation invariant:''' # There is a natural number <math>N\in\mathbb{N}</math>, which is constant throughout the lifetime of the object. #...")
 
No edit summary
 
(11 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,\lodts,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 ==


== Methods ==
'''Input:''' An element <math>i\in\{1,\ldots,N\}</math>.


Name: '''find'''.
'''Output:''' The element <math>j\in\{1,\ldots,N\}</math> that represents the subset to which <math>i</math> currently belongs (<math>i=j</math> is possible).
Input: An element <math>i\in\{1,\ldots,N\}</math>.
Output: The element <math>j\in\{1,\ldots,N\}</math> that represents the subset to which <math>i</math> currently belongs (<math>i=j</math> is possible).
Precondition:
Postcondition:
Method


Name:  '''unite'''.
'''Precondition:''' none.
Input: Two elements, <math>i,j\in\{1,\ldots,N\}</math>.
Output:
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:''' none.
== Unite ==
'''Input:''' Two elements, <math>i,j\in\{1,\ldots,N\}</math>.
'''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>.
'''Postcondition:''' The subsets to which <math>i</math> and <math>j</math> belong are united (the representative of the united set is not specified).


== Known implementations ==
== Known implementations ==


# Union-find with lists
# [[Union-find with lists]]

Latest revision as of 13:58, 20 June 2015

Chapters
  1. [00:00] Einführung
  2. [06:27] Wie funktioniert Union-Find nochmal?
  3. [07:03] Und wie war das noch mit der asymptotischen Komplexität?

General information

Representation invariant:

  1. There is a nonnegative natural number [math]\displaystyle{ N\in\mathbb{N} }[/math], which is constant throughout the lifetime of the object.
  2. At any moment, there is a (dynamically changing) partition of [math]\displaystyle{ S:=\{1,\ldots,N\} }[/math] into non-empty disjoint subsets. Each element of [math]\displaystyle{ S }[/math] belongs to exactly one of these partition sets.
  3. Each of these subsets [math]\displaystyle{ S'\subseteq S }[/math] is represented by an arbitrary particular member of [math]\displaystyle{ S' }[/math], which does not change as long as [math]\displaystyle{ S' }[/math] is one of the partition sets (in other words, as long as [math]\displaystyle{ S' }[/math] is not involved in any call of method unite).

Constructor: Receives [math]\displaystyle{ N }[/math] as its input and initializes the union-find object such that each [math]\displaystyle{ i\in\{1,\ldots,N\} }[/math] is a singleton [math]\displaystyle{ \{i\} }[/math], which is represented by its unique member [math]\displaystyle{ i }[/math].

Find

Input: An element [math]\displaystyle{ i\in\{1,\ldots,N\} }[/math].

Output: The element [math]\displaystyle{ j\in\{1,\ldots,N\} }[/math] that represents the subset to which [math]\displaystyle{ i }[/math] currently belongs ([math]\displaystyle{ i=j }[/math] is possible).

Precondition: none.

Postcondition: none.

Unite

Input: Two elements, [math]\displaystyle{ i,j\in\{1,\ldots,N\} }[/math].

Output: none.

Precondition: The elements [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math] do not belong to the same subset. In other words, it is find[math]\displaystyle{ (i)\neq }[/math] find[math]\displaystyle{ (j) }[/math].

Postcondition: The subsets to which [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math] belong are united (the representative of the united set is not specified).

Known implementations

  1. Union-find with lists