AlgorithmsGraph AlgorithmsArtikel

Bridges in Graphen: Tarjan, Low-Link und kritische Kanten

Praxisnaher Leitfaden zu Bridges mit DFS, Discovery Time, Low-Link, Cycle-Intuition und Netzwerkresilienz.

21. August 20269 Min. Lesezeit10 Aufrufe

#Graph#Algorithms#Bridges#Tarjan#DFS#Low Link#JavaScript#TypeScript

Arian Soleimanzadeh

Software Engineer & Researcher

Visueller Leitfaden zu Bridges und kritischen Kanten

Arian Soleimanzadeh

KI · Code · Produkt

Forschung + Engineering

Auf dieser Seite

Eine Bridge oder Cut Edge ist eine Kante in einem ungerichteten Graphen, deren Entfernung die Anzahl der Connected Components erhöht.

Unterschied zum Articulation Point

Code

Bridge = kritische Kante
Articulation Point = kritischer Knoten

Discovery und Low-Link

Tarjans DFS verwendet:

Code

disc[u]
low[u]

Für eine DFS-Baumkante (u,v) gilt:

Code

low[v] > disc[u]

Dann ist (u,v) eine Bridge.

Intuition

Kann der Teilbaum von v keinen Vorfahren von u über eine alternative Back Edge erreichen, ist (u,v) die einzige Verbindung nach oben.

Zyklen

Eine Kante in einem Zyklus ist keine Bridge, weil ein alternativer Weg existiert.

Anwendungen

Netzwerklinks
Data-Center-Redundanz
Verkehrsnetze
Telekommunikation
Infrastrukturresilienz

2-edge-connected Graph

Ein zusammenhängender Graph ohne Bridges ist 2-edge-connected.

Komplexität

Code

O(V + E)

Fazit

Bridge Detection identifiziert strukturelle Single Points of Failure auf Kantenebene und kann mit DFS und Low-Link-Werten in linearer Zeit durchgeführt werden.

Vorheriger Artikel

Articulation Points: Tarjan, Low-Link und kritische Knoten

Nächster Artikel

Bellman-Ford: Negative Gewichte und Negative Cycles

AlgorithmsGraph AlgorithmsArtikel

Bridges in Graphen: Tarjan, Low-Link und kritische Kanten

Praxisnaher Leitfaden zu Bridges mit DFS, Discovery Time, Low-Link, Cycle-Intuition und Netzwerkresilienz.

21. August 20269 Min. Lesezeit10 Aufrufe

#Graph#Algorithms#Bridges#Tarjan#DFS#Low Link#JavaScript#TypeScript

Arian Soleimanzadeh

Software Engineer & Researcher

Arian Soleimanzadeh

KI · Code · Produkt

Forschung + Engineering

Auf dieser Seite

Eine Bridge oder Cut Edge ist eine Kante in einem ungerichteten Graphen, deren Entfernung die Anzahl der Connected Components erhöht.

Unterschied zum Articulation Point

Code

Bridge = kritische Kante
Articulation Point = kritischer Knoten

Discovery und Low-Link

Tarjans DFS verwendet:

Code

disc[u]
low[u]

Für eine DFS-Baumkante (u,v) gilt:

Code

low[v] > disc[u]

Dann ist (u,v) eine Bridge.

Intuition

Kann der Teilbaum von v keinen Vorfahren von u über eine alternative Back Edge erreichen, ist (u,v) die einzige Verbindung nach oben.

Zyklen

Eine Kante in einem Zyklus ist keine Bridge, weil ein alternativer Weg existiert.

Anwendungen

Netzwerklinks
Data-Center-Redundanz
Verkehrsnetze
Telekommunikation
Infrastrukturresilienz

2-edge-connected Graph

Ein zusammenhängender Graph ohne Bridges ist 2-edge-connected.

Komplexität

Code

O(V + E)

Fazit

Bridge Detection identifiziert strukturelle Single Points of Failure auf Kantenebene und kann mit DFS und Low-Link-Werten in linearer Zeit durchgeführt werden.

Vorheriger Artikel

Articulation Points: Tarjan, Low-Link und kritische Knoten

Nächster Artikel