Bridges
Learn Bridges (Graphs, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Bridges in an Undirected Graph A bridge (cut edge) is an edge whose removal disconnects the graph. They mark weak links in a network. Run one DFS and compute disc and low for each vertex. A tree edge u - v (v a child of u) is a bridge when low[v] > disc[u] : nothing in v's subtree can get back to u or above. Skip only the edge you came from (by edge id , so parallel edges are handled). Cost: O(V + E) .
More lessons in Graphs
- Graph Representation - Adjacency Matrix
- Graph Representation - Adjacency List
- Directed Graph
- Undirected Graph
- Weighted Graph
- BFS
- DFS
- Connected Components
- Cycle Detection
- Bipartite Graph
- Topological Sort
- Kahn's Algorithm
- DFS Topological Sort
- Shortest Path - BFS
- Shortest Path - Dijkstra
- Shortest Path - Bellman-Ford
- Shortest Path - Floyd-Warshall
- Minimum Spanning Tree - Prim's
- Minimum Spanning Tree - Kruskal's
- Disjoint Set Union - DSU
- Union-Find
- Strongly Connected Components - Kosaraju
- Strongly Connected Components - Tarjan
- Articulation Points
- Euler Path / Circuit
- Hamiltonian Path / Cycle
- Graph Coloring
- Network Flow
- Maximum Flow
- Bipartite Matching