Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


30. Zusammenhang



Algorithmen zur Vereinigungs-Suche

Bei manchen Anwendungen möchten wir einfach wissen, ob in einem Graph ein Knoten x mit einem Knoten y verbunden ist oder nicht; der eigentliche Pfad, der sie verbindet, kann bedeutungslos sein. Dieses Problem ist in den letzten Jahren gründlich untersucht worden; die effizienten Algorithmen, die dabei entwickelt worden sind, sind auch für sich allein von Interesse, da sie auch für die Verarbeitung von Mengen verwendet werden können.

Graphen entsprechen in einer natürlichen Weise Mengen von Objekten: Knoten entsprechen Objekten, und Kanten bedeuten »gehört der gleichen Menge an wie«. So entspricht der Graph aus dem Beispiel im vorangegangenen Kapitel den Mengen {A B C D E F G}, {H I} und {J K L M}. Jede zusammenhängende Komponente entspricht einer anderen Menge. Bei Mengen interessiert uns die grundlegende Frage: »Gehört x der gleichen Menge an wie y?« Dies entspricht offenbar der grundlegenden Frage für Graphen: »Ist Knoten x mit Knoten y verbunden?«

Wenn eine Menge von Kanten gegeben ist, können wir eine Darstellung des entsprechenden Graphen mit Hilfe von Adjazenzlisten erzeugen und Tiefensuche benutzen, um jedem Knoten den Index seiner zusammenhängenden Komponente zuzuweisen, und damit können Fragen der Art »Ist x mit y verbunden?« mit nur zwei Zugriffen auf ein Feld und einem Vergleich beantwortet werden. Die zusätzliche Besonderheit bei den Methoden, die wir hier betrachten, ist, daß sie dynamisch sind: Sie können neue Kanten aufnehmen, wobei beliebig Anfragen eingestreut werden können, und die Anfragen unter Verwendung der erhaltenen Informationen richtig beantworten. Aufgrund der Entsprechung zu dem Problem für Mengen wird das Hinzufügen einer neuen Kante eine Vereinigungs-Operation genannt, und Anfragen werden Such-Operationen genannt.

Unser Ziel ist es, eine Funktion anzugeben, die prüfen kann, ob zwei Knoten x und y der gleichen Menge angehören (oder, bei der Darstellung als Graph, der gleichen zusammenhängenden Komponente), und die, wenn das nicht der Fall ist, die Knoten in die gleiche Menge aufnehmen kann (im Graph eine Kante zwischen ihnen erzeugen kann). Anstatt eine direkte Adjazenzliste oder eine andere Darstellung des Graphen herzustellen, wollen wir die Effizienz erhöhen, indem wir eine interne Struktur benutzen, die speziell auf die Unterstützung der Vereinigungs- und des Such-Operationen abzielt. Bei dieser internen Struktur handelt es sich um einen Wald von Bäumen, mit einem Baum für jede zusammenhängende Komponente. Wir müssen feststellen können, ob zwei Knoten zu ein und demselben Baum gehören, und in der Lage sein, zwei Bäume zu einem zu kombinieren. Es erweist sich, daß diese beiden Operationen effizient implementiert werden können.

Um zu veranschaulichen, wie dieser Algorithmus abläuft, wollen wir den Wald betrachten, der erzeugt wird, wenn die Kanten des Graphen aus dem in Abbildung 30.1 dargestellten Beispiel in der Reihenfolge AG AB AC LM JM JL JK ED FD HI FE AF GE GC GH JG JL verarbeitet werden. Die ersten sieben Schritte zeigt Abbildung 30.4. Am Anfang befinden sich alle Knoten in verschiedenen Bäumen. Dann bewirkt die Kante AG, daß ein zwei Knoten enthaltender Baum mit A an der Wurzel gebildet wird. (Diese Wahl ist willkürlich; wir hätten ebensogut G an die Wurzel setzen können.) Die Kanten AB und AC fügen in der gleichen Weise B und C diesem Baum hinzu. Danach erzeugen die Kanten LM, JM, JL und JK einen J, K, L und M enthaltenden Baum, der eine etwas andere Struktur besitzt (wir bemerken, daß JL keine Veränderung bewirkt, da LM und JM die Knoten L und J bereits in der gleichen Komponente anordnen).

Abbildung 30.4
Abbildung 30.4 Anfangsschritte der Vereinigungs-Suche.

