Draw a network as an undirected graph — roads, power lines, server links, it doesn't matter which — and one question always matters: which single point of failure would actually disconnect it? Two related but distinct answers. An articulation point (or cut vertex) is a vertex whose removal splits the graph into more pieces than it started with. A bridge (or cut edge) is an edge with the same property. Neither requires the whole graph to fall apart — just some two vertices that were connected before and aren't after.
Strongly Connected Components's
low-link bookkeeping already answers a question about how far back up an active DFS path a subtree
can reach. Turned on an undirected graph instead of a directed one, that same number
answers a sharper local question directly — no explicit stack, no closing components, just an
inequality checked the instant each child's exploration returns. For a non-root vertex
u with DFS child v: if nothing in v's subtree can reach back
above u (low[v] ≥ disc[u]), then u is the only thing
holding that subtree onto the rest of the graph — remove it, and the subtree falls off.
u is an articulation point. Tighten the inequality by one (low[v] >
disc[u], nothing reaches back to u at all, not even tied with it) and the tree
edge u–v itself is the only path between two halves of the graph — a bridge.
Eight nodes, A through H: two triangles, {A,B,C} and
{D,E,F}, joined by a bridge C–D, with a two-hop pendant chain
D–G–H hanging off the second triangle. Press Step or
Run to walk the DFS from A: a dashed node is on the current recursion
path; a filled tan node has finished. A node that turns solid and bold marks a
confirmed articulation point — that marking persists once made. A dashed red edge
marks a confirmed bridge, also persistent. The strips below track discovery/low-link
numbers, the live recursion path (root → current), and the two running result lists.
Every vertex gets a discovery time disc[u] — a plain DFS counter — and a low-link
value low[u] that starts equal to disc[u] and can only shrink. It shrinks
in the same two situations SCC's version does: a tree edge to child v returns with a
smaller low[v], or an edge lands directly on some already-visited vertex v
that isn't u's own DFS parent — a back edge, pulling low[u] down to
disc[v]. That second case is the whole difference from SCC: on an undirected graph,
"visited" only ever means "found by an earlier part of this same DFS," so a back edge here is any
edge that isn't the single edge u just came in on.
The two tests fire the instant a child's recursive call returns, comparing what it found against
u's own discovery time: low[v] ≥ disc[u] for an articulation point,
low[v] > disc[u] (strictly, no tie) for a bridge. A vertex can rack up either marking
more than once — once per child that fails to escape — but only needs to earn it once to stay
flagged for good.
The root of the DFS tree needs its own rule, and the demo's own graph shows why: A,
the root here, has degree 2 (edges to both B and C), but only one
of those becomes a DFS tree edge — the other is discovered as a back edge from inside B's
own subtree before A ever gets to explore it directly, so A ends up with
exactly one DFS child. The general test would still technically evaluate true at the root (its
disc is always the graph's smallest, 0, so any child's low is
automatically ≥ it) — but that's vacuous, not meaningful: a root with only one DFS
child has nowhere else for the rest of the graph to be, so removing it can't create a second piece.
The real rule for the root ignores the low-link test entirely and just counts DFS children directly:
two or more means an articulation point, exactly one (as with A here) does not.
Matches the demo above one for one — the demo's step generator is this same recursive shape with
yield points added at each state transition. adjacency is undirected: every
edge appears in both endpoints' lists.
function findArticulationPointsAndBridges(numNodes, adjacency) {
const disc = new Array(numNodes).fill(-1);
const low = new Array(numNodes).fill(-1);
const parent = new Array(numNodes).fill(-1);
const isArticulation = new Array(numNodes).fill(false);
const bridges = [];
let time = 0;
function dfs(u) {
disc[u] = low[u] = time++;
let children = 0;
for (const v of adjacency[u]) {
if (disc[v] === -1) {
children++;
parent[v] = u;
dfs(v);
low[u] = Math.min(low[u], low[v]);
if (parent[u] !== -1 && low[v] >= disc[u]) isArticulation[u] = true;
if (low[v] > disc[u]) bridges.push([u, v]);
} else if (v !== parent[u]) {
// back edge to an ancestor — NOT the parent edge, see Pitfalls for
// what a value-only parent check misses on graphs with parallel edges
low[u] = Math.min(low[u], disc[v]);
}
}
if (parent[u] === -1 && children > 1) isArticulation[u] = true;
}
for (let u = 0; u < numNodes; u++) {
if (disc[u] === -1) dfs(u);
}
return { isArticulation, bridges };
}The root really does need its own rule, not just an exemption. It's tempting to
think "skip the low-link test at the root" is just a defensive guard against an edge case that
happens not to matter. Checked directly: deleting the parent[u] !== -1 guard and
letting the general test run unconditionally at the root, too, flips A in the demo's own
graph to a false positive. A's one DFS child B returns with
low[B] = 0, and 0 ≥ disc[A] = 0 is true — the buggy version marks
A an articulation point, even though removing A leaves B and
C still directly connected to each other and to everything past C. The
general rule isn't "almost right" at the root; it's answering a different, meaningless question
there (whether the root can reach above itself, which it never can) and needs the child-count rule
in its place, not just alongside it.
Skipping the parent "by value" breaks on parallel edges. v !== parent[u]
correctly ignores the single edge u arrived on — as long as there's only one edge between
u and its parent. Add a second, parallel C–D edge to the demo's graph (two
separate wires between the same two intersections, not a typo) and C–D stops being a
bridge — a real second path exists between the two triangles even if one wire is cut. But a
value-based check can't tell those two edges apart: when D walks its adjacency list and
meets C a second time, C === parent[D] is still true, so the check skips it
exactly like the real parent edge, and low[D] never learns about the extra connection.
Checked directly by running the reference implementation above against the graph with that duplicate
edge added: the buggy value-check version still reports C–D as a bridge, wrongly. A
correct implementation on a graph with parallel edges has to track the specific edge the
parent link came in on (an edge index or object identity), not just the parent vertex's value — this
demo's graph is simple (no parallel edges) specifically so the value check is safe to use in it, not
because the distinction never matters.
One cut vertex can split a graph into more than two pieces. It's easy to picture
"cut" as always meaning "one graph becomes two," but nothing in the definition promises that.
D in the demo's graph is an articulation point three separate ways: it's the sole link
back to {A,B,C}, the sole link out to {E,F}, and the sole link out to the
{G,H} chain. Checked directly with a plain connectivity scan of the graph with
D and its edges deleted: three separate components remain, not two —
{A,B,C}, {E,F}, and {G,H}. A bridge can't do this — removing
one edge always leaves exactly two pieces, never more — but an articulation point's piece count is
just however many separately-hanging subtrees happened to route through it.
Deep graphs can still overflow the call stack. Same limitation as any deep
recursive DFS, including SCC's own
version above: a long chain of vertices can exceed the language's call-stack limit. See
DFS's own Pitfalls for why, and why an iterative rewrite
with an explicit stack (carrying low/parent/child-iteration-position
alongside each frame) sidesteps it.
Time: O(V + E) — one DFS pass, identical in shape to SCC's: every
vertex is visited exactly once and every edge inspected exactly once from each endpoint.
Space: O(V) for disc, low, parent,
and the recursion depth.
This site's guide, Choosing a Graph Traversal Approach, compares this entry against the other ten Graph Traversal entries side by side.