Stark zusammenhängende Komponenten
Gruppieren Sie mit Tarjan gegenseitig erreichbare Knoten
Stark zusammenhängende Komponenten ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was eine SCC ist
Eine stark zusammenhängende Komponente ist eine maximale Gruppe von Knoten, in der jeder Knoten jeden anderen über gerichtete Kanten erreichen kann.
Warum das wichtig ist
Wenn Sie jede SCC zu einem Superknoten zusammenfassen, wird aus jedem gerichteten Graphen ein DAG. Dadurch lassen sich gegenseitige Abhängigkeiten leicht nachvollziehen.
Tarjan in einem Durchlauf
Tarjans Algorithmus findet jede SCC in einer einzigen DFS. Er läuft in O(V + E), also mit den gleichen Kosten wie ein einfacher Durchlauf.
Entdeckungsnummern
Geben Sie jedem Knoten eine Entdeckungszeit entsprechend der Reihenfolge, in der DFS ihn erstmals besucht. Anhand dieser IDs können Sie vergleichen, welcher Knoten früher entdeckt wurde.
disc = [-1] * n
timer = 0Der Low-Link-Wert
Der Low-Link-Wert eines Knotens ist die kleinste von ihm erreichbare Entdeckungs-ID, auch über Rückwärtskanten. Er verankert die Komponente.
low = [-1] * nAuf den Stack legen
Wenn DFS einen Knoten betritt, setzen Sie dessen disc und low und legen ihn anschließend auf einen Stack mit Knoten, die möglicherweise zu seiner Komponente gehören.
disc[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = Truelow aus den Kindknoten aktualisieren
Nach dem rekursiven Aufruf für einen unbesuchten Kindknoten übernehmen Sie dessen low-Wert nach oben: low[u] wird zum Minimum aus seinem bisherigen Wert und dem low-Wert des Kindes.
dfs(v)
low[u] = min(low[u], low[v])Rückwärtskanten behandeln
Wenn sich ein Nachbar bereits auf dem Stack befindet, ist er ein Vorfahr in dieser SCC. Verwenden Sie dessen disc, um low[u] zu verringern.
elif on_stack[v]:
low[u] = min(low[u], disc[v])Die Wurzel einer Komponente erkennen
Wenn low[u] gleich disc[u] ist, ist Knoten u die Wurzel einer SCC. Alle Knoten darüber auf dem Stack gehören zusammen.
Die Komponente entnehmen
An einer Wurzel entnehmen Sie Knoten vom Stack, bis Sie u entfernen. Die entnommene Gruppe ist genau eine stark zusammenhängende Komponente.
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u: breakKosaraju als Alternative
Bevorzugen Sie zwei Durchläufe? Kosarajus Algorithmus führt DFS aus, kehrt jede Kante um und führt anschließend in der Abschlussreihenfolge erneut DFS aus, um die SCCs herauszulösen.
Schnelltest
Während Tarjans DFS erfüllt Knoten u die Bedingung low[u] == disc[u]. Was sagt Ihnen das?
Rückblick: SCCs mit Tarjan
Verfolgen Sie disc und low in einer DFS, legen Sie aktive Knoten auf den Stack und entnehmen Sie eine Komponente, sobald low gleich disc ist. SCCs in O(V+E). 🧩
Häufig gestellte Fragen
Ist die Lektion „Stark zusammenhängende Komponenten“ kostenlos?
Ja — der vollständige Text von „Stark zusammenhängende Komponenten“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Stark zusammenhängende Komponenten“?
Gruppieren Sie mit Tarjan gegenseitig erreichbare Knoten Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Stark zusammenhängende Komponenten“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Topologische Sortierung mit Kahns Algorithmus
- Zyklen in gerichteten Graphen erkennen
- Stark zusammenhängende Komponenten
- Brücken und Artikulationspunkte