Algorithm for finding strongly connected components using DFS

What is the time complexity of Tarjan SCC?

The time complexity of Tarjan SCC is O(V + E).

What are the applications of Tarjan SCC?

Tarjan SCC is commonly used for: Social network analysis, Compiler optimization, Web crawling.

What difficulty level is Tarjan SCC?

Tarjan SCC is considered advanced level in graph theory and algorithms.

learngraphtheory.org

Interaktives Graphentheorie-Lernen

learngraphtheory.org

Interaktives Graphentheorie-Lernen

Guest User

Using app without sign in

Algorithmusauswahl

Dieser Algorithmus benötigt einen gerichteten Graphen. Überprüfen Sie die Einstellungen, um zu konfigurieren.

Algorithmuskategorie

Algorithmus wählen

Tarjan SCC-Algorithmus

Findet stark zusammenhängende Komponenten mit DFS und Stack

Zeit: O(V + E)

Speicher: O(V)

Anwendungsfall: Abhängigkeitsanalyse, soziale Netzwerkanalyse

Startknoten

Automatisch abspielenKomplexität anzeigen

Algorithmusausführung

Wählen Sie einen Algorithmus und generieren Sie Schritte, um die Visualisierung zu beginnen

Über Tarjan SCC-Algorithmus

Findet stark zusammenhängende Komponenten mit DFS und Stack.

Anwendungsfall: Abhängigkeitsanalyse, soziale Netzwerkanalyse

Den ganzen Artikel lesen: Graph Algorithms and Their Complexity

Verwandte Algorithmen: Kosaraju SCC-Algorithmus, Tiefensuche, Topologische Sortierung

Interaktive Steuerung

Grundaktionen

• Doppelklick → Knoten hinzufügen

• Ziehen → Knoten bewegen

• Umschalt + Klick → Knoten verbinden

• Rechtsklick → Kontextmenü

Erweitert

• Strg + Klick → Mehrfachauswahl

• Entf-Taste → Ausgewählte entfernen

• Doppelklick Kante → Gewicht bearbeiten

• Strg + Ziehen → Ansicht schwenken

Zoom Controls

Ctrl + / -

100%

Zoom:Ctrl + / -

Reset:Ctrl + 0

Toggle:Ctrl + Shift + Z

Knoten: 4

Kanten: 4

Knoten-InfoKantenflussIntelligentes Aufräumen