Abbildung 30.5 zeigt die Vollendung des Prozesses. Die Kanten ED, FD und HI erzeugen zwei weitere Bäume, so daß ein Wald mit vier Bäumen vorliegt. Dieser Wald besagt, daß die bis zu diesem Moment verarbeiteten Kanten einen Graph mit vier zusammenhängenden Komponenten beschreiben, oder, was dazu äquivalent ist, daß die bis zu diesem Moment ausgeführten Vereinigungs-Operationen zu vier Mengen {A B C G}, {J K L M}, {D E F} und {H I} geführt haben. Die Kante FE ändert nun nichts an der Struktur, da F und E der gleichen Komponente angehören, doch die Kante AF kombiniert die ersten zwei Bäume; danach ändern GE und GC nichts, doch GH und JG bewirken, daß alles zu einem Baum kombiniert wird.

Abbildung 30.5
Abbildung 30.5 Vollendung der Vereinigungs-Suche.

Es muß darauf hingewiesen werden, daß im Unterschied zu Tiefensuchbäumen, der einzige Zusammenhang zwischen diesen Vereinigungs-Suchbäumen und dem ihnen zugrundeliegenden Graph mit den gegebenen Kanten darin besteht, daß sie die Knoten in der gleichen Weise in Mengen einteilen. Zum Beispiel gibt es keine Entsprechung zwischen den Pfaden, die Knoten in den Bäumen verbinden, und den Pfaden, die Knoten im Graph verbinden.

Die Vereinigungs- und Such-Operationen lassen sich sehr leicht implementieren, indem die Darstellung über die »Verkettung mit dem Vorgänger« für die Bäume verwendet wird (siehe Kapitel 4):

    function find(x,y: integer; union: boolean): boolean;
      var i,j: integer;
      begin
      i:=x; while dad[i]>0 do i:=dad[i];
      j:=y; while dad[j]>0 do j:=dad[j];
      if union and (i<>j) then dad[j]:=i;
      find:=(i<>j)
      end;

Das Feld dad[1..V] enthält für jeden Knoten den Index seines Vorgängers (mit einem Eintrag 0 für Knoten, die sich an der Wurzel eines Baumes befinden). Um den Vorgänger eines Knotens j zu finden, setzen wir einfach j:=dad[j], und um die Wurzel des Baumes zu finden, zu dem j gehört, wiederholen wir diese Operation so lange, bis wir 0 erreichen.

Die Funktion find gibt false zurück, wenn sich die beiden übergebenen Knoten in der gleichen Komponente befinden. Wenn sie nicht der gleichen Komponente angehören und das union-Flag gesetzt ist, wird bewirkt, daß sie in die gleiche Komponente kommen. Die Methode ist einfach: Benutze das Feld dad, um zur Wurzel des Baumes zu gelangen, der jeden der Knoten enthält, und prüfe dann, ob die Wurzeln identisch sind. Um den Baum mit der Wurzel j mit dem Baum mit der Wurzel i zu verknüpfen, setzen wir einfach dad[j]=i.

Abbildung 30.6 zeigt den Inhalt der Datenstruktur während dieses Prozesses. Wie gewöhnlich nehmen wir an, daß Funktionen index und name zur Verfügung stehen, um den Übergang zwischen Knotennamen und ganzen Zahlen zwischen 1 und V zu vollziehen: Jeder Eintrag in der Tabelle ist der Name des entsprechenden Eintrags im Feld dad. Zum Beispiel könnte man mit dem Funktionsaufruf find(index(x),index(y),false) prüfen, ob ein Knoten mit dem Namen x der gleichen Komponente angehört wie ein Knoten mit dem Namen y (ohne eine Kante zwischen ihnen zu erzeugen).

Abbildung 30.6
Abbildung 30.6 Datenstruktur der Vereinigungs-Suche.

Der oben beschriebene Algorithmus weist im ungünstigsten Fall ein schlechtes Verhalten auf, da die erzeugten Bäume entartet sein können. Wenn zum Beispiel die Kanten in der Reihenfolge AB BC CD DE EF FG GH HI IJ ... YZ genommen werden, wird eine lange Kette erzeugt, wobei Z auf Y zeigt, Y auf X usw. Eine derartige Struktur benötigt eine zu V2 proportionale Zeit für ihre Erzeugung, und die für eine durchschnittliche Prüfung auf Äquivalenz erforderliche Zeit ist proportional zu V.

