Robert Sedgewick: Algorithmen

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


30. Zusammenhang



Zusammenhängende Komponenten

Für das Auffinden der zusammenhängenden Komponenten eines Graphen kann jedes Graphen-Traversierungsverfahren aus dem vorangegangenen Kapitel benutzt werden, da sie alle auf der gleichen allgemeinen Strategie beruhen, alle Knoten in einer zusammenhängenden Komponente zu besuchen und sich dann zur nächsten zu begeben. Ein einfacher Weg, um die zusammenhängenden Komponenten auszudrucken, besteht darin, eines der rekursiven Programme für die Tiefensuche so zu modifizieren, daß man visit den Knoten ausdrucken läßt, der gerade besucht wird (etwa durch Einfügen von write (name(k)) unmittelbar vor dem Verlassen der Schleife), und daß man dann unmittelbar vor dem (nichtrekursiven) Aufruf von visit in dfs einen Hinweis darauf ausdruckt, daß nun eine neue Komponente beginnt (etwa durch Einfügen von zwei writeln-Anweisungen). Diese Methode würde, wenn dfs auf die Adjazenzlistendarstellung des Graphen aus unserem Beispiel (Abbildung 29.1) mittels Adjazenzliste angewandt würde, die folgende Ausgabe bewirken:

G D E F C B A
I H
K M L J

Andere Varianten, wie etwa die Adjazenzmatrix-Variante von visit, stapelbasierte Tiefensuche und Breitensuche, können (selbstverständlich) die gleichen zusammenhängenden Komponenten berechnen, doch die Knoten werden in einer anderen Reihenfolge ausgedruckt.

Erweiterungen mit dem Ziel, kompliziertere Operationen mit den zusammenhängenden Komponenten vorzunehmen, sind sehr einfach. Zum Beispiel erhalten wir, indem wir einfach inval[id]=k nach val[k]=id einfügen, das zum Feld val »inverse« Feld, dessen id-te Eintragung der Index des id-ten besuchten Knotens ist. Knoten in den gleichen zusammenhängenden Komponenten sind in diesem Feld benachbart, wobei der Index jeder neuen zusammenhängenden Komponente jedesmal, wenn visit in dfs aufgerufen wird, durch den Wert von id gegeben ist. Diese Werte können gespeichert werden, oder sie können benutzt werden, um Begrenzer in inval zu markieren (zum Beispiel könnte der erste Eintrag jeder zusammenhängenden Komponente negiert werden).

Abbildung 30.1
Abbildung 30.1 Datenstrukturen für zusammenhängende Komponenten.

Abbildung 30.1 zeigt die Werte, die diese Felder für unser Beispiel enthalten würden, wenn die Adjazenzlisten-Variante von dfs derart modifiziert würde. Gewöhnlich lohnt es sich, solche Methoden anzuwenden, um einen Graph für die spätere Verarbeitung mit Hilfe komplizierterer Algorithmen in seine zusammenhängenden Komponenten zu zerlegen, um diese Algorithmen von den Einzelheiten der Behandlung nicht zusammenhängender Komponenten zu befreien.


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