Idee: Für jedes Element aus {1,...,n} führe einen Knoten ein. Diese Knoten faßt man in Bäumen zusammen, die durch ihre Wurzel repräsentiert werden.
Die dazu benötigte Datenstruktur: VAR vater: ARRAY[0..n-1] OF INTEGER,
Dabei gilt: | vater[x] = yy ist Vater von x |
vater[x] = xx ist Wurzel x ist Repräsentant. |
Daraus ergeben sich folgende Prozeduren:
PROCEDURE find(x: INTEGER): INTEGER
(* liefert Repräsentanten von x *)
BEGIN
WHILE vater[x] x DO
x := vater[x];
END;
RETURN x;
END;
PROCEDURE union(x, y: INTEGER);
BEGIN
vater[find(x)] := find(y);
END;
Die optimale Situation für die find-Prozedur liegt dann vor, wenn der Baum möglichst flach ist, also alle Knoten direkte Söhne der Wurzel sind. Die Prozedur union zerstört diese Situation aber, indem sie die Bäume vereinigt und sie untereinander setzt.
Um diesen Schaden allerdings möglichst klein zu halten, gibt es zwei verschiedene Ansätze: