Union-Find-Strukturen
Prof.Dr.Th Ottmann
WS 2006-07
11
Union-Find Strukturen
Problem:
Verwaltung einer Familie von paarweise disjunkten Mengen unter den
Operationen:
e.make-set():
Erzeugt eine neue Menge mit Element e.
e.find-set():
Liefert diejenige Menge Mi, die das Element e enthält.
WS 2006-07
2
Union-Find Strukturen
union(Mi, Mj):
Vereinigt die Mengen Mi und Mj zu einer
neuen Menge.
Repräsentation der Mengen Mi :
Mi wird durch ein repräsentatives (kanonisches) Element
aus Mi identifiziert.
WS 2006-07
3
Union-Find Strukturen
Operationen mit repräsentativen Elementen:
e.make-set():
Erzeugt eine neue Menge mit einzigem Element e. Die Menge wird
durch e repräsentiert.
e.find-set():
Liefert den Namen des Repräsentanten derjenigen Menge, die das
Element e enthält.
e.union(f):
Vereinigt die Mengen Me und Mf , die die Elemente e und f enthalten
zu einer neuen Menge M und liefert ein Element aus
Me  Mf als Repräsentanten von M. Me und Mf werden zerstört.
WS 2006-07
4
Folgerungen
 Ist n die Anzahl der e.make-set() Operationen und werden
insgesamt m Operationen e.make-set(), e.find-set(), e.union(f)
ausgeführt, so ist
 m >= n
 nach höchstens (n – 1) union – Operationen besteht die
Kollektion von Mengen nur noch aus einer einzigen Menge
WS 2006-07
5
Anwendungs-Beispiel: Zusammenhangstest
Input: Graph G =(V,E)
Output: die Familie der Zusammenhangskomponenten von G
Algorithmus: Connected-Components
for all v in V do v.makeset()
for all (u,v) in E do
if u.findset()  v.findset()
then u.union(v)
Same-Component (u,v):
if u.findset() = v.findset()
then return true
WS 2006-07
6
Repräsentation durch verkettete Listen
e
b
f
a
• x.make-set()
• x.find-set()
• x.union(y)
g
WS 2006-07
h
d
7
Repräsentation durch verkettete Listen
b.union(d)
e
WS 2006-07
b
f
a
g
h
d
8
Teurere Operations-Folge
e1.make-set()
e1
e2.make-set()
e2
en.make-set()
en
e2.union(e1)
e2
e1
e2.union(e1)
e3
e2
e1
e3
e2
en.union(en-1)
en
en-1
e1
en
en-1
e2
e1
e1
e1
Längere Liste wird stets an kurze angehängt!
Zeigerzuweisungen im i-ten Schritt ei.union(ei-1):
2n Operationen kosten Zeit:
WS 2006-07
9
Verbesserung
Gewichtete Union-Heuristik
Hänge stets die kürzere an die längere Liste.
(Führe Listenlänge als Parameter mit).
Satz
Bei Verwendung der gewichteten Union-Heuristik kann jede Folge
von m make-set(), find-set(), und union()-Operationen, die höchstens n
make-set() Operationen enthält, in Zeit O(m + n log n) ausgeführt werden.
Beweis
Betrachte Element e
Anzahl der Änderungen des Zeigers von e auf das repräsentative Element:
log n
WS 2006-07
10
Repräsentation durch Wald von Bäumen
c
h
b
f
e
r
d
s
g
i
a
u
v
x
y
• a.make-set()
• y.find-set()
• d.union(e): mache den Repräsentanten der einen Menge (z.B. f)
zum direkten Vater des Repräsentanten.
WS 2006-07
11
Beispiel
m = Gesamtanzahl der Operationen (  2n )
for i = 1 to n do ei.make-set( )
for i = n to 2 do ei-1.union(ei )
for i = 1 to f do en.find-set( )
i – ter Schritt
n-i
Kosten für f find-set Operationen:
WS 2006-07
O(f * n)
12
Vereinigung nach Größe
zusätzliches Feld:
e.size = (#Knoten im Teilbaum von e)
e.make-set()
1 e.parent = e
2 e.size = 1
e.union(f)
1 Link(e.find-set( ), f.find-set( ))
WS 2006-07
13
Vereinigung nach Größe
Link(e,f)
1 if e.size  f.size
2
then f.parent = e
3
e.size = e.size + f.size
4
else /* e.size < f.size */
5
e.parent = f
6
f.size = e.size + f.size
WS 2006-07
14
Vereinigung nach Größe
Satz
Das Verfahren Vereinigung nach Größe hat folgende Invariante:
Ein Baum mit Höhe h hat wenigstens 2h Knoten
Beweis
h1
h2
T1
g1  T1  2h
T2
g 2  T2  2h
1
2
T1
WS 2006-07
T2
15
Vereinigung nach Größe
Fall 1: Der neue Baum ist genauso hoch wie T1
g1  g2  g1  2h
1
Fall2 : Der neue Baum ist gewachsen
Höhe von T: h2 + 1
g  g1  g2  2h  2h  2h 1
2
2
2
Konsequenz
Eine find-set-Operation kostet höchsten O( log n ) viele Schritte, falls
die Anzahl der make-set-Operationen gleich n ist.
WS 2006-07
16
Pfadverkürzung
e.find-set()
1 if e  e.parent
2
then e.parent = e.parent.find-set( )
3 return
WS 2006-07
17
Analyse der Laufzeit
m Gesamtanzahl der Operationen, davon
f find-Set-Operation und
n make-Set-Operation.
 höchstens n – 1 union-Operationen
Vereinigung nach Größe:
O( n + f log n)
Vereinigung nach Pfadverkürzung:
Falls f < n, Q(n + f log n)
Falls f  n, Q(f log1 +f/n n)
WS 2006-07
18
Analyse der Laufzeit
Satz ( Vereinigung nach Größe und Pfadverkürzung)
Bei der Verwendung der Strategie Vereinigung nach Größe und
Pfadverkürzung benötigen m Union-Find-Operation über n Elementen
Q(m * (m,n)) Schritte.
(m,n) = Inverse der Ackermann-Funktion
WS 2006-07
19
Ackermann-Funktion und Inverse
Ackermann-Funktion
A(1,j) = 2j
A(i,1) = A(i – 1,2)
A(i,j) = A(i – 1, A(i, j - 1))
für j  1
für i  2
für i,j  2
Inverse Ackermann-Funktion
 (m, n)  min i  1 Ai, m / n  log n
WS 2006-07
20
Ackermann-Funktion und Inverse
Ai, m / n   Ai,1
A2,1  A1,2   22  4
A3,1  A2,2   A1, A2,1  24  16
A4,1  A3,2   A2, A3,1  A2,16 
2
22
22
 265536
 m, n   4, für log n  265536
WS 2006-07
21

11_Union-Find