Bridges and Articulation Points

Imagine a city whose neighbourhoods are connected by roads. Most roads are redundant — if one closes, drivers detour. But some roads are bridges: remove one and a whole district becomes unreachable. The same idea lives inside any network, from power grids to computer networks to social graphs.

In graph theory, a bridge (also called a cut edge) is an edge whose removal increases the number of connected components — it is the only path between two parts of the graph. An articulation point (or cut vertex) is a vertex with the same property: delete it, together with all its edges, and the graph splits.

Both concepts measure vulnerability. A network with many bridges and articulation points is fragile; a highly redundant network has none. Finding them quickly is therefore a fundamental task in network analysis, and the answer is elegant: Robert Tarjan's 1972 depth-first search algorithm does it in $O(V + E)$ time — one pass, linear in the size of the graph, and provably no algorithm can do better since every edge must be inspected at least once.

The key insight is a pair of timestamps computed during DFS. When the search visits vertex u, it records a discovery time disc[u]. It also maintains a low value low[u]: the smallest discovery time reachable from the subtree rooted at u using at most one back edge (an edge leading back up to an ancestor in the DFS tree). If low[v] > disc[u] for a tree edge (u, v), then v cannot reach u or any ancestor of u without crossing that edge — so the edge is a bridge. If low[v] >= disc[u] and u is not the DFS root (or the root has two or more children), then u is an articulation point.

Related reading: Euler vs Hamiltonian Paths explores another foundational distinction in graph traversal, and Minimum Spanning Tree shows how DFS-family ideas underpin optimal connectivity.

The graph below has eight vertices and several edges. Click Find Bridges & Cut Vertices to run Tarjan's algorithm: bridges turn red and articulation points get a bold ring. You can also click Add Random Edge to make the graph more redundant and re-run to see bridges disappear.

<p class="hint">{{hint}}</p>
<canvas id="gc" width="480" height="300"></canvas>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="find" type="button">{{btn_find}}</button>
  <button id="addedge" type="button">{{btn_add_edge}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 10px; background: #f5f8fa;
         max-width: 100%; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.5em; }
.status.bridge { color: #c92f3c; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Watch how adding a single edge can eliminate multiple bridges at once — redundancy compounds quickly. Removing bridges one at a time shows how the graph fractures into isolated components.

How hard is it to find all bridges and articulation points?

• Lower bound — every edge matters. Any correct algorithm must inspect every edge at least once, because a single unseen edge could be a bridge. That gives an Ω(V + E) lower bound.
• Tarjan's algorithm matches it. A single DFS traversal visits every vertex once and every edge twice (once in each direction for undirected graphs), computing disc[] and low[] in $O(V + E)$. The algorithm was published by Robert Tarjan in 1972 as part of his landmark paper on DFS.
• The low value is the magic. For each vertex u with DFS tree child v, the edge (u, v) is a bridge if and only if low[v] > disc[u]. This check is $O(1)$ per edge, so the whole pass stays linear.
• Articulation points by the same pass. Vertex u is an articulation point if it is the DFS root with ≥ 2 children, or if it has a child v with low[v] >= disc[u]. The DFS root case needs special handling because the root has no parent to "escape through."
• Status: solved. This is not an open problem or a hard problem — it is provably optimal and fully solved (Tarjan, 1972). No NP-hardness, no approximation needed. The algorithm is textbook and runs in linear time on any graph.

Contrast this with P vs NP: bridge-finding sits squarely in P, and in fact at the bottom of P — $O(V + E)$ is as efficient as reading the input.

Finding the vulnerable edges and vertices of a network is a first step in almost every reliability analysis:

• Internet routing: a bridge in the network graph means a single link whose failure partitions the internet. ISPs run bridge-detection algorithms to identify and harden these single points of failure.
• Road and rail networks: traffic engineers find articulation points — intersections or stations whose closure would cut off entire regions — to prioritise redundancy investment.
• Power grids: grid operators model the network as a graph and look for bridges (transmission lines) and articulation points (substations) to assess vulnerability to cascading failures.
• Social network analysis: articulation points in a social graph are brokers — individuals whose removal fragments the community into isolated groups. Identifying them matters for epidemiology, marketing, and counter-disinformation work.
• Chip design: in VLSI layout, a bridge in the connectivity graph of a printed circuit can mean a manufacturing defect that disconnects a component; automated tools run bridge detection as part of design-rule checking.
• Bioinformatics: protein interaction networks contain articulation points — proteins whose removal would disconnect functional modules. These are often essential genes and drug targets.

All of these use exactly the same $O(V + E)$ DFS algorithm. Its elegance is that finding vulnerability is no harder than simply traversing the network.

Bridges and articulation points reveal the hidden skeleton of a network — the edges and vertices that carry all the connectivity load with no redundancy. Finding them feels like it should be expensive, but Tarjan's 1972 algorithm proves otherwise: one depth-first search, linear time, no approximation needed.

The trick — recording discovery times and computing low values on the fly — is a beautiful example of how the right bookkeeping during a traversal can answer deep structural questions for free. No extra passes, no backtracking, no combinatorial explosion.

In a world where networks underpin everything from power supply to social discourse, knowing where the bridges are is the first step to building systems that survive when they fail. And now you know exactly how to find them — in the time it takes to simply read the graph.