Es wurden verschiedene Verfahren vorgeschlagen, um dieses Problem zu lösen. Eine natürliche Methode, an die der Leser vielleicht schon gedacht hat, besteht darin, zwei Bäume »besser« zu mischen, anstatt willkürlich dad[j]:=i zu setzen. Wenn ein Baum mit Wurzel i mit einem Baum mit Wurzel j gemischt werden soll, muß einer der Knoten eine Wurzel bleiben, und der andere (und alle seine Nachfolger) muß sich im Baum um eine Ebene nach unten bewegen. Um für die Mehrheit der Knoten die Entfernung zur Wurzel zu minimieren, ist es sinnvoll, als Wurzel denjenigen Knoten zu nehmen, der mehr Nachfolger hat. Diese Idee, die Ausgleichen des Gewichts (weight balancing) genannt wird, läßt sich leicht implementieren, indem man die Größe jedes Baumes (Anzahl von Nachfolgern der Wurzel) in den Eintrag im Feld dad eines jeden Wurzelknotens speichert. Zur Kodierung der Baumgröße verwendet man nichtpositive Zahlen, so daß der Wurzelknoten entdeckt werden kann, wenn in find im Baum aufwärts gegangen wird.

Als Idealfall würden wir wünschen, daß jeder Knoten direkt auf die Wurzel seines Baumes zeigt. Doch gleichgültig, welche Strategie wir benutzen: Die Realisierung dieses Idealfalls würde es erfordern, wenigstens alle Knoten in einem der beiden zu mischenden Bäume zu betrachten. Dies könnten jedoch sehr viele sein, im Vergleich zu den relativ wenigen Knoten auf dem Pfad zur Wurzel, die find gewöhnlich prüft. Doch wir können uns dem Idealzustand nähern, indem wir alle Knoten, die wir prüfen, auf die Wurzel zeigen lassen! Dies scheint auf den ersten Blick ein drastischer Schritt zu sein, doch er läßt sich leicht verwirklichen, und die Struktur dieser Bäume ist wirklich nichts Unantastbares; wenn sie so modifiziert werden können, daß der Algorithmus effizienter wird, sollten wir das tun. Dieses Pfadverdichtung (path compression) genannte Verfahren läßt sich leicht implementieren, indem jeder Baum, nachdem die Wurzel gefunden worden ist, nochmals durchlaufen wird und der Eintrag im Feld dad für jeden Knoten, der längs des Weges angetroffen wird, so gesetzt wird, daß er auf die Wurzel zeigt.

Die Kombination des Gewichtausgleichens und der Pfadverdichtung gewährleistet, daß der Algorithmus sehr schnell abläuft. Die folgende Implementation zeigt, daß der erforderliche zusätzliche Programmieraufwand ein kleiner Preis ist, um entarteten Fällen vorzubeugen.

    function find(x,y: integer; union: boolean): boolean;
      var i,j,t: integer;
      begin
      i:=x; while dad[i]>0 do i:=dad[i];
      j:=y; while dad[j]>0 do j:=dad[j];
      while dad[x]>0 do
        begin t:=x; x:=dad[x]; dad[t]:=i end;
      while dad[y]>0 do
        begin t:=y; y:=dad[y]; dad[t]:=j end;
      if union and (i<>j) then
        if dad[j]<dad[i]
          then begin dad[j]:=dad[j]+dad[i]-1; dad[i]:=j end
          else begin dad[i]:=dad[i]+dad[j]-1; dad[j]:=i end;
      find:=(i<>j)
      end;

Abbildung 30.7
Abbildung 30.7 Anfangsschritte der Vereinigungs-Suche (gewichtet, mit Pfadverdichtung).

Es wird angenommen, daß das Feld dad mit 0 initialisiert ist. (In den folgenden Kapiteln setzen wir voraus, daß das in einer getrennten Prozedur findinit erfolgt.) Abbildung 30.7 zeigt die ersten acht Schritte, wenn dieses Verfahren auf die Daten aus unserem Beispiel angewandt wird, und Abbildung 30.8 zeigt die Vollendung des Prozesses. Die durchschnittliche Pfadlänge des resultierenden Baumes beträgt 31/13 rund 2,38, im Vergleich zu 38/13 rund 2,92 für Abbildung 30.5. Für die ersten fünf Kanten ist der sich ergebende Wald der gleiche wie in Abbildung 30.4; die letzten drei Kanten ergeben jedoch aufgrund der Regel des Gewichtausgleichens einen »flachen« Baum, der J, K, L und M enthält. Die Wälder sind in diesem Beispiel tatsächlich so flach, daß sich alle Knoten, die an Vereinigungs-Operationen beteiligt sind, an der Wurzel oder unmittelbar darunter befinden; Pfadverdichtung kommt nicht zur Anwendung. Pfadverdichtung könnte zu noch flacheren Bäumen führen: Wenn zum Beispiel die letzte Vereinigung FJ anstelle von GJ beträfe, so wäre am Ende F gleichfalls ein Nachfolger von A.

Abbildung 30.8
Abbildung 30.8 Vollendung der Vereinigungs-Suche (gewichtet, mit Pfadverdichtung).

