Bridges & Articulation Points

We have seen depth-first search lay a tree over a graph, and we used that tree to direct edges, find cycles, and decompose a digraph into strongly connected components. This lesson turns the same machinery on a different question, one that matters whenever a graph models a network: which parts of it are fragile? If a single fiber link is cut or a single router fails, the network may split into pieces that can no longer reach one another. These single points of failure have names.

A graph with no bridges is 2-edge-connected: you must cut at least two edges to disconnect it, so every pair of vertices is joined by two edge-disjoint paths. A graph with no articulation points (and at least three vertices) is 2-vertex-connected, or biconnected: two vertex-disjoint paths between every pair.¹ The maximal biconnected subgraphs are the biconnected components; bridges and cut vertices are the seams where they meet. So the question where is my network fragile? is the question find the cut edges and cut vertices, and one DFS answers it.

2-edge-connected (left, every edge on a cycle) vs a graph with a bridge (right,

u - v

cut)

The DFS-tree view

Run DFS from any vertex of a connected, undirected graph. Classify each edge by when DFS first traverses it. The decisive structural fact is that only two kinds survive.

This is what makes undirected connectivity tractable: the only way to leave a DFS subtree is a back edge climbing to an ancestor. Bridges and cut vertices are both about whether such an escape exists. To detect it we time the search and track how high each subtree can climb.

undirected DFS yields only tree edges (solid) and back edges (dashed) — no cross or forward edges

In words, $l o w [u]$ is the smallest discovery time reachable from $u$ 's DFS subtree using any number of tree edges (downward) plus at most one back edge (the final hop up). It measures the highest ancestor the subtree rooted at $u$ can reach without going through $u$ 's parent. Both quantities are computed in the same recursion: set $d i sc [u] = l o w [u]$ on entry, then relax $l o w [u]$ against each child's finished $l o w$ and each back edge's target $d i sc$ .

dfs_lowlink.pypython

from collections.abc import Hashable
from typing import Generic, TypeVar

from graph import Edge, Graph

Label = TypeVar("Label", bound=Hashable)

class EdgeIdentity(Generic[Label]):
  """
    A canonical id for each undirected edge, shared by its two Edge objects.\n
    `Graph` creates a forward Edge and a separate reverse Edge per undirected\n
    edge, appended in lock-step order. Zipping the two endpoints' edge lists\n
    by position pairs the k-th forward copy with the k-th reverse copy, so\n
    parallel edges between the same vertices each get a distinct id.\n
  """

  def __init__(self, graph: Graph[Label]) -> None:
    # map each Edge object's identity to its canonical undirected-edge id.
    self._id_of: dict[int, int] = {}
    next_id: int = 0
    seen_pairs: set[frozenset[Label]] = set()

    for vertex in graph.vertices:
      for neighbor in {edge.target.label for edge in vertex.outgoing}:
        # a self-loop never affects connectivity; give each copy a unique id
        # so the DFS treats it as a harmless (skippable) back edge to self.
        if vertex.label == neighbor:
          for loop_edge in vertex.outgoing:
            if loop_edge.target.label == vertex.label:
              self._id_of[id(loop_edge)] = next_id
              next_id += 1
          continue

        # handle each unordered pair once, from the first endpoint that meets it.
        endpoints: frozenset[Label] = frozenset((vertex.label, neighbor))
        if endpoints in seen_pairs:
          continue
        seen_pairs.add(endpoints)

        # collect the forward copies and their mirror twins on the far side.
        forward: list[Edge[Label]] = [
          edge for edge in vertex.outgoing if edge.target.label == neighbor
        ]
        reverse: list[Edge[Label]] = [
          edge
          for edge in graph.vertex(neighbor).outgoing
          if edge.target.label == vertex.label
        ]

        # pair the k-th forward copy with the k-th reverse copy under one id.
        for forward_edge, reverse_edge in zip(forward, reverse):
          self._id_of[id(forward_edge)] = next_id
          self._id_of[id(reverse_edge)] = next_id
          next_id += 1

  def of(self, edge: Edge[Label]) -> int:
    """
      The shared id of `edge` and its mirror twin.\n
    """
    return self._id_of[id(edge)]

graph.pypython

from collections.abc import Hashable, Iterator
from typing import Generic, Optional, TypeVar


Label = TypeVar("Label", bound=Hashable)


