Bridges and Articulation Points with Tarjan's Low-Link Algorithm: One DFS, Two Answers, and the Details That Break Real Implementations

The DFS tree, and why undirected graphs make this easy

Run a depth-first search from any vertex. The edges along which the search first reaches a new vertex form a DFS tree (a forest, if the graph is disconnected). Every other edge is a non-tree edge. In a directed graph non-tree edges come in three kinds (back, forward and cross), but in an undirected graph there is only one: every non-tree edge joins a vertex to one of its own ancestors or descendants. There are no cross edges: if DFS at u sees an unvisited neighbour v, it descends into it immediately, so v ends up inside u's subtree.

The whole algorithm rests on that fact. Apart from the tree edge to its parent, a subtree can stay connected to the rest of the graph only through a back edge climbing from inside it to an ancestor above it. If no such escape route exists, the subtree's parent is the only door in and out.

Discovery time and low-link

Give every vertex a discovery time disc[u]: a counter value assigned the moment DFS first visits it. Ancestors always have smaller discovery times than their descendants. Then define the low-link:

low[u] = the smallest discovery time reachable from u by going down zero or more tree edges into u's subtree and then following at most one back edge.

You compute it bottom-up as the search unwinds. Start with low[u] = disc[u]. For each back edge u - w, take low[u] = min(low[u], disc[w]). When a child v finishes, take low[u] = min(low[u], low[v]), because anything v's subtree can reach, u's subtree can reach too.

Now the two conditions follow almost by definition. For a tree edge from parent p to child v:

• Bridge if low[v] > disc[p]: nothing in v's subtree reaches p or above except through p - v.
• Articulation point (non-root p) if low[v] >= disc[p] for some child v: the subtree climbs back to p but no higher. A back edge to p saves the edge, not the subtree once p is gone; hence >=.
• The root has no ancestors, so the second rule would flag it whenever it has a child. Instead the root is an articulation point exactly when it has two or more DFS children: DFS could not reach the second subtree from the first except back through the root.

Both checks run when a child finishes, so one pass produces both lists. Each vertex is visited once and each edge examined twice, giving O(V + E) time and memory.

A worked example by hand

Take nine vertices forming three triangles: 0-1-2, 3-4-5 and 6-7-8, joined by the edges 1-3 and 4-6. Anyone can see the answer by eye (the two connecting edges are bridges, and their four endpoints are cut vertices), which makes it a good graph for checking the mechanics. Start DFS at 0 and visit neighbours in edge order.

DFS goes 0, 1, 2; the back edge 2-0 gives low[2] = 0, which flows up to 1. Then 1 enters 3, 4, 5; the back edge 5-3 gives low = 3 for 5 and 4. Then 4 enters 6, 7, 8; the back edge 8-6 gives low = 6 for 8, 7 and 6. The checks, as each child finishes:

Result: bridges 1-3 and 4-6, articulation points 1, 3, 4 and 6. That matches the answer by eye and the output of the code below.

An implementation that survives real graphs

Textbook versions are recursive, and a path of a million vertices means a million-deep recursion: Python's default limit is 1,000, and Java or C++ thread stacks overflow. The version below keeps an explicit stack of (vertex, entering edge, next neighbour index) frames on the heap, and records the edge id used to enter each vertex rather than the parent vertex.

def bridges_and_cut_vertices(n, edges):
    """edges: list of (a, b) pairs on vertices 0..n-1; parallel edges allowed."""
    adj = [[] for _ in range(n)]
    for eid, (a, b) in enumerate(edges):
        adj[a].append((b, eid))
        adj[b].append((a, eid))
    disc = [-1] * n          # discovery time, -1 = unvisited
    low = [0] * n
    timer = 0
    bridges, cut = [], set()
    for root in range(n):
        if disc[root] != -1:
            continue
        disc[root] = low[root] = timer; timer += 1
        root_children = 0
        stack = [(root, -1, 0)]          # (vertex, edge id used to enter it, next adjacency index)
        while stack:
            u, in_edge, i = stack[-1]
            if i < len(adj[u]):
                stack[-1] = (u, in_edge, i + 1)
                v, eid = adj[u][i]
                if eid == in_edge:
                    continue             # skip only the edge we arrived by, not every edge to the parent
                if disc[v] == -1:        # tree edge: descend
                    disc[v] = low[v] = timer; timer += 1
                    if u == root:
                        root_children += 1
                    stack.append((v, eid, 0))
                else:                    # already visited: use its DISCOVERY time
                    low[u] = min(low[u], disc[v])
            else:
                stack.pop()
                if stack:                # u is finished; fold it into its parent p
                    p = stack[-1][0]
                    low[p] = min(low[p], low[u])
                    if low[u] > disc[p]:
                        bridges.append(edges[in_edge])
                    if p != root and low[u] >= disc[p]:
                        cut.add(p)
        if root_children >= 2:
            cut.add(root)
    return bridges, sorted(cut)

Running it on the worked example:

edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3), (4, 6), (6, 7), (7, 8), (8, 6)]
print(bridges_and_cut_vertices(9, edges))
# ([(4, 6), (1, 3)], [1, 3, 4, 6])