Abbildung 30.9 zeigt den Inhalt des Feldes dad während der Erzeugung dieses Waldes. Um diese Tabelle anschaulicher zu gestalten, wurde jeder positive Eintrag i durch den i-ten Buchstaben des Alphabets (den Namen des Vorgängers) ersetzt, und jeder negative Eintrag wurde durch die komplementäre positive ganze Zahl (das Gewicht des Baumes) ersetzt.

Abbildung 30.9
Abbildung 30.9 Datenstruktur der Vereinigungs-Suche (gewichtet, mit Pfadverdichtung).

Um entartete Strukturen zu vermeiden, wurden noch verschiedene andere Methoden entwickelt. Zum Beispiel hat Pfadverdichtung den Nachteil, daß ein weiterer Durchlauf durch den Baum nach oben erforderlich ist. Eine andere Methode, die Halbierung (halving) genannt wird, bewirkt, daß jeder Knoten auf seinen vorletzten Vorgänger auf dem Weg im Baum nach oben zeigt. Ein weiteres Verfahren, Aufspaltung (splitting), läuft wie die Halbierung ab, wird aber nur auf jeden zweiten Knoten auf dem Suchpfad angewandt. Jede dieser Methoden kann in Kombination mit dem Ausgleichen des Gewichts benutzt werden, oder mit dem Ausgleichen der Höhe (height balancing), das ähnlich ist, jedoch die Höhe des Baumes anstelle der Größe des Baumes verwendet, um zu entscheiden, in welcher Weise Bäume zu mischen sind.

Wie soll man unter all diesen Verfahren eine Wahl treffen? Und exakt wie »flach« werden die erzeugten Bäume? Die Analyse dieses Problems ist sehr kompliziert, da die Leistungsfähigkeit nicht nur von den Parametern V und E abhängt, sondern auch von der Anzahl der Such-Operationen und, was noch schlimmer ist, von der Reihenfolge, in der die Operationen union und find auftreten. Anders als beim Sortieren, wo die in der Praxis tatsächlich auftretenden Dateien sehr oft annähernd »zufällig« sind, ist es schwer zu sagen, wie Graphen und Anforderungen, die in der Praxis auftreten könnten, modelliert werden sollten. Aus diesem Grunde werden Algorithmen, die sich im ungünstigsten Fall gut verhalten, normalerweise als Vereinigungs-Such-Algorithmen (und als andere Algorithmen für Graphen) bevorzugt, auch wenn dies ein übervorsichtiger Ansatz sein mag.

Selbst wenn nur der ungünstigste Fall betrachtet wird, ist die Analyse von Vereinigungs-Such-Algorithmen äußerst komplex und schwierig. Dies ergibt sich schon aus der Natur der Ergebnisse, welche uns dennoch eine klare Vorstellung davon geben, wie sich die Algorithmen in einer praktischen Situation verhalten.

Eigenschaft 30.2 Falls entweder das Ausgleichen des Gewichts oder das Ausgleichen der Höhe in Kombination mit Verdichtung, Halbierung oder Aufspaltung verwendet wird, so ist die Gesamtzahl der Operationen, die erforderlich sind, um unter Verwendung von E Kanten eine Struktur zu erzeugen, nahezu (doch nicht ganz) linear.

Die Anzahl der erforderlichen Operationen ist exakt proportional zu E Alpha (E), wobei Alpha (E) eine Funktion ist, die derart langsam wächst, daß Alpha (E) < 4 ist, es sei denn, E ist so groß, daß lg16 E (also 16-malige Anwendung von lg auf E) immer noch größer als 1 ist. Dies ist eine unvorstellbar große Zahl; für alle praktischen Zwecke kann man mit Sicherheit annehmen, daß die durchschnittliche Zeit für die Ausführung jeder Operation find und union konstant ist. Dieses Ergebnis stammt von R. E. Tarjan, der außerdem zeigte, daß kein Algorithmus für dieses Problem (aus einer gewissen allgemeinen Klasse) besser sein kann als E Alpha (E), so daß diese Funktion für das Problem charakteristisch ist. w.z.b.w.

Eine wichtige praktische Anwendung von Vereinigungs-Such-Algorithmen besteht darin, mit einem zu V proportionalen Aufwand an Platz (und in nahezu linearer Zeit) zu bestimmen, ob ein Graph mit V Knoten und E Kanten zusammenhängend ist. Dies ist in manchen Situationen ein Vorteil gegenüber der Tiefensuche: Hier brauchen wir die Kanten nicht im Speicher zu halten. Somit kann der Zusammenhang eines Graphen mit Tausenden von Knoten und Millionen von Kanten mit einem schnellen Durchlauf durch die Kanten bestimmt werden.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]