Introduction

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)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.

Try It

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">An undirected graph with 8 vertices. Click <b>Find Bridges &amp; Cut Vertices</b> to run Tarjan's algorithm — bridges glow red, articulation points get a bold ring. Use <b>Add Random Edge</b> to make the graph more redundant and re-run.</p>
<canvas id="gc" width="480" height="300"></canvas>
<div class="status" id="status">Press the button to analyse the graph.</div>
<div class="btns">
  <button id="find" type="button">Find Bridges &amp; Cut Vertices</button>
  <button id="addedge" type="button">Add Random Edge</button>
  <button id="reset" type="button" class="ghost">Reset Graph</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Tarjan's bridge / articulation-point algorithm (1972), iterative.
// For each tree edge (p -> u), edge is a bridge iff low[u] > disc[p].
// Vertex p is an articulation point iff:
//   (a) p is the DFS root with >= 2 tree children, or
//   (b) p is a non-root with a child u where low[u] >= disc[p].
// Key fix: track parent by EDGE INDEX (not vertex ID) so the algorithm works correctly even when two vertices share multiple paths.

const W = 480, H = 300, R = 14;

// Fixed vertex positions (0..1 normalised, scaled to canvas)
const POS = [
  [0.12, 0.50], // 0 — left hub
  [0.30, 0.18], // 1
  [0.30, 0.82], // 2
  [0.50, 0.50], // 3 — central articulation point
  [0.70, 0.18], // 4
  [0.70, 0.82], // 5
  [0.88, 0.30], // 6
  [0.88, 0.70], // 7
];

// Default edges: left triangle {0,1,2} connected to centre 3 via two edges;
// then 3-4, 3-5 (bridges), 4-6, 5-7 (bridges). Bridges: 3-4, 3-5, 4-6, 5-7.  Articulation points: 3, 4, 5.
const DEFAULT_EDGES = [
  [0,1],[0,2],[1,2],  // left triangle — internally connected
  [1,3],[2,3],        // two paths from triangle to centre (3 is NOT a bridge endpoint here)
  [3,4],[3,5],        // bridges: only path from 3 to the right
  [4,6],[5,7],        // bridges: only path from 4 to 6, 5 to 7
];

let edges = DEFAULT_EDGES.map(e => [...e]);
let bridges = new Set();   // "a,b" with a < b
let artPoints = new Set(); // vertex indices

function px(i) { return Math.round(POS[i][0] * W); }
function py(i) { return Math.round(POS[i][1] * H); }

// ── Iterative Tarjan ────────────────────────────────────────────────────────
function tarjan(n, edgeList) {
  // Build adjacency with {to, idx} so we track edges by index, not vertex.
  const adj = Array.from({length: n}, () => []);
  edgeList.forEach(([a, b], idx) => {
    adj[a].push({ to: b, idx });
    adj[b].push({ to: a, idx });
  });

  const disc       = new Array(n).fill(-1);
  const low        = new Array(n).fill(0);
  const par        = new Array(n).fill(-1);  // parent vertex
  const parEdge    = new Array(n).fill(-1);  // parent edge index
  const childCount = new Array(n).fill(0);

  const newBridges  = new Set();
  const newAP       = new Set();
  let timer = 0;

  for (let src = 0; src < n; src++) {
    if (disc[src] !== -1) continue;
    disc[src] = low[src] = timer++;
    const stk = [[src, 0]]; // [vertex, adj-list cursor]

    while (stk.length) {
      const frame = stk[stk.length - 1];
      const u = frame[0];
      let pushed = false;

      while (frame[1] < adj[u].length) {
        const { to: v, idx } = adj[u][frame[1]];
        frame[1]++;
        if (idx === parEdge[u]) continue; // skip the edge we arrived on

        if (disc[v] === -1) {
          // Tree edge — recurse into v
          disc[v] = low[v] = timer++;
          par[v] = u;
          parEdge[v] = idx;
          childCount[u]++;
          stk.push([v, 0]);
          pushed = true;
          break;
        } else {
          // Back edge — update low
          low[u] = Math.min(low[u], disc[v]);
        }
      }

      if (!pushed) {
        // All neighbours of u exhausted — pop and propagate upward
        stk.pop();
        const p = par[u];
        if (p !== -1) {
          low[p] = Math.min(low[p], low[u]);
          if (low[u] > disc[p]) {
            newBridges.add(Math.min(p, u) + ',' + Math.max(p, u));
          }
          if (par[p] !== -1 && low[u] >= disc[p]) {
            newAP.add(p); // non-root articulation point
          }
        }
      }
    }
  }

  // Root articulation points: DFS root with >= 2 tree children
  for (let v = 0; v < n; v++) {
    if (par[v] === -1 && disc[v] !== -1 && childCount[v] >= 2) newAP.add(v);
  }

  bridges = newBridges;
  artPoints = newAP;
}

