Dieselbe Information ist auch schon in einem Gerüst des Graphen vorhanden, also in einem Wald, dessen Bäume gerade die Klassen aufspannen; die Wurzeln dieser Bäume kann man als Repräsentanten der Klassen ansehen, und zwei Knoten sind genau dann äquivalent, wenn sie zur selben Wurzel gehören. Der Baum für einen isolierten Knoten besteht nur aus der Wurzel allein.
Manchmal ist man nur an zwei Operationen interessiert, die traditionell Find und Union genannt werden: Find findet zu einem Knoten die zugehörige Klasse, und Union vereinigt die Klassen zweier gegebener Knoten, fügt also eine neue Äquivalenzbeziehung hinzu. Dies läßt sich platzsparend realisieren durch das Gerüst, wobei man nur von jedem Knoten zur Wurzel seines Baumes gelangen können muß. Es genügt also jeweils ein Verweis auf den Vaterknoten, um die Wurzel zu finden, und zur Vereinigung zweier Bäume nimmt man einen Verweis von einer der beiden Wurzeln auf einen beliebigen Knoten des anderen Baumes hinzu.
Damit können wir die Operationen Find und Union
bereits korrekt realisieren, doch läßt sich die Effizienz
noch erheblich verbessern durch einen Kunstgriff,
der Pfadkompression genannt wird.
Find arbeitet um so schneller, je kürzer der dabei
zurückgelegte Weg zur Wurzel ist,
und daher ersetzen wir, sobald wir die Wurzel kennen,
für den Ausgangsknoten und alle Zwischenknoten den Vaterverweis
durch einen Zeiger auf die Wurzel, falls er nicht bereits dorthin weist.
So wird der Baum zusehends immer flacher,
enthält aber immer noch dieselben Knoten und dieselbe Wurzel,
und erfüllt also noch denselben Zweck.
Unser Verfahren beschleunigt sich also durch den Gebrauch selbst!
Das Verfahren ist, abgesehen von seiner praktischen Brauchbarkeit,
auch theoretisch interessant, weil sich bei seiner genaueren Analyse
für seinen Aufwand eine Funktion ergibt, die zwar nicht konstant ist,
aber geradezu unvorstellbar langsam anwächst.