class Edge(Generic[Label]):
  """
    A directed connection from `source` to `target`, carrying a weight.\n
  """

  def __init__(
    self,
    source: Vertex[Label],
    target: Vertex[Label],
    weight: float = 1.0,
  ) -> None:
    self.source: Vertex[Label] = source
    self.target: Vertex[Label] = target
    self.weight: float = weight

  def __repr__(self) -> str:
    return f"Edge({self.source.label!r} -> {self.target.label!r}, w={self.weight})"


class Vertex(Generic[Label]):
  """
    A graph vertex: a label plus the list of edges leaving it.\n
  """

  def __init__(self, label: Label) -> None:
    self.label: Label = label
    self.outgoing: list[Edge[Label]] = []

  def neighbors(self) -> list[Vertex[Label]]:
    """
      The vertices reachable from this one by a single edge.\n
    """
    return [edge.target for edge in self.outgoing]

  def edge_to(self, label: Label) -> Optional[Edge[Label]]:
    """
      The outgoing edge to the vertex with `label`, or None.\n
    """
    for edge in self.outgoing:
      if edge.target.label == label:
        return edge
    return None

  def __repr__(self) -> str:
    return f"Vertex({self.label!r})"


class Graph(Generic[Label]):
  """
    A graph of Vertex objects linked by Edge objects.\n
    Pass `directed=True` for a digraph; otherwise each `add_edge` inserts\n
    the reverse edge too.\n
  """

  def __init__(self, directed: bool = False) -> None:
    self.directed: bool = directed
    self._vertices: dict[Label, Vertex[Label]] = {}

  def add_vertex(self, label: Label) -> Vertex[Label]:
    """
      Return the vertex for `label`, creating it if it is absent.\n
    """
    # reuse the existing vertex, or mint and register a fresh one.
    vertex = self._vertices.get(label)
    if vertex is None:
      vertex = Vertex(label)
      self._vertices[label] = vertex
    return vertex

  def add_edge(
    self,
    source_label: Label,
    target_label: Label,
    weight: float = 1.0,
  ) -> None:
    """
      Connect two labels (creating either vertex as needed).\n
      Adds the reverse edge as well when the graph is undirected.\n
    """
    source = self.add_vertex(source_label)
    target = self.add_vertex(target_label)

    # link source to target, and mirror it back when undirected.
    source.outgoing.append(Edge(source, target, weight))
    if not self.directed:
      target.outgoing.append(Edge(target, source, weight))

  def vertex(self, label: Label) -> Vertex[Label]:
    """
      The vertex carrying `label` (raises KeyError if absent).\n
    """
    return self._vertices[label]

  @property
  def vertices(self) -> list[Vertex[Label]]:
    """
      Every vertex, in insertion order.\n
    """
    return list(self._vertices.values())

  @property
  def labels(self) -> list[Label]:
    """
      Every vertex label, in insertion order.\n
    """
    return list(self._vertices)

  def edges(self) -> Iterator[Edge[Label]]:
    """
      Each edge once — an undirected edge is yielded a single time.\n
    """
    # track undirected endpoint pairs so each is emitted only once.
    seen: set[frozenset[Label]] = set()

    for vertex in self._vertices.values():
      for edge in vertex.outgoing:
        # skip an undirected edge already yielded from the other endpoint.
        if not self.directed:
          endpoints = frozenset((edge.source.label, edge.target.label))
          if endpoints in seen:
            continue
          seen.add(endpoints)

        yield edge

  def __contains__(self, label: Label) -> bool:
    return label in self._vertices

  def __iter__(self) -> Iterator[Vertex[Label]]:
    return iter(self._vertices.values())

  def __len__(self) -> int:
    return len(self._vertices)

DFS tree (solid = tree edge, dashed = back edge); bridge

\leftrightarrow l o w [v] > d i sc [u]

In the figure each node is labeled $d i sc / l o w$ . The back edge $C \to A$ pulls $l o w [C] = l o w [B] = 1$ , so the subtrees of $B$ and $C$ can all climb back above their parents: none of $A - B$ , $B - C$ is a bridge. But $D$ is a dead end, $l o w [D] = d i sc [D] = 4$ , nothing in $D$ 's subtree reaches above $C$ , so cutting $C - D$ strands $D$ . The edge $A - E$ is a bridge too, since $E$ 's only escape, the back edge $F \to E$ , stays inside $E$ 's own subtree.

The bridge criterion

The criterion $l o w [v] > d i sc [u]$ is a decision test on a single edge — is this a bridge? — and the iff is its two-sided correctness in the sense of the foundations. The forward direction ( $l o w [v] > d i sc [u]$ implies the edge really is a bridge) is its soundness: the test never flags a safe edge. The reverse (a true bridge always satisfies $l o w [v] > d i sc [u]$ , since otherwise a back edge offers an alternative route) is its completeness: no bridge is missed.

