Zusammenhangskomponenten (Algorithmus 4.3)

So geht’s: Beim Öffnen läuft der Testclient mit dem Graphen tinyG aus dem Buch: erst entsteht der Graph Kante für Kante, dann arbeitet der Konstruktor. Seine for-Schleife geht die Knoten der Reihe nach durch (gestrichelt umrandet, Marke „s“). Trifft sie auf einen unmarkierten Knoten, startet dort eine Tiefensuche – Aufruf für Aufruf wie bei der Tiefensuche, orange der laufende Aufruf, orange umrandet die wartenden, blau der Nachbar, der gerade geprüft wird. Jeder erreichte Knoten bekommt id[v] = count und die Farbe seiner Komponente; ist die Suche fertig, zählt count++ weiter. „Bis fertig“ springt jeweils bis zum Ende einer Komponente. Am Ende sammelt der Testclient die Knoten in Bags und gibt sie aus – rückwärts, wie im Buch. Oben lässt sich mit connected(v, w) jede Frage stellen oder ein Zufallsgraph erzeugen, der meist in mehrere Teile zerfällt. „↺ Neu starten“ lädt den Testclient neu.

Erklärung

Zusammenhangskomponenten (Algorithmus 4.3), Klasse CC (connected components). Frage: In welche unabhängigen Teile zerfällt der Graph, und liegen zwei Knoten im selben Teil?

Der Code:

• marked[]: besucht oder nicht.
• id[]: Nummer der Komponente für jeden Knoten.
• count: Anzahl der Komponenten bisher.
• Konstruktor: Alle Knoten der Reihe nach durchgehen. Trifft man auf einen unmarkierten, startet man von dort eine Tiefensuche und zählt danach count hoch.
• dfs(G, v): wie in [30], nur dass statt edgeTo jetzt id[v] = count gesetzt wird. Jeder Knoten, den diese Suche erreicht, bekommt die aktuelle Komponentennummer.
• connected(v, w): id[v] == id[w]. Genau wie bei Union-Find [19].

Das Beispiel tinyG.txt (13 Knoten, 13 Kanten):

• Tiefensuche ab 0 erreicht 0 bis 6 → alle bekommen id 0.
• Nächster unmarkierter ist 7 → erreicht 7 und 8 → id 1.
• Nächster unmarkierter ist 9 → erreicht 9 bis 12 → id 2.
• Ergebnis: 3 Komponenten.
• Die Ausgabe zeigt die Knoten jeder Komponente rückwärts (6 5 4 3 2 1 0), weil der Testclient sie in Bags [17] sammelt und add immer vorne einfügt.

Satz C: Vorverarbeitung in Zeit und Speicher proportional zu V + E. Danach beantwortet connected() jede Anfrage in konstanter Zeit.

CC vs. Union-Find [19], [21]: Beide lösen dasselbe Problem mit derselben id[]-Idee, aber in unterschiedlichen Situationen.

Faustregel aus dem Buch: Graph fest und viele Anfragen → CC. Graph wächst laufend → Union-Find. In der Praxis ist Union-Find oft schneller, weil kein vollständiger Graph aufgebaut werden muss.

Stand Kapitel 4:

• Algorithmus 4.1: Tiefensuche für Pfade [30]
• Algorithmus 4.2: Breitensuche für kürzeste Pfade [31]
• Algorithmus 4.3: Zusammenhangskomponenten [32]