// ── Rendering ───────────────────────────────────────────────────────
function draw() {
  const canvas = document.getElementById('gc');
  const ctx = canvas.getContext('2d');
  ctx.clearRect(0, 0, W, H);

  edges.forEach(([a, b]) => {
    const key = Math.min(a, b) + ',' + Math.max(a, b);
    const isBridge = bridges.has(key);
    ctx.beginPath();
    ctx.moveTo(px(a), py(a));
    ctx.lineTo(px(b), py(b));
    ctx.strokeStyle = isBridge ? '#e63946' : '#7a9ab5';
    ctx.lineWidth   = isBridge ? 3.5 : 2;
    ctx.stroke();
  });

  POS.forEach((_, i) => {
    const x = px(i), y = py(i);
    const isAP = artPoints.has(i);

    if (isAP) {
      ctx.beginPath();
      ctx.arc(x, y, R + 5, 0, 2 * Math.PI);
      ctx.strokeStyle = '#e63946';
      ctx.lineWidth = 3;
      ctx.stroke();
    }

    ctx.beginPath();
    ctx.arc(x, y, R, 0, 2 * Math.PI);
    ctx.fillStyle = isAP ? '#fde8ea' : '#1d3557';
    ctx.fill();
    ctx.strokeStyle = isAP ? '#e63946' : '#1d3557';
    ctx.lineWidth = 2;
    ctx.stroke();

    ctx.fillStyle = isAP ? '#c92f3c' : '#fff';
    ctx.font = 'bold 12px system-ui, sans-serif';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText(i, x, y);
  });
}

function setStatus(text, cls) {
  const el = document.getElementById('status');
  el.textContent = text;
  el.className = 'status ' + (cls || '');
}

function analyse() {
  tarjan(POS.length, edges);
  draw();
  const bCount = bridges.size;
  const aCount = artPoints.size;
  if (bCount === 0 && aCount === 0) {
    setStatus('No bridges or articulation points — the graph is 2-connected!', 'ok');
  } else {
    const bList = bCount
      ? [...bridges].sort().map(k => '(' + k.replace(',', '–') + ')').join(', ')
      : 'none';
    const aList = aCount
      ? [...artPoints].sort((a, b) => a - b).join(', ')
      : 'none';
    setStatus(fmt('Bridges: %bList%. Articulation points: vertex %aList%.', { bList: bList, aList: aList }), 'bridge');
  }
}

function addRandomEdge() {
  const n = POS.length;
  const existing = new Set(edges.map(([a, b]) => Math.min(a, b) + ',' + Math.max(a, b)));
  const candidates = [];
  for (let a = 0; a < n; a++)
    for (let b = a + 1; b < n; b++)
      if (!existing.has(a + ',' + b)) candidates.push([a, b]);
  if (!candidates.length) {
    setStatus('Graph is already complete — no more edges to add.', 'ok');
    return;
  }
  const pick = candidates[Math.floor(Math.random() * candidates.length)];
  edges.push(pick);
  bridges = new Set(); artPoints = new Set();
  draw();
  setStatus(fmt('Added edge (%v%–%v2%). Press Find to re-analyse.', { v: pick[0], v2: pick[1] }));
}

function resetGraph() {
  edges = DEFAULT_EDGES.map(e => [...e]);
  bridges = new Set(); artPoints = new Set();
  draw();
  setStatus('Graph reset. Press the button to analyse.');
}

document.getElementById('find').addEventListener('click', analyse);
document.getElementById('addedge').addEventListener('click', addRandomEdge);
document.getElementById('reset').addEventListener('click', resetGraph);

draw(); // initial plain draw
console.log('Bridges & Articulation Points demo ready.');
console.log('Default bridges: 3-4, 3-5, 4-6, 5-7. Articulation points: 3, 4, 5.');
Result
Console

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.

The Real Complexity

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)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)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)O(V + E) is as efficient as reading the input.

Where It Matters

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)O(V + E) DFS algorithm. Its elegance is that finding vulnerability is no harder than simply traversing the network.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/bridges-articulation/Content licensed under CC BY-NC 4.0.