# Tarjan-Dekomposition stark zusammenhängender Komponenten, Brücken und Artikulationspunkte mit topologischer Ordnung Eingabe: Kantenliste (a b / a -> b, mit optionalem Gewicht) oder Adjazenz (a: b c): Der iterative Tarjan-Algorithmus (1972) und Kosarajus Doppeldurchlauf zerlegen die stark zusammenhängenden Komponenten mit Gegenprüfung; Ausgabe: Artikulationspunkte und Brücken, Kondensations-DAG mit Kahn-Topologie, Zyklusbericht und BFS/DFS-Durchläufe mit Tiefenbegrenzung. > Kanonische Seite: https://elysiatools.com/de/tools/tarjan-scc-tarjan-bridge-and-strongly-connected-components-topological-order-graph-decomposer - **Kategorie:** Development - **Schlagwörter:** Tarjan, stark zusammenhängende Komponenten, Kosaraju, Artikulationspunkte, Brücken, Kondensation, topologische Sortierung, Zyklenerkennung ## Überblick Tarjan-SCC läuft iterativ mit explizitem Stack (disc/low-Arrays, Sammeln beim Abladen); Kosaraju sortiert nach Finish-Zeit und sammelt auf dem umgekehrten Graphen — beide müssen komponentenweise übereinstimmen (Gegenprüfung). Brücken und Artikulationspunkte folgen dem Low-Link auf der ungerichteten Sicht: low[v] > disc[u] ⟹ Brücke; Wurzel mit ≥2 Teilbäumen oder low[v] ≥ disc[u] ⟹ Artikulation. Die Kondensation baut den Komponenten-DAG, Kahn liefert die Topologie; eine vollständige Ordnung existiert genau bei Zyklusfreiheit (Knoten auf Zyklen = SCC der Größe > 1 ∪ Schleifen). BFS schichtweise, DFS mit explizitem Stack, beide durch maxDepth begrenzt. Komplexität O(V+E). ## Eingaben - **Graph (Kantenliste oder Adjazenz, eine pro Zeile)** (textarea): a -> b b -> c c -> a d -> c - **Gerichteter Graph** (checkbox) - **Startknoten** (text): a - **Maximale Tiefe** (number): 4 ## Wann verwenden - Wenn Sie zirkuläre Abhängigkeiten in Software-Modulen, Build-Pipelines oder Datenbankrelationen aufspüren und isolieren müssen. - Wenn Sie kritische Schwachstellen wie Brücken oder Artikulationspunkte (Single Points of Failure) in Netzwerkstrukturen identifizieren möchten. - Wenn Sie einen azyklischen Kondensations-DAG mit gültiger topologischer Ausführungsreihenfolge aus einem zyklischen Graphen ableiten wollen. ## Funktionsweise - Graphdaten werden als Kantenliste (z. B. 'a -> b' oder 'a b') oder Adjazenzliste ('a: b c') zeilenweise eingelesen und als Adjazenzstruktur aufgebaut. - Der iterative Tarjan-Algorithmus ermittelt stark zusammenhängende Komponenten über Discovery- und Low-Link-Indizes mit explizitem Stack und gleicht die Ergebnisse komponentenweise mit Kosarajus Vorwärts-/Rückwärtsdurchlauf ab. - Über die ungerichtete Tiefensuche werden Schnittknoten (Artikulationspunkte) und Schnittkanten (Brücken) anhand der Low-Link-Bedingungen berechnet. - Das Tool fasst Komponenten zu einem Kondensations-DAG zusammen, ermittelt per Kahn-Algorithmus die topologische Reihenfolge und liefert BFS-/DFS-Pfade bis zur gewählten Maximaltiefe. ## Anwendungsfälle - Analyse von Software-Architekturen zur Auflösung zyklischer Importe und Ermittlung stabiler Modul-Build-Reihenfolgen. - Topologische Strukturprüfung von Prozessabläufen und CI/CD-Pipelines zur Validierung von Abhängigkeitsketten. - Zuverlässigkeitsanalyse von Kommunikationsnetzen zur Lokalisierung von Single Points of Failure (Brücken und Artikulationspunkte). ## Häufig gestellte Fragen ### Welche Eingabeformate für Graphen werden unterstützt? Sie können Kantenlisten (z. B. 'a -> b', 'a b', optional mit Gewichten) oder Adjazenzlisten im Format 'a: b c' zeilenweise eintragen. ### Warum werden sowohl Tarjan als auch Kosaraju ausgeführt? Beide Algorithmen ermitteln stark zusammenhängende Komponenten unabhängig voneinander, was eine automatische algorithmische Gegenprüfung der Komponentenzerlegung ermöglicht. ### Wann besitzt ein Graph eine vollständige topologische Sortierung? Eine vollständige topologische Ordnung existiert nur dann, wenn der Graph vollkommen zyklenfrei ist (DAG); andernfalls wird die Topologie auf dem Kondensations-DAG berechnet. ### Wie werden Artikulationspunkte und Brücken berechnet? Sie werden über Low-Link- und Discovery-Zeit-Vergleiche in einer Tiefensuche auf der ungerichteten Sicht des Graphen identifiziert. ### Welche Auswirkung hat der Parameter 'maxDepth'? Er begrenzt die Suchtiefe der vom angegebenen Startknoten ausgehenden Breitensuche (BFS) und Tiefensuche (DFS). ## Ähnliche Tools - [Cron-Ausdruck-Visualisierer](https://elysiatools.com/de/tools/cron-expression-visualizer): Analysiert Cron-Zeitplaene, validiert Standard- oder Quartz-Syntax und visualisiert kommende Ausfuehrungen auf Zeitachse und gruppierter Kalenderansicht - [Tailwind-Farbpaletten-Sync](https://elysiatools.com/de/tools/tailwind-color-palette-sync): Gib HEX ein, wähle Namensschema (Skala 50–950 / Einzelname / Verschachtelung) und generiere das theme.extend.colors-Fragment für tailwind.config.ts mit WCAG AA/AAA-Leveln. Dark Mode optional. - [Cron-Ausdruck-Erklärer](https://elysiatools.com/de/tools/cron-expression-explainer): Zerlegt einen Cron-Ausdruck (5/6 Felder oder Quartz) in eine Beschreibung in natürlicher Sprache, zeigt die Felder und die nächsten N Ausführungen in jeder IANA-Zone, mit KI-Erklärung - [Cron-Job-Simulator](https://elysiatools.com/de/tools/cron-job-simulator): Simuliert zukuenftige Ausfuehrungen von einem oder zwei 5-teiligen Cron-Ausdruecken und markiert Ueberlappungen sowie zu dichte Plaene. - [API-Contract-Mutation-Tester](https://elysiatools.com/de/tools/api-contract-mutation-tester): Fuehrt semantische Mutationen auf OpenAPI-Feldern aus und sendet sie optional an ein echtes Backend, um die defensive Validierung zu pruefen - [CSV-Chirurg für fehlerhafte Zeilen](https://elysiatools.com/de/tools/csv-malformed-row-surgeon): Repariert fehlerhafte CSV-Zeilen chirurgisch einzeln: nicht escapete (stragglinge) Anführungszeichen, gemischte Trennzeichen (Tabulator/Semikolon/Komma in derselben Datei), BOM-präfixierte Kopfzeilen, CRLF/CR-Zeilenumbrüche und leere Zeilen. Der Chirurg parst tolerant, zeigt einen zeilenweisen Rot/Grün-Diff jeder Änderung (vor → nach, mit markiertem Reparaturgrund), listet die unverändert akzeptierten Zeilen und gibt die bereinigte CSV aus. Die optionale KI-Reparatur kann verdächtige Zeilen nach dem deterministischen Durchlauf erneut prüfen. Er ergänzt den CSV-Validator (der nur Probleme meldet), indem er die beschädigten Zeilen tatsächlich repariert. - [OAuth-2.0-/OIDC-Autorisierungscode-mit-PKCE-Ablaufvisualisierer](https://elysiatools.com/de/tools/oauth-oidc-authorization-code-pkce-flow-visualizer): Simuliert den Autorisierungscode-Ablauf mit PKCE vollständig: Verifier/Challenge-Erzeugung, Autorisierungs-URL, Token-Austausch, ID-Token-Prüfcheckliste und eine Abfangangriffs-Demo. - [Responsive Picture / srcset Art-Direction-Builder](https://elysiatools.com/de/tools/responsive-picture-srcset-art-direction-builder): Erzeugt vollständiges \-Markup mit Art-Direction-Zuschnitten: \-Elemente je Breakpoint, 1x/2x-Kandidaten oder Breitendeskriptoren per {w}-Vorlage, optionale AVIF/WebP-Schichten, sizes-Behandlung, CLS-sicheres width/height sowie HTML- und JSX-Varianten mit spec-basierten Lint-Hinweisen. ## Beispiele - [FLAC Audio-Beispiele ohne Urheberrechte](https://elysiatools.com/de/samples/flac-samples): Sammlung verlustfreier FLAC-Audios für Tests und Entwicklung, einschließlich Naturklänge und Meditationsmusik - [WAV Audio-Beispiele ohne Urheberrechte](https://elysiatools.com/de/samples/wav-samples): Sammlung unkomprimierter WAV-Audios für Tests und Entwicklung, einschließlich Naturklänge und Meditationsmusik - [Android Java Bildverarbeitungsbeispiele](https://elysiatools.com/de/samples/android-image-processing-java): Android Java Bildverarbeitungsbeispiele einschließlich Lesen/Schreiben, Skalierung und Formatkonvertierung - [Android Kotlin Bildverarbeitungsbeispiele](https://elysiatools.com/de/samples/android-image-processing-kotlin): Android Kotlin Bildverarbeitungsbeispiele einschließlich Lesen/Schreiben, Skalierung und Formatkonvertierung