9.17 Bridges
You need to find edges whose removal disconnects a graph.
9.17 Bridges
Problem
You need to find edges whose removal disconnects a graph.
In Chapter 9.16, you learned how to identify articulation points, which are critical vertices. Sometimes the failure point is not a vertex but a connection itself.
Examples include:
- A network cable connecting two data centers
- A highway connecting two regions
- A communication link between clusters
- A transmission line connecting power grids
- A dependency edge connecting subsystems
You need to identify edges that act as single points of failure.
Solution
Use DFS with discovery times and low-link values.
A bridge, also called a cut edge, is an edge whose removal increases the number of connected components.
Consider:
A -- B -- C
Removing:
B -- C
produces:
A -- B
C
The graph becomes disconnected.
Therefore:
(B, C)
is a bridge.
Likewise:
(A, B)
is also a bridge.
Every edge in a tree is a bridge.
Discussion
Bridges reveal critical connections.
They answer the question:
Which links hold the graph together?
This concept appears frequently in reliability analysis.
Consider a network:
A -- B -- C
|
D
Every connection is important.
Failure of any edge disconnects part of the graph.
Now consider:
A -- B
| |
D -- C
No edge is a bridge.
Multiple routes exist between every pair of vertices.
If one edge fails, traffic can reroute through another path.
This observation leads to a useful intuition:
An edge is a bridge if it does not belong to any cycle.
Cycles provide alternate routes.
Without an alternate route, the edge becomes critical.
DFS Tree View
Run DFS and build a DFS tree.
Example:
A
|
B
|
C
|
D
DFS tree:
A
|
B
|
C
|
D
Every edge appears in the tree.
No back edges exist.
Every connection is a bridge.
Now consider:
A -- B
| |
D -- C
A DFS might produce:
A
|
B
|
C
|
D
but there is also a back edge:
D -- A
That back edge creates an alternate route.
No tree edge in the cycle is a bridge.
Discovery Times
As in articulation-point detection, assign each vertex:
disc[v]
which records when DFS first visits it.
Example:
A = 0
B = 1
C = 2
D = 3
These timestamps establish ancestor relationships within the DFS tree.
Low-Link Values
Also compute:
low[v]
which records the earliest discovery time reachable from v or its descendants.
This value captures whether a subtree can reach an ancestor through a back edge.
Example:
A -- B
| |
D -- C
The subtree rooted at B can reach:
A
through:
B → C → D → A
Therefore:
low[B]
becomes equal to:
disc[A]
This information tells us that removing A-B does not disconnect the graph.
Bridge Condition
Consider a DFS tree edge:
v
|
to
If:
low[to] > disc[v]
then the subtree rooted at to cannot reach v or any ancestor of v through a back edge.
The only connection between the subtree and the rest of the graph is:
v -- to
Removing that edge disconnects the graph.
Therefore:
(v, to)
is a bridge.
This is the central bridge-detection rule.
Recipe: Find All Bridges
def bridges(graph):
time = 0
disc = {}
low = {}
result = []
def dfs(vertex, parent):
nonlocal time
disc[vertex] = time
low[vertex] = time
time += 1
for neighbor in graph[vertex]:
if neighbor == parent:
continue
if neighbor not in disc:
dfs(neighbor, vertex)
low[vertex] = min(
low[vertex],
low[neighbor]
)
if low[neighbor] > disc[vertex]:
result.append(
(vertex, neighbor)
)
else:
low[vertex] = min(
low[vertex],
disc[neighbor]
)
for vertex in graph:
if vertex not in disc:
dfs(vertex, None)
return result
Example:
graph = {
"A": ["B"],
"B": ["A", "C", "D"],
"C": ["B"],
"D": ["B"],
}
print(bridges(graph))
Output:
[
("A", "B"),
("B", "C"),
("B", "D"),
]
Every edge is critical.
Why the Test Works
Consider:
v
|
to
If:
low[to] <= disc[v]
then the subtree rooted at to can reach v or an ancestor of v.
An alternate route exists.
The edge is not a bridge.
However, if:
low[to] > disc[v]
then no such route exists.
Every path between the subtree and earlier vertices passes through:
v -- to
Removing that edge disconnects the graph.
That is exactly the definition of a bridge.
Example: Tree Graph
Consider:
A
|
B
/ \\n C D
|
E
Every edge is a bridge.
Output:
[
("A", "B"),
("B", "C"),
("B", "D"),
("D", "E"),
]
This illustrates an important theorem:
Every edge in a tree is a bridge.
Trees contain no cycles.
Without cycles, no alternate routes exist.
Example: Cycle Graph
Consider:
A -- B
| |
D -- C
Output:
[]
No bridges exist.
Removing any edge still leaves another path connecting the endpoints.
This reflects another useful theorem:
No edge belonging to a cycle can be a bridge.
Cycles provide redundancy.
Naïve Verification
For testing, a slower implementation is useful.
Remove one edge at a time.
Then recompute connectivity.
def is_bridge(graph, u, v):
modified = {}
for vertex, neighbors in graph.items():
modified[vertex] = [
n
for n in neighbors
if not (
(vertex == u and n == v)
or
(vertex == v and n == u)
)
]
return (
count_components(modified)
>
count_components(graph)
)
This approach is expensive but useful for validating optimized implementations on small graphs.
Bridge Tree
After removing all non-bridge edges, the graph decomposes into highly connected regions.
Consider:
[A B C]
|
[D E]
|
[F G H]
The connecting edges are bridges.
Collapsing each region produces:
Region1
|
Region2
|
Region3
This structure is called a bridge tree.
Bridge trees are useful in network analysis and fault-tolerance studies.
Relationship to Articulation Points
Bridges and articulation points are closely related.
| Concept | Removal Target |
|---|---|
| Articulation Point | Vertex |
| Bridge | Edge |
Both rely on:
- DFS
- Discovery times
- Low-link values
The conditions differ slightly.
Articulation point:
low[child] >= disc[parent]
Bridge:
low[child] > disc[parent]
The strict inequality is important.
Many implementations accidentally confuse the two rules.
Applications
Network Reliability
Identify communication links whose failure disconnects the network.
Transportation Systems
Locate roads whose closure isolates regions.
Power Distribution
Find transmission lines that create single points of failure.
Infrastructure Planning
Determine where redundancy should be added.
Social Networks
Identify relationships connecting otherwise separate communities.
Complexity Analysis
Let:
V= number of verticesE= number of edges
The algorithm performs one DFS.
| Operation | Complexity |
|---|---|
| DFS traversal | O(V + E) |
| Low-link computation | O(V + E) |
| Bridge detection | O(V + E) |
| Memory usage | O(V) |
The algorithm is linear in graph size.
This efficiency makes it practical for very large sparse graphs.
Common Pitfalls
Do not use:
low[child] >= disc[parent]
for bridge detection.
The correct test is:
low[child] > disc[parent]
Do not treat the parent edge as a back edge.
Do not stop after one DFS in disconnected graphs.
Do not assume high-degree vertices cannot be connected by bridges.
Degree and bridge status are unrelated.
Do not forget that every tree edge in a tree is a bridge.
Do not assume bridges exist only in sparse graphs.
Dense graphs may still contain bridge edges connecting dense regions.
Recipe: Check Whether an Edge Is Critical
Once bridge information is available:
critical = set(
tuple(sorted(edge))
for edge in bridges(graph)
)
edge = tuple(sorted(("A", "B")))
print(edge in critical)
Output:
True
This lookup can be useful in routing and reliability systems.
Takeaway
Bridges identify edges whose removal disconnects an undirected graph. They represent critical connections, expose single points of failure, and help measure network resilience. Using DFS, discovery times, and low-link values, all bridges can be found in linear time. Together with articulation points, bridge detection provides a powerful framework for understanding graph robustness and structural vulnerability.