Brücken Finder

Pseudocode

Dieselbe Maschinerie wie bei den Artikulationspunkten, mit einem einzigen von größer gleich auf strikt größer geänderten Vergleich.

dfs(u, vorgänger):
    entd[u] = low[u] = ++zeit

    für jeden Nachbarn v von u:
        wenn v == vorgänger: weiter   // Ankunftskante überspringen
        wenn v bereits besucht:
            low[u] = min(low[u], entd[v])    // Rückkante
        sonst:
            dfs(v, u)
            low[u] = min(low[u], low[v])
            wenn low[v] > entd[u]:
                melde die Kante (u, v) als Brücke

Die strikte Ungleichung macht den ganzen Unterschied zu den Artikulationspunkten aus. low[v] > entd[u] besagt, dass nichts im Teilbaum unterhalb von v den Knoten u oder etwas darüber erreichen kann, die Kante (u, v) ist also die einzige Route und ihr Entfernen trennt den Graphen. Artikulationspunkte nutzen low[v] >= entd[u], wobei Gleichheit bedeutet, dass der Teilbaum u selbst erreicht, aber nicht darüber hinaus; das schneidet den Teilbaum ab, wenn du den Knoten u löschst, nicht aber, wenn du nur die Kante löschst.

Durchgerechnetes Beispiel, Schritt für Schritt

Führe die Tiefensuche von A aus auf einem Dreieck mit zweikantigem Anhängsel aus, demselben Graphen wie bei den Artikulationspunkten, damit sich beide Tests auf identischen Daten vergleichen lassen.

Beispielgraph: Ungerichtete Kanten A-B, B-C und C-A bilden ein Dreieck, dazu C-D und D-E.

1. Entdeckungszeiten vergeben. Der Abstieg über A, B, C, D und E ergibt die Entdeckungszeiten 1, 2, 3, 4 und 5.
2. E ist eine Sackgasse. E hat nur seinen Vorgänger D als Nachbarn, also bleibt low[E] bei 5.
3. D-E ist eine Brücke. Zurück bei D gilt low[D] = min(4, low[E] = 5) = 4. Prüfe die Kante: low[E] = 5 > entd[D] = 4, also ist D-E eine Brücke. Ihr Entfernen isoliert E, was offensichtlich zutrifft.
4. C-D ist ebenfalls eine Brücke. Bei C liefert die Rückkante C-A den Wert low[C] = min(3, entd[A] = 1) = 1, und mit dem Kind zusammen min(1, low[D] = 4) = 1. Prüfe die Kante zu D: low[D] = 4 > entd[C] = 3, also ist auch C-D eine Brücke.
5. Die Dreieckskanten sind keine. Bei B gilt low[B] = min(2, low[C] = 1) = 1. Prüfe die Kante B-C: low[C] = 1 > entd[B] = 2 ist falsch, B-C ist also keine Brücke. C erreicht A auch ohne B-C, die Kante besitzt somit eine Ausweichroute. Dieselbe Überlegung schließt A-B und C-A aus.

Die Brücken sind C-D und D-E. Beachte den Gegensatz zu den Artikulationspunkten auf genau diesem Graphen, wo die Antwort die Knoten C und D lautete. Jede Kante des Dreiecks liegt auf einem Zyklus und hat damit einen Umweg, während jede Kante des Anhängsels die einzige Verbindung zu allem dahinter ist. Die allgemeine Regel folgt unmittelbar: eine Kante ist genau dann eine Brücke, wenn sie auf keinem Zyklus liegt.

Komplexität und woher sie kommt

Zeit: O(V + E) · Speicher: O(V)

Eine einzige Tiefensuche mit konstantem Zusatzaufwand je Kante, die Kosten entsprechen also denen des Durchlaufs. Jeder Knoten wird einmal besucht und jede Kante zweimal betrachtet, einmal von jedem Endpunkt. Der Zustand besteht aus zwei ganzen Zahlen je Knoten plus dem Rekursionsstapel, alles O(V). Der naive Ansatz, jede Kante zu entfernen und den Zusammenhang zu prüfen, kostet O(E mal (V + E)); bei einem Graphen mit 10.000 Kanten ist die Low-Link-Methode damit rund vier Größenordnungen schneller.

