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).

Tarjan-Dekomposition stark zusammenhängender Komponenten, Brücken und Artikulationspunkte mit topologischer Ordnung | Kostenloses Online-Tool

Tarjan-Dekomposition stark zusammenhängender Komponenten, Brücken und Artikulationspunkte mit topologischer Ordnung | Kostenloses Online-Tool | Elysia Tools

Beispiele

1. Erkennung starker Komponenten und Kondensation in zyklischer Modulstruktur

Software-Architekt

Hintergrund

Ein Softwaresystem weist komplexe zyklische Modulabhängigkeiten auf, die das Build-System blockieren.

Aufgabe

Zirkuläre Komponenten müssen gruppiert und der verbleibende gerichtete Graph topologisch geordnet werden.

Verwendung

Geben Sie die Modulaufrufe zeilenweise mit Pfeilsyntax ein, aktivieren Sie die Option für gerichtete Graphen und setzen Sie den Einstiegsknoten.

graphInput: a -> b\nb -> c\nc -> a\nc -> d\nd -> c\ne -> a\nf -> e\nf -> g\ng -> f
directed: true
startNode: a
maxDepth: 2

Ergebnis

Das Werkzeug identifiziert 3 SCCs ({a,b,c,d}, {f,g}, {e}), bestätigt Übereinstimmung zwischen Tarjan und Kosaraju und gibt die topologische Reihenfolge des Kondensations-DAGs (2 -> 1 -> 0) aus.

2. Schwachstellenanalyse in einem ungerichteten Rechnernetzwerk

Netzwerk-Ingenieur

Hintergrund

Ein lokales Firmennetzwerk soll auf kritische Verbindungsknoten und anfällige Leitungen hin überprüft werden.

Aufgabe

Ausfallgefährdete Verbindungsglieder (Brücken) und Schnittstellenknoten müssen exakt bestimmt werden.

Verwendung

Tragen Sie die Netzwerkverbindungen ungerichtet zeilenweise ein und deaktivieren Sie das Häkchen für gerichtete Graphen.

graphInput: a b\nb c\nc d\nd e
directed: false
startNode: a
maxDepth: 3

Ergebnis

Die Knoten b, c und d werden als Artikulationspunkte identifiziert, alle 4 Kanten als Brücken ausgewiesen und die BFS-Erreichbarkeit ab Knoten 'a' bis Tiefe 3 aufgelistet.

Tarjan-Dekomposition stark zusammenhängender Komponenten, Brücken und Artikulationspunkte mit topologischer Ordnung

Wobei dieses Tool hilft

Dieses Tool ausführen

Beispiele zu diesem Tool

Mit verwandten Tools und Themen fortfahren

Erfahren Sie, wann dieses Tool passt, was es unterstützt und wie Nutzer es anwenden.

Wichtige Fakten

Überblick

Wann verwenden

So funktioniert es

Anwendungsfälle

Beispiele

1. Erkennung starker Komponenten und Kondensation in zyklischer Modulstruktur

2. Schwachstellenanalyse in einem ungerichteten Rechnernetzwerk

FAQ

FLAC Audio-Beispiele ohne Urheberrechte

WAV Audio-Beispiele ohne Urheberrechte

Android Java Bildverarbeitungsbeispiele

Android Kotlin Bildverarbeitungsbeispiele

Cron-Ausdruck-Visualisierer

Tailwind-Farbpaletten-Sync

Cron-Ausdruck-Erklärer

Cron-Job-Simulator