The outer loop starts a fresh tree in each component, so disconnected graphs and isolated vertices work. Drop self-loops before building the adjacency list: they never affect connectivity, and each appears twice in one vertex's list.

Four details that break implementations

1. Skipping the parent vertex instead of the parent edge. With if v == parent: continue, two parallel edges between a and b are both skipped, and a - b is reported as a bridge although removing one copy leaves the other. Redundant cables between two switches are exactly this case. Skipping by edge id skips only the edge you arrived on.

2. Using low[w] instead of disc[w] on a back edge. Harmless for bridges, wrong for articulation points. Take edges 0-1 twice, 1-2, 2-3, 3-1. Vertex 1 is a cut vertex. DFS from 0 reaches 1, whose parallel edge to 0 sets low[1] = 0. When 3's back edge to 1 uses low[1], low[3] and low[2] become 0 and the test at 1 fails: the disc version reports [1], the low version nothing (both were run to confirm). Chaining through another vertex's low-link lets a subtree borrow an escape route that runs through the very vertex being tested.

3. Applying the non-root rule to the root. low[v] >= disc[root] is always true, so every root with a child would be flagged. Count the root's DFS children instead.

4. Recursing on big graphs. Deep recursion is the most common production crash; the iterative form above avoids it.

Beyond two lists: biconnected components and the bridge tree

Articulation points split a graph into biconnected components (blocks): maximal subgraphs with no cut vertex of their own. To extract them, push each edge on a stack as you traverse it; when a child v of p finishes with low[v] >= disc[p], pop edges down to and including p - v: those form one block. A graph is planar exactly when each block is, which is why linear-time planarity testing starts here.

Bridges give a coarser split. Delete every bridge and the remaining components are the 2-edge-connected components, which survive any single link failure. Contract each to a node, add the bridges back, and you get the bridge tree; "how many single-link failures can separate A from B?" becomes a path length in that tree. In the example it is a path of three nodes, one per triangle.

For tolerance to k failures rather than one, use flows: by Menger's theorem, edge connectivity between two vertices equals unit-capacity max flow, computed with, for example, Edmonds-Karp.

Testing it against a brute-force oracle

Graph code fails on shapes you did not think of: parallel edges, isolated vertices, several components. The cheapest protection is a slow, obviously correct oracle run on thousands of random small graphs. This one removes each edge and vertex in turn and counts components with union-find (removing an isolated vertex lowers the count, hence the adjustment).

import random

def components(n, edges, drop_vertex=None, drop_edge=None):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    for i, (a, b) in enumerate(edges):
        if i == drop_edge or drop_vertex in (a, b):
            continue
        parent[find(a)] = find(b)
    return len({find(x) for x in range(n) if x != drop_vertex})

def brute(n, edges):
    base = components(n, edges)
    br = sorted(edges[i] for i in range(len(edges)) if components(n, edges, drop_edge=i) > base)
    cut = []
    for v in range(n):
        isolated = all(v not in e for e in edges)
        if components(n, edges, drop_vertex=v) > base - (1 if isolated else 0):
            cut.append(v)
    return br, cut

random.seed(1)
for _ in range(4000):
    n = random.randint(1, 9)
    edges = [(a, b) for a, b in ((random.randrange(n), random.randrange(n))
                                 for _ in range(random.randint(0, 14))) if a != b]
    fast_b, fast_c = bridges_and_cut_vertices(n, edges)
    assert (sorted(fast_b), fast_c) == brute(n, edges), (n, edges)

The implementation above passes all 4,000 cases. A fixed seed makes failures reproducible, and small graphs find nearly every structural bug.

Where this shows up, and what it costs at scale

Common uses:

• Network and infrastructure resilience. Model routers, links, power substations or pipelines as a graph; the cut vertices and bridges are the single points of failure to make redundant first.
• Service dependency graphs. Treated as undirected, a cut vertex is a service whose outage partitions the system; strict directed reachability needs strong articulation points, a harder problem.
• Road and transit networks. Bridges find the only road into a settlement, which matters for evacuation and maintenance planning.

At scale, memory access dominates. For tens of millions of edges, store adjacency in compressed sparse row form (offsets, neighbours and edge-id arrays) and keep disc and low in typed integer arrays. DFS order makes the algorithm sequential; parallel alternatives exist but only pay off on very large graphs. If the graph changes rarely, recompute from scratch; see Big-O analysis for judging when linear recomputation is cheap enough.

Trade-offs and alternatives

The same disc/low idea, plus a vertex stack, gives Tarjan's strongly connected components algorithm for directed graphs.

What to do next

1. Implement the iterative version with edge ids and reproduce bridges 1-3, 4-6 and cut vertices 1, 3, 4, 6 on the example.
2. Run the brute-force oracle on thousands of random multigraphs.
3. Swap disc for low on back edges and confirm the oracle catches it on the pitfall graph.
4. Extend the code to emit biconnected components and the bridge tree.
5. Run it on one real graph you own (network, service calls, roads) and rank cut vertices by how much they would strand.
6. For tolerance to more than one failure, use max-flow connectivity on the critical pairs.