Algorithmen und Datenstrukturen · Senior · Frage 34 von 75
Was berechnet der Algorithmus von Tarjan oder Kosaraju?
- 1Kürzeste Wege mit negativen Kantengewichten
- 2Den maximalen Fluss zwischen zwei Knoten
- 3Starke Komponenten eines gerichteten Graphen
Antwort zeigen
Richtige Antwort: Starke Komponenten eines gerichteten Graphen
Erklärung
Eine starke Zusammenhangskomponente ist eine Gruppe, in der jeder Knoten jeden anderen erreicht. Beide Algorithmen laufen mit DFS in O(V + E). Fasst man SCCs zusammen, wird jeder gerichtete Graph zu einem DAG, nützlich für die Analyse von Abhängigkeiten.