- Repräsentant : Wert des kleinsten Knotens
Bestimmung von schwachen Zusammenhangskompnenten
Naiver Algorithmus
-
wir nutzen die Transitivität der Erreichbarkeit in unserem Graphen aus
-
Wir starten mit einem Knoten
-
Wir schauen zu welchen anderen Knoten dieser verbunden ist
-
Wir setzen die repräsentanten von allen Verbundenen Knoten gleich dem repräsentanten von dem Knoten mit dem wir angefangen haben
Wir erhalten die Laufzeit :
Zusammenhangskomponenete mittels Tiefensuche :
-
Wir führen auf dem Graphen eine Tiefensuche aus
-
mit dem Array ==rep[]== merken wir uns, von welchem Knoten aus der Knoten entdeckt und abgearbeitet worden ist.
Wir erhalten die Laufzeit :
-
Diese Laufzeit ist besser, als die von dem Naiven Algorithmus
5.2 Starke Zusammenhangskomponenten
- bei gerichteten Graphen
Algorithmus von Kosaraju
-
wir bestimmen die starken ZHK eines gerichteten Graphs mittels der Tiefensuche
-
Hierbei Transponiert : Kanten umdrehen
-
Transponierten Graph bestimmen und Tiefensuche ausführen
-
Ordne die Knoten des Graphen in ==absteigender Reihenfolge== ihrer Endzeitpunkte aus Schritt 1
-
Führe die Tiefensuche auf dem ursprünglichen Graphen durch, und betrachte hierbei die Knoten gemäß der Reihenfolge aus Schritt 2 als Startknoten
Die
==Tiefensuchbäume der ganzehitlichen Tiefensuche in Schritt 3 entsprechen dann den starken ZHK== des gerichteten Graphen
Zu
2 : Wir können das in absteigender Reihenfolge vereinfachen, in dem wir ein Array ==ord[]== mitverfolgen.
Es funktioniert wie folgt : wird ein Knoten schwarz gefärbt, so notieren wir ihn an der nächsten freien Position im Array
Nach Beendung der DFS stehen die Knoten in ==aufsteigender== ==Reihenfolge== ihrer ==Endzeitpunkte== im neuen Array ==ord==