The articulation criterion

Cut vertices need one more case, because removing $u$ deletes all of $u$ 's incident edges at once, including the tree edges to each child.

Proof. The root case. The root has no ancestors, so back edges cannot help. If it has two or more children, those child-subtrees were discovered separately and the only edges joining them ran through the root (cross edges don't exist), so deleting the root splits them. One child means the root is just a leaf-side endpoint and removing it leaves the rest connected.

The non-root case. For a non-root $u$ , deleting $u$ severs child $v$ 's subtree from $u$ . That subtree stays attached to the rest of the graph only if some back edge climbs strictly above $u$ , i.e. $l o w [v] < d i sc [u]$ . If instead $l o w [v] \geq d i sc [u]$ , every escape from $v$ 's subtree reaches no higher than $u$ itself, so removing $u$ isolates that subtree and $u$ is a cut vertex. The contrast with the bridge test comes down to the boundary case: a back edge to $u$ ( $l o w [v] = d i sc [u]$ ) saves the edge $(u, v)$ but does not save the vertex $u$ , since deleting $u$ destroys that back edge's endpoint too. Hence $>$ for bridges, $\geq$ for cut vertices. $□$

cut vertex

\leftrightarrow l o w [c hi l d] \geq d i sc [u]

(or root with

\geq 2

children)

Here the back edge $X \to U$ gives $l o w [X] = d i sc [U] = 2$ . The subtree of $X$ can climb to $U$ but no higher, so $l o w [X] \geq d i sc [U]$ holds and $U$ is a cut vertex: deleting it strands $X$ and $Y$ from $R$ . Yet the edge $U - X$ is not a bridge, since $l o w [X] = d i sc [U]$ is not strictly greater. The same local data, two thresholds apart, distinguishes fragile edges from fragile vertices.

One DFS finds them all

Both criteria read off $d i sc$ and $l o w$ , so a single recursion computes everything. The one subtlety is the parent edge: in an undirected graph the edge back to the parent must not be mistaken for a back edge that lowers $l o w$ . Guarding by parent vertex is correct only when there are no multi-edges (two distinct edges between the same pair); with multi-edges, a second $u$ –parent edge is a genuine back edge and the second copy must be allowed to lower $l o w$ . The reliable fix is to track the parent edge id rather than the parent vertex.

Algorithm:

\textsc{Bridges-AP}(G)

— find all bridges and articulation points in

O(V+E)

1
$timer \gets 0$ ;\ \ $disc[\,\cdot\,] \gets 0$ (0 = unvisited)
2
for each vertex $s$ in $V$ do
3
if $disc[s] = 0$ then $\textsc{Dfs}(s,\ \text{nil})$
nil = no parent edge
4
5
procedure $\textsc{Dfs}(u,\ pe)$ :
$pe$ = id of edge to parent
6
$timer \gets timer + 1$
7
$disc[u] \gets low[u] \gets timer$
8
$children \gets 0$
9
for each incident edge $e = \{u,w\}$ do
10
if $e = pe$ then continue
skip arrival edge
11
if $disc[w] = 0$ then
tree edge
12
$children \gets children + 1$
13
$\textsc{Dfs}(w,\ e)$
14
$low[u] \gets \min(low[u],\ low[w])$
15
if $low[w] > disc[u]$ then report bridge $\{u,w\}$
16
if $pe \ne \text{nil}$ and $low[w] \ge disc[u]$ then mark $u$ articulation
17
else
back edge
18
$low[u] \gets \min(low[u],\ disc[w])$
19
if $pe = \text{nil}$ and $children \ge 2$ then mark $u$ articulation

Each vertex is discovered once and each edge is examined a constant number of times (twice over the whole run, once from each endpoint), so the search is $Θ (V + E)$ , asymptotically free on top of the DFS we were already running. The outer loop over $s$ makes it work on disconnected graphs as well: it finds the bridges and cut vertices of every component. The same low-link bookkeeping, with a stack of edges, also peels off the biconnected components directly (pop the stack down to $(u, v)$ whenever $l o w [v] \geq d i sc [u]$ ), which is Tarjan's original formulation.²³

A complete trace

Here is the whole computation, step by step, on a seven-vertex graph built from two triangles joined by a chain: triangle $a, b, c$ , bridge $c - d$ , triangle $d, e, f$ , bridge $f - g$ . Deleting $c$ , $d$ , or $f$ splits the graph, so those three are its cut vertices.

The input graph: triangles

{a, b, c}

and

{d, e, f}

joined by the bridge

c - d

, with a pendant bridge

f - g

. Cut vertices

c

d

f

are ringed.

Start DFS at $a$ with alphabetical adjacency lists. The recursion discovers the chain $a, b, c, d, e, f, g$ (each vertex's first unvisited neighbor happens to be the next letter), and the interesting work happens on the way back up:

step	event	effect
1	discover $a$	$d i sc [a] = l o w [a] = 1$
2	discover $b$ via tree edge $a - b$	$d i sc [b] = l o w [b] = 2$
3	discover $c$ via tree edge $b - c$	$d i sc [c] = l o w [c] = 3$
4	$c$ sees $a$ : back edge	$l o w [c] = min (3, d i sc [a]) = 1$
5	discover $d$ via tree edge $c - d$	$d i sc [d] = l o w [d] = 4$
6	discover $e$ via tree edge $d - e$	$d i sc [e] = l o w [e] = 5$
7	discover $f$ via tree edge $e - f$	$d i sc [f] = l o w [f] = 6$
8	$f$ sees $d$ : back edge	$l o w [f] = min (6, d i sc [d]) = 4$
9	discover $g$ via tree edge $f - g$	$d i sc [g] = l o w [g] = 7$ ; $g$ has no other neighbor, returns
10	$g$ returns to $f$	$l o w [f] = min (4, 7) = 4$ ; $l o w [g] = 7 > d i sc [f] = 6$ : bridge $f - g$ ; $l o w [g] \geq d i sc [f]$ : $f$ is a cut vertex
11	$f$ returns to $e$	$l o w [e] = min (5, 4) = 4$ ; $l o w [f] = 4 \neq > d i sc [e] = 5$ : no bridge, no cut
12	$e$ returns to $d$	$l o w [d] = min (4, 4) = 4$ ; $l o w [e] = 4 \geq d i sc [d] = 4$ : $d$ is a cut vertex (but $4 \neq > 4$ : $d - e$ is no bridge)
13	$d$ sees $f$ : second view of edge $d - f$	$l o w [d] = min (4, d i sc [f]) = 4$ , no change
14	$d$ returns to $c$	$l o w [c] = min (1, 4) = 1$ ; $l o w [d] = 4 > d i sc [c] = 3$ : bridge $c - d$ ; $l o w [d] \geq d i sc [c]$ : $c$ is a cut vertex
15	$c$ returns to $b$	$l o w [b] = min (2, 1) = 1$ ; $l o w [c] = 1 \neq > d i sc [b] = 2$ : nothing
16	$b$ returns to $a$	$l o w [a] = min (1, 1) = 1$ ; root $a$ has $1$ tree child: not a cut vertex
17	$a$ sees $c$ : second view of edge $a - c$	$l o w [a] = min (1, d i sc [c]) = 1$ , no change

Steps 13 and 17 show a quiet feature of undirected DFS: every non-tree edge is examined twice, once from each endpoint. The view from the ancestor side ( $d$ looking at $f$ , $a$ looking at $c$ ) relaxes against a larger discovery time and never changes anything; only the view from the descendant side (steps 4 and 8) matters. Both sightings are harmless as long as neither is mistaken for the parent edge.

The final state, drawn on the DFS tree — which for this graph is a single chain — with each vertex labeled $d i sc / l o w$ :

The DFS tree of the trace (a chain), back edges dashed, each vertex labeled

d i sc / l o w

. Bridges in blue: exactly the tree edges with

l o w [child] > d i sc [parent]

; cut vertices

c

d

f

ringed.

Reading the picture against the two criteria: the back edge $c \to a$ pins $l o w$ at $1$ across the first triangle, so nothing in ${a, b, c}$ is separated by removing one edge; the back edge $f \to d$ pins $l o w$ at $4$ across the second. The only tree edges whose child cannot climb past the parent are $c - d$ ( $l o w [d] = 4 > 3$ ) and $f - g$ ( $l o w [g] = 7 > 6$ ) — the two bridges. And the children $d$ , $e$ , $g$ certify $c$ , $d$ , $f$ as cut vertices via $l o w [v] \geq d i sc [u]$ , while the root $a$ , with a single tree child, is exempt.

Common pitfalls

The root always passes the non-root test. Since $d i sc [r oo t]$ is the smallest discovery time in its tree, every child $v$ satisfies $l o w [v] \geq d i sc [r oo t]$ . Apply the non-root rule to the root and it is flagged unconditionally. The root must be special-cased by counting tree children — and tree children, not neighbors: in a triangle the root has degree $2$ but only one tree child (the other neighbor is reached around the cycle), and it is correctly not a cut vertex.
Skipping the parent by vertex instead of by edge. With parallel edges, ignore neighbors equal to my parent skips both copies of a doubled edge, so the child looks trapped and the pair is reported as a bridge — but a doubled edge is never a bridge, since the twin copy survives any single cut. Track the id (or adjacency-list index) of the arrival edge and skip only that one; the second copy then acts as a legitimate back edge and lowers $l o w$ .
Relaxing back edges with $l o w [w]$ instead of $d i sc [w]$ . The definition permits at most one back edge per escape route, and the proofs lean on it. While $w$ is still gray, $l o w [w]$ is a moving target, and chaining through it can credit $v$ with escape routes that pass through vertices whose deletion is under test. Back edges relax against $d i sc [w]$ , tree edges against the child's finished $l o w$ .
Testing the wrong pair. The bridge test compares the child's low against the parent's disc: $l o w [v] > d i sc [u]$ . Both nearby variants fail. Comparing $d i sc [v] > d i sc [u]$ flags every tree edge, since children are always discovered later. Comparing $l o w [v] > l o w [u]$ breaks when $u$ has its own escape: attach a triangle $u, v, w$ below a vertex $r$ , plus a back edge from $u$ to $r$ 's parent $s$ . Then $l o w [u] = 1 < l o w [v] = d i sc [u]$ , so $l o w [v] > l o w [u]$ misreports the cycle edge $u - v$ as a bridge even though $u, v, w$ sit on a common cycle.
Recursion depth. The DFS tree of a path graph is the whole path; on a million-vertex chain the recursive version overflows most default call stacks. An explicit-stack rewrite must still perform the post-visit relaxation $l o w [u] \leftarrow min (l o w [u], l o w [w])$ when a child is popped, which takes some care to get right; test it on long chains.

The parallel-edge trap deserves a picture, because the buggy and correct runs differ on the smallest possible graph:

Parallel edges

{u, v}

: guarding by parent vertex skips both copies and misreports a bridge (left); guarding by the arrival edge's id lets the twin copy act as a back edge,

l o w [v] = d i sc [u]

, no bridge (right).

On the left, $v$ 's only edges both lead to its parent, both are skipped, and $l o w [v]$ stays at $d i sc [v] = 2 > d i sc [u] = 1$ : the doubled edge is declared a bridge, wrongly. On the right, only the arrival copy is skipped; the twin is processed as a back edge (dashed), $l o w [v]$ drops to $1 = d i sc [u]$ , and the strict test correctly reports nothing.

When to reach for this

The low-link machinery answers what breaks if one element fails, and it shows up wherever that question does: single points of failure in a computer or transport network, load-bearing joints in a mesh, and the decomposition of a graph into biconnected components before running algorithms that assume 2-connectivity. Two contrasts are worth keeping straight. First, bridges and cut vertices concern undirected connectivity; the analogous directed question is answered by strongly connected components, and Tarjan's SCC algorithm reuses this same low-link idea with a stack. Second, the criteria are about single failures only — surviving the loss of any $k$ edges or vertices is $(k + 1)$ -connectivity, which calls for maximum-flow techniques rather than one DFS.

bridges.pypython

from collections.abc import Hashable
from typing import Optional, TypeVar

from dfs_lowlink import EdgeIdentity
from graph import Graph

Label = TypeVar("Label", bound=Hashable)

def find_bridges(graph: Graph[Label]) -> set[frozenset[Label]]:
  """
    Every bridge of an undirected `graph`, each as a two-label frozenset.\n
    Works on disconnected graphs: the outer loop launches a DFS from every\n
    component. A duplicated edge between the same pair shares no id with its\n
    parallel copy, so it acts as a genuine back edge and (correctly) keeps\n
    the other copy from being reported as a bridge.\n
  """
  # canonical edge ids plus the per-vertex disc/low bookkeeping.
  identity: EdgeIdentity[Label] = EdgeIdentity(graph)
  discovery: dict[Label, int] = {}
  low_link: dict[Label, int] = {}
  bridges: set[frozenset[Label]] = set()
  timer: int = 0

  def explore(source: Label, parent_edge: Optional[int]) -> None:
    """
      Depth-first visit recording disc/low and reporting bridges.\n
    """
    # stamp discovery time; low-link starts at the vertex's own time.
    nonlocal timer
    timer += 1
    discovery[source] = low_link[source] = timer

    for edge in graph.vertex(source).outgoing:
      neighbor: Label = edge.target.label
      this_edge: int = identity.of(edge)

      # never walk back along the edge we arrived on.
      if this_edge == parent_edge:
        continue

      # tree edge: recurse, fold up the child's low-link, and test for a bridge.
      if neighbor not in discovery:
        explore(neighbor, this_edge)
        low_link[source] = min(low_link[source], low_link[neighbor])
        if low_link[neighbor] > discovery[source]:
          bridges.add(frozenset((source, neighbor)))

      # back edge: the subtree can climb to this already-seen ancestor.
      else:
        low_link[source] = min(low_link[source], discovery[neighbor])

  # launch a DFS in every component so disconnected graphs are covered.
  for vertex in graph.vertices:
    if vertex.label not in discovery:
      explore(vertex.label, None)
  return bridges

articulation_points.pypython

from collections.abc import Hashable
from typing import Optional, TypeVar

from dfs_lowlink import EdgeIdentity
from graph import Graph

Label = TypeVar("Label", bound=Hashable)

def find_articulation_points(graph: Graph[Label]) -> set[Label]:
  """
    Every articulation point (cut vertex) of an undirected `graph`.\n
    Handles disconnected graphs and multi-edges. Each component's DFS root is\n
    judged by its tree-child count; every other vertex by whether any child\n
    subtree can climb no higher than the vertex itself.\n
  """
  # canonical edge ids plus the per-vertex disc/low bookkeeping.
  identity: EdgeIdentity[Label] = EdgeIdentity(graph)
  discovery: dict[Label, int] = {}
  low_link: dict[Label, int] = {}
  cut_vertices: set[Label] = set()
  timer: int = 0

  def explore(source: Label, parent_edge: Optional[int]) -> None:
    """
      Depth-first visit recording disc/low and marking cut vertices.\n
    """
    # stamp discovery time; low-link starts at the vertex's own time.
    nonlocal timer
    timer += 1
    discovery[source] = low_link[source] = timer

    # count tree children so the root can be judged after the loop.
    tree_children: int = 0
    is_root: bool = parent_edge is None

    for edge in graph.vertex(source).outgoing:
      neighbor: Label = edge.target.label
      this_edge: int = identity.of(edge)

      # never walk back along the edge we arrived on.
      if this_edge == parent_edge:
        continue

      # tree edge: recurse, fold up the child's low-link, test the cut rule.
      if neighbor not in discovery:
        tree_children += 1
        explore(neighbor, this_edge)
        low_link[source] = min(low_link[source], low_link[neighbor])
        if not is_root and low_link[neighbor] >= discovery[source]:
          cut_vertices.add(source)

      # back edge: the subtree can climb to this already-seen ancestor.
      else:
        low_link[source] = min(low_link[source], discovery[neighbor])

    # a DFS root is a cut vertex exactly when it forks two or more subtrees.
    if is_root and tree_children >= 2:
      cut_vertices.add(source)

  # launch a DFS in every component so disconnected graphs are covered.
  for vertex in graph.vertices:
    if vertex.label not in discovery:
      explore(vertex.label, None)
  return cut_vertices

biconnected_components.pypython

from collections.abc import Hashable
from typing import Optional, TypeVar

from dfs_lowlink import EdgeIdentity
from graph import Graph

Label = TypeVar("Label", bound=Hashable)

def biconnected_components(
  graph: Graph[Label],
) -> list[list[frozenset[Label]]]:
  """
    The biconnected components of an undirected `graph`.\n
    Each component is a list of its edges (two-label frozensets); a lone\n
    bridge appears as a one-edge component. Handles disconnected graphs and\n
    multi-edges. Isolated vertices belong to no edge and so appear in no\n
    component.\n
  """
  identity: EdgeIdentity[Label] = EdgeIdentity(graph)
  discovery: dict[Label, int] = {}
  low_link: dict[Label, int] = {}
  components: list[list[frozenset[Label]]] = []

  # the stack holds edges (as ordered label pairs) in discovery order; a
  # component is the run popped off the top down to the splitting tree edge.
  edge_stack: list[tuple[Label, Label]] = []
  timer: int = 0

  def pop_component(boundary: tuple[Label, Label]) -> None:
    """
      Pop edges down to and including `boundary` into one component.\n
    """
    # drain the stack top until the splitting tree edge comes off.
    component: list[frozenset[Label]] = []
    while True:
      source, target = edge_stack.pop()
      component.append(frozenset((source, target)))
      if (source, target) == boundary:
        break
    components.append(component)

  def explore(source: Label, parent_edge: Optional[int]) -> None:
    """
      Depth-first visit that pushes edges and pops finished components.\n
    """
    # stamp discovery time; low-link starts at the vertex's own time.
    nonlocal timer
    timer += 1
    discovery[source] = low_link[source] = timer

    for edge in graph.vertex(source).outgoing:
      neighbor: Label = edge.target.label
      this_edge: int = identity.of(edge)

      # never walk back along the edge we arrived on.
      if this_edge == parent_edge:
        continue

      # tree edge: push it, recurse, then cut off a component at the threshold.
      if neighbor not in discovery:
        edge_stack.append((source, neighbor))
        explore(neighbor, this_edge)
        low_link[source] = min(low_link[source], low_link[neighbor])
        if low_link[neighbor] >= discovery[source]:
          pop_component((source, neighbor))

      # back edge: push once (only when ancestor) and lower the low-link.
      elif discovery[neighbor] < discovery[source]:
        edge_stack.append((source, neighbor))
        low_link[source] = min(low_link[source], discovery[neighbor])

  # launch a DFS in every component so disconnected graphs are covered.
  for vertex in graph.vertices:
    if vertex.label not in discovery:
      explore(vertex.label, None)
  return components

graph.pypython

from collections.abc import Hashable, Iterator
from typing import Generic, Optional, TypeVar


Label = TypeVar("Label", bound=Hashable)


class Edge(Generic[Label]):
  """
    A directed connection from `source` to `target`, carrying a weight.\n
  """

  def __init__(
    self,
    source: Vertex[Label],
    target: Vertex[Label],
    weight: float = 1.0,
  ) -> None:
    self.source: Vertex[Label] = source
    self.target: Vertex[Label] = target
    self.weight: float = weight

  def __repr__(self) -> str:
    return f"Edge({self.source.label!r} -> {self.target.label!r}, w={self.weight})"


class Vertex(Generic[Label]):
  """
    A graph vertex: a label plus the list of edges leaving it.\n
  """

  def __init__(self, label: Label) -> None:
    self.label: Label = label
    self.outgoing: list[Edge[Label]] = []

  def neighbors(self) -> list[Vertex[Label]]:
    """
      The vertices reachable from this one by a single edge.\n
    """
    return [edge.target for edge in self.outgoing]

  def edge_to(self, label: Label) -> Optional[Edge[Label]]:
    """
      The outgoing edge to the vertex with `label`, or None.\n
    """
    for edge in self.outgoing:
      if edge.target.label == label:
        return edge
    return None

  def __repr__(self) -> str:
    return f"Vertex({self.label!r})"


class Graph(Generic[Label]):
  """
    A graph of Vertex objects linked by Edge objects.\n
    Pass `directed=True` for a digraph; otherwise each `add_edge` inserts\n
    the reverse edge too.\n
  """

  def __init__(self, directed: bool = False) -> None:
    self.directed: bool = directed
    self._vertices: dict[Label, Vertex[Label]] = {}

  def add_vertex(self, label: Label) -> Vertex[Label]:
    """
      Return the vertex for `label`, creating it if it is absent.\n
    """
    # reuse the existing vertex, or mint and register a fresh one.
    vertex = self._vertices.get(label)
    if vertex is None:
      vertex = Vertex(label)
      self._vertices[label] = vertex
    return vertex

  def add_edge(
    self,
    source_label: Label,
    target_label: Label,
    weight: float = 1.0,
  ) -> None:
    """
      Connect two labels (creating either vertex as needed).\n
      Adds the reverse edge as well when the graph is undirected.\n
    """
    source = self.add_vertex(source_label)
    target = self.add_vertex(target_label)

    # link source to target, and mirror it back when undirected.
    source.outgoing.append(Edge(source, target, weight))
    if not self.directed:
      target.outgoing.append(Edge(target, source, weight))

  def vertex(self, label: Label) -> Vertex[Label]:
    """
      The vertex carrying `label` (raises KeyError if absent).\n
    """
    return self._vertices[label]

  @property
  def vertices(self) -> list[Vertex[Label]]:
    """
      Every vertex, in insertion order.\n
    """
    return list(self._vertices.values())

  @property
  def labels(self) -> list[Label]:
    """
      Every vertex label, in insertion order.\n
    """
    return list(self._vertices)

  def edges(self) -> Iterator[Edge[Label]]:
    """
      Each edge once — an undirected edge is yielded a single time.\n
    """
    # track undirected endpoint pairs so each is emitted only once.
    seen: set[frozenset[Label]] = set()

    for vertex in self._vertices.values():
      for edge in vertex.outgoing:
        # skip an undirected edge already yielded from the other endpoint.
        if not self.directed:
          endpoints = frozenset((edge.source.label, edge.target.label))
          if endpoints in seen:
            continue
          seen.add(endpoints)

        yield edge

  def __contains__(self, label: Label) -> bool:
    return label in self._vertices

  def __iter__(self) -> Iterator[Vertex[Label]]:
    return iter(self._vertices.values())

  def __len__(self) -> int:
    return len(self._vertices)

Connectivity, statically and dynamically

The block-cut tree. Grouping the graph's biconnected components (blocks) and articulation points into a tree — a node per block, a node per cut vertex, an edge whenever a cut vertex lies on a block — gives the block-cut tree, a compact map of exactly how the graph can fall apart.⁴ Any two vertices in the same block survive the loss of one vertex; a path between blocks in the tree passes through precisely the cut vertices that would disconnect them. Many is the graph still connected if I delete $v$ queries become tree lookups after one $O (V + E)$ preprocessing pass. The edge analogue, contracting each 2-edge-connected component, yields the bridge tree, in which each tree edge is a bridge of the graph.

Beyond single failures. Bridges and cut vertices are the $k = 1$ case of a hierarchy. Surviving any two edge failures is 3-edge-connectivity; the general question is the graph $k$ -connected is answered by max-flow (Menger's theorem equates the minimum $s$ – $t$ cut with the number of vertex- or edge-disjoint $s$ – $t$ paths), and global $k$ -edge-connectivity by the Stoer-Wagner minimum-cut algorithm. The single-DFS low-link trick is special to $k = 1$ — it is what makes that one case linear.

Dynamic connectivity. When edges are inserted and deleted online, recomputing bridges each time is wasteful. Holm, de Lichtenberg, and Thorup (2001) maintain full connectivity — and 2-edge-connectivity — under arbitrary updates in $O (log^{2} n)$ amortized time per operation using a hierarchy of spanning forests.⁵ This is the data structure behind interactive network-reliability tools and incremental mesh processing, where the graph changes faster than a from-scratch DFS could keep up.

Takeaways

A bridge (cut edge) and an articulation point (cut vertex) are the single points of failure of a network: removing one increases the component count. Their absence is 2-edge-connectivity and 2-vertex-connectivity (biconnectivity); cut edges and vertices are the seams between biconnected components.
DFS on an undirected graph produces only tree edges and back edges, with no cross or forward edges, so the only way out of a subtree is a back edge to an ancestor.
The low-link $l o w [u]$ is the smallest discovery time reachable from $u$ 's subtree via tree edges plus at most one back edge; compute it alongside $d i sc [u]$ in one recursion.
Bridge criterion: tree edge $(u, v)$ is a bridge $\leftrightarrow l o w [v] > d i sc [u]$ . Articulation criterion: a non-root $u$ is a cut vertex $\leftrightarrow$ some child has $l o w [v] \geq d i sc [u]$ ; the root is a cut vertex $\leftrightarrow$ it has $\geq 2$ children. The strict-vs-nonstrict gap ( $>$ vs $\geq$ ) is the whole distinction.
A single $O (V + E)$ DFS reports all bridges and cut vertices (and biconnected components). Guard the parent edge by id, not the parent vertex, to stay correct under multi-edges.

Skiena, §5 — Graph Traversal: edge- and vertex-connectivity, and articulation vertices as the weak points found by DFS low-links. ↩
CLRS, Ch. 22 — Elementary Graph Algorithms (DFS): an undirected DFS yields only tree and back edges; the parenthesis/white-path structure that grounds the low-link argument. ↩
Erickson, Ch. 6 — Depth-First Search: Tarjan's low-link computation for bridges, articulation points, and biconnected components in linear time. ↩
Hopcroft, J. & Tarjan, R. E. (1973), Algorithm 447: efficient algorithms for graph manipulation, Communications of the ACM 16(6), 372–378 — biconnected components and the block-cut structure via DFS. ↩
Holm, J., de Lichtenberg, K. & Thorup, M. (2001), Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Journal of the ACM 48(4), 723–760. ↩

The DFS-tree view

The bridge criterion

The articulation criterion

One DFS finds them all

A complete trace

Common pitfalls

When to reach for this

Connectivity, statically and dynamically

Takeaways

Footnotes