3

EA (Subject) / EA Foliensatz 2 (Lesson)

This lesson was created by blumenkohl.

Learn lesson

This lesson is not released for learning.

back  |  next 1 / 1

• Kantenklassifikation Baum-Kanten (T): Kanten, denen die Tiefensuche folgt Rückwärtskanten (B): Kanten von einem DFS-Knoten v zu einem Vorgänger von v im DFS-Baum. Vorwärtskanten (F): Kanten von v zu einem bereits erreichten Nachfolgerknoten w. Querkanten (C): alle anderen Kanten.
• Definition - Starker Zusammenhang Sei G = (V,E) ein gerichteter Graph. Gibt es einen gerichteten Weg von v nach w (mit v,w &isin; V), so schreiben wir v -> w. Gilt v -> w und w -> v, so schreiben wir v <-> w. Zwei Knoten v,w &isin; V heißen stark zusammenhängend, wenn v <-> w gilt. Die Äquivalenzklassen von V bezüglich <-> heißen starke Zusammenhangskomponenten.  
• Algorithmus von Kosaraju 1. Führe DFS-Traversierung von G = (V, E) durch, vergib dabei in absteigender Reihenfolge die f -Nummern n, n − 1, . . . , 1an die Knoten. Knoten v ∈ V erhält seine f -Nummer beim Abschluss des Aufrufs von DFS(v).2. Berechne G* := (V, E*) mit E* := {(w, v) | (v, w) ∈ E}.3. Führe DFS-Traversierung von G* durch, durchlaufe dabei im Rahmenalgorithmus die Knoten v ∈ V in Reihenfolge aufsteigender f -Nummern, Start in Knoten v mit f [v] = 1.4. Gib die T -Bäume der zweiten DFS-Traversierung als starke Zusammenhangskomponenten aus. Laufzeit: O(|V| + |E|)

back  |  next 1 / 1