Wann Brückenfindung passt und wann nicht

Dieselbe DFS beantwortet mehrere verwandte Fragen. Wähle danach, ob das Anfällige eine Kante, ein Knoten oder eine ganze Region ist.

Häufige Fehler

• >= statt > verwenden. Der Artikulationspunkttest lautet low[v] >= entd[u]; der Brückentest lautet strikt low[v] > entd[u]. Mit >= wird jede Baumkante zu einem Knoten gemeldet, der nicht über seinen Vorgänger hinausreicht, was massiv übermeldet. Ein einziges Zeichen trennt die beiden Algorithmen.
• Den Vorgänger über den Knoten statt über die Kante überspringen. Bei parallelen Kanten zwischen u und v ist die zweite Kante eine echte Ausweichroute und keine der beiden ist eine Brücke. Über die Knotenidentität zu überspringen verbirgt das und meldet eine Brücke, die es nicht gibt. Merke dir die konkrete Kante, über die du angekommen bist.
• Für Rückkanten low[v] statt entd[v] verwenden. Triffst du auf einen bereits besuchten Nachbarn, beziehe seine Entdeckungszeit ein, nicht seinen Low-Link. Die Verwendung von low[v] kann einen Wert aus einem unverwandten Teilbaum einschleppen und echte Brücken stillschweigend unterdrücken.
• Ihn auf gerichtete Graphen anwenden. Brücken sind für ungerichtete Graphen definiert. Die gerichtete Frage, welche Kanten bei Entfernung die Zahl der starken Zusammenhangskomponenten erhöhen, ist ein anderes Problem und erfordert andere Werkzeuge.
• Unzusammenhängende Komponenten vergessen. Eine DFS deckt nur eine Komponente ab. Iteriere über alle Knoten und starte von jedem unbesuchten eine neue Suche, sonst bleiben Brücken in anderen Komponenten unentdeckt.

Häufig gestellte Fragen

Was ist eine Brücke in einem Graphen?

Eine Brücke, auch Schnittkante genannt, ist eine Kante, deren Entfernen die Zahl der Zusammenhangskomponenten erhöht. Gleichbedeutend ist sie eine Kante, die auf keinem Zyklus liegt: gäbe es einen Zyklus durch sie, so böte der Rest dieses Zyklus eine Ausweichroute und ihr Entfernen würde nichts trennen.

Wie findet man Brücken in einem Graphen?

Führe eine einzige Tiefensuche aus und notiere für jeden Knoten Entdeckungszeit und Low-Link, also die früheste aus seinem Teilbaum über höchstens eine Rückkante erreichbare Entdeckungszeit. Eine Baumkante von u zum Kind v ist genau dann eine Brücke, wenn low[v] > entd[u] gilt, also nichts unterhalb von v den Knoten u oder etwas darüber erreicht. Der gesamte Algorithmus läuft in O(V + E).

Was ist der Unterschied zwischen einer Brücke und einem Artikulationspunkt?

Eine Brücke ist eine Kante, deren Entfernen den Graphen trennt; ein Artikulationspunkt ist ein Knoten, der das bewirkt. Beide entspringen derselben DFS und unterscheiden sich in einem Vergleich: strikt größer für Brücken, größer gleich für Artikulationspunkte. Ein Graph kann das eine ohne das andere besitzen.

Kann eine Brücke Teil eines Zyklus sein?

Nein, und das ist die klarste Sichtweise darauf. Liegt eine Kante auf einem Zyklus, so bildet der Rest dieses Zyklus einen Ausweichweg zwischen ihren Endpunkten, ihr Entfernen lässt den Graphen also zusammenhängend. Brücken sind genau jene Kanten, die auf keinem Zyklus liegen.

Wofür werden Brücken verwendet?

Zum Auffinden kritischer Verbindungen in Telekommunikations- und Glasfaser-Backbones, unverzichtbarer Straßen und Bahnabschnitte, deren Sperrung eine Region zerteilen würde, fragiler Verbindungen in Stromnetzen und zur Risikoanalyse von Abhängigkeiten in Software. Auf LeetCode erscheint dasselbe Problem als Critical Connections in a Network.