Starke Zusammenhangskomponente PDF

Preview

Summary

* Lehrveranstaltung von Professor Sanders
* Dozent: Simon Gog
* Wintersemester...

Description

Zusammenfassung - Starke Zusammenhangskomponente Tiefensuche    

Bei mehreren Source-Knoten, hintereinander prüfen Funktioniert auch bei Dependency-Graphs Rückkante bedeutet Zyklus!

O(|V |+| E|)

Starke Zusammenhangskomponente G heißt stark zusammenhängend, falls es zwischen zwei beliebigen Knoten u und v aus G sowohl einen gerichteten Weg von u nach v wie auch einen gerichteten Weg von v nach u gibt. Kurz: Man muss von jedem Knoten zu jedem anderen Knoten kommen!  

Finden sich in einem Graphen nur triviale SCCs (mit nur einem Knoten), ist der Graph frei von Zyklen Schrumpfgraph mit nur einem Knoten ohne eingehende Kanten -> Von den Knoten in dieser SCC sind alle anderen Knoten erreichbar

Der Schrumpfgraph (rechts) enthält keine Zyklen mehr (azyklisch!), Knoten sind SCCs.

Algorithmus  



 

Führt eine Tiefensuche (DFS) auf dem Graphen aus Stacks o oReps: Repräsentanten offener Komponenten o oNodes: Alle offenen Knoten Invarianten o Keine Kanten von geschlossenen in offene Komponenten o Offene Komponenten liegen auf Pfad o Repräsentanten partitionieren offene Komponenten bzgl. dfsNum Kreise vereinigen alle auf dem Kreis liegenden offenen Komponenten Komponenten werden nach Bearbeitung aller ausgehenden Kanten geschlossenen

Beispiel...