Brücken und Artikulationspunkte
Finden Sie Kanten und Knoten, deren Entfernung den Graphen trennt
Brücken und Artikulationspunkte ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 4 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 Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Schwachstellen in einem Graphen
Einige Teile eines ungerichteten Graphen sind kritisch: Entfernt man sie, zerfällt der Graph. Wenn Sie sie finden, werden schwache Verbindungen sichtbar.
Was eine Brücke ist
Eine Brücke ist eine Kante, deren Entfernung die Anzahl der Zusammenhangskomponenten erhöht. Sie ist der einzige Weg zwischen zwei Bereichen.
Was ein Artikulationspunkt ist
Ein Artikulationspunkt ist ein Knoten, dessen Entfernung den Graphen unzusammenhängend macht. Netzwerke sind an solchen einzelnen Ausfallpunkten besonders verwundbar.
DFS-Bäume erneut betrachtet
Beide Verfahren basieren auf einer DFS und verfolgen Entdeckungszeit sowie einen low-Wert, ähnlich wie Tarjan, aber für einen ungerichteten Graphen.
disc = [-1] * n
low = [-1] * nlow bedeutet die größte Reichweite
Das low eines Knotens ist die früheste Entdeckungs-ID, die von seinem DFS-Teilbaum aus erreichbar ist, möglicherweise über eine Rückwärtskante nach oben.
Beim Betreten initialisieren
Wenn DFS einen Knoten betritt, setzen Sie dessen disc und low auf den aktuellen Zählerstand und gehen anschließend zu seinen Nachbarn weiter.
disc[u] = low[u] = timer
timer += 1Die Brückenbedingung
Nach dem rekursiven Aufruf für den Kindknoten v gilt: Wenn low[v] > disc[u], überspringt keine Rückwärtskante u. Daher ist die Kante u-v eine Brücke.
if low[v] > disc[u]:
bridges.append((u, v))Die Artikulationsbedingung
Ein Knoten u, der keine Wurzel ist, ist ein Artikulationspunkt, wenn ein Kind v low[v] >= disc[u] erfüllt: Der Teilbaum von v kann u nicht umgehen.
if parent[u] != -1 and low[v] >= disc[u]:
art.add(u)Der Sonderfall der Wurzel
Die DFS-Wurzel ist nur dann ein Artikulationspunkt, wenn sie mindestens zwei Kinder im DFS-Baum hat. Zählen Sie diese daher.
if parent[u] == -1 and children > 1:
art.add(u)Die Elternkante überspringen
Wenn Sie low anhand einer Rückwärtskante aktualisieren, dürfen Sie nicht über die Kante zu Ihrem Elternknoten zurückgehen, sonst beurteilen Sie Brücken falsch.
if v != parent[u]:
low[u] = min(low[u], disc[v])Ein Durchlauf, beide Ergebnisse
Eine einzige DFS findet jede Brücke und jeden Artikulationspunkt gemeinsam in O(V + E). Ein zusätzlicher Durchlauf ist nicht erforderlich.
Schnelltest
Nach dem rekursiven Aufruf für den Kindknoten v von u stellen Sie fest, dass low[v] > disc[u] gilt. Was haben Sie gefunden?
Rückblick: Kritische Kanten und Knoten
Eine DFS mit disc und low findet alles: low[v] > disc[u] kennzeichnet eine Brücke, und low[v] >= disc[u] kennzeichnet einen Artikulationspunkt. 🌉
Häufig gestellte Fragen
Ist die Lektion „Brücken und Artikulationspunkte“ kostenlos?
Ja — der vollständige Text von „Brücken und Artikulationspunkte“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Brücken und Artikulationspunkte“?
Finden Sie Kanten und Knoten, deren Entfernung den Graphen trennt Du übst Competitive Programming Academy 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 Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy 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 4 von 4.
Wie lange dauert die Lektion „Brücken und Artikulationspunkte“?
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 Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-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