Bridges and Articulation Points in Python (Tarjan)

By Engr. Henry Akpan

Finding the Weak Points in a Network

Which road, if closed, would cut a town off from the rest of the state? Which router, if it failed, would split a computer network in two? Which person in a social network is the only link between two groups? In graph terms these are bridges (edges whose removal disconnects the graph) and articulation points or cut vertices (vertices whose removal disconnects it). The obvious approach removes each edge or vertex in turn and checks connectivity, which is slow. Tarjan's algorithm finds all bridges and articulation points in a single depth-first search, in linear time. This tutorial explains the idea of discovery times and low-link values, gives a Python implementation, and checks it against the brute-force method. All outputs come from running the code.

Definitions

Consider an undirected, connected graph.

  • An edge is a bridge if removing it increases the number of connected components. A bridge is never part of a cycle: if an edge lies on a cycle, the rest of the cycle offers another route.
  • A vertex is an articulation point if removing it (and its edges) increases the number of components.
  • A graph with no articulation points is called biconnected: it survives the loss of any single vertex. Network designers aim for this.

Our example graph has 9 vertices. Vertices 0, 1, 2 form a triangle; 1 connects to 3; 3, 4, 5 form a triangle; 5 connects to 6; 6, 7, 8 form a triangle. Intuitively, the single links 1–3 and 5–6 are bridges, and 1, 3, 5 and 6 are articulation points.

from collections import defaultdict

edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3), (5, 6), (6, 7), (7, 8), (8, 6)]
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)
n = 9
print({v: sorted(graph[v]) for v in range(n)})

Output:

{0: [1, 2], 1: [0, 2, 3], 2: [0, 1], 3: [1, 4, 5], 4: [3, 5], 5: [3, 4, 6], 6: [5, 7, 8], 7: [6, 8], 8: [6, 7]}

The Key Idea: Discovery Time and Low-Link

Run a depth-first search (DFS) and record two numbers for each vertex u:

  • disc[u]: the time at which DFS first discovered u (0, 1, 2, …).
  • low[u]: the smallest discovery time reachable from u's subtree in the DFS tree, using at most one back edge (an edge to an already-visited ancestor). It measures how far "up" the tree u's subtree can reach without using the edge to its parent.

Then, for a tree edge from parent u to child v:

  • The edge u–v is a bridge if low[v] > disc[u]: nothing in v's subtree can reach u or above except through this edge.
  • A non-root vertex u is an articulation point if some child v has low[v] ≥ disc[u]: v's subtree cannot reach above u, so removing u cuts it off.
  • The root of the DFS is an articulation point only if it has two or more children in the DFS tree.

The two conditions differ only by "≥" versus ">": for an articulation point, the subtree may reach u itself (u is removed anyway), but for a bridge it must not.

Bridges and Articulation Points in Python

def bridges_and_cut_vertices(n, graph):
    disc = [-1] * n
    low = [0] * n
    bridges, cut = [], set()
    timer = 0

    def dfs(u, parent):
        nonlocal timer
        disc[u] = low[u] = timer
        timer += 1
        children = 0
        for v in graph[u]:
            if disc[v] == -1:                 # tree edge
                children += 1
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.append((min(u, v), max(u, v)))
                if parent != -1 and low[v] >= disc[u]:
                    cut.add(u)
            elif v != parent:                 # back edge
                low[u] = min(low[u], disc[v])
        if parent == -1 and children >= 2:
            cut.add(u)

    for s in range(n):                        # handles disconnected graphs too
        if disc[s] == -1:
            dfs(s, -1)
    return sorted(bridges), sorted(cut), disc, low

b, c, disc, low = bridges_and_cut_vertices(n, graph)
print("bridges:", b)
print("articulation points:", c)
print("disc:", disc)
print("low: ", low)

Output:

bridges: [(1, 3), (5, 6)]
articulation points: [1, 3, 5, 6]
disc: [0, 1, 2, 3, 4, 5, 6, 7, 8]
low:  [0, 0, 0, 3, 3, 3, 6, 6, 6]

Reading the low values: vertices 0–2 can all reach time 0 (the triangle loops back to the start); vertices 3–5 can only reach 3; vertices 6–8 only 6. Each jump in low values marks a bridge. For edge 1–3, low[3] = 3 > disc[1] = 1, so it is a bridge.

The whole algorithm visits each vertex and edge once: O(V + E) time.

Note on parallel edges: the check v != parent assumes at most one edge between two vertices. If the graph can have duplicate edges, skip the parent by edge identity instead, since a doubled road is not a bridge.

Checking Against Brute Force

The brute-force method removes each edge (or vertex) and counts components with a simple BFS. It is O(E × (V + E)), far slower, but obviously correct, which makes it ideal for testing:

from collections import deque

def components(n, edge_list, removed_vertex=None):
    adj = defaultdict(list)
    for u, v in edge_list:
        if removed_vertex not in (u, v):
            adj[u].append(v); adj[v].append(u)
    seen, count = set(), 0
    for s in range(n):
        if s == removed_vertex or s in seen:
            continue
        count += 1
        seen.add(s)
        q = deque([s])
        while q:
            x = q.popleft()
            for y in adj[x]:
                if y not in seen:
                    seen.add(y); q.append(y)
    return count

base = components(n, edges)
brute_bridges = sorted((min(e), max(e)) for e in edges
                       if components(n, [f for f in edges if f != e]) > base)
brute_cut = [v for v in range(n) if components(n, edges, removed_vertex=v) > base]
print(brute_bridges == b, brute_cut == c)

Output:

True True

A Larger Random Test

import random

random.seed(7)
for trial in range(200):
    m = random.randint(2, 12)
    es = list({(min(a, b), max(a, b)) for a, b in
               ((random.randrange(m), random.randrange(m)) for _ in range(random.randint(1, 18))) if a != b})
    g = defaultdict(list)
    for u, v in es:
        g[u].append(v); g[v].append(u)
    fb, fc, _, _ = bridges_and_cut_vertices(m, g)
    base = components(m, es)
    assert fb == sorted(e for e in es if components(m, [f for f in es if f != e]) > base)
    assert fc == [v for v in range(m) if components(m, es, removed_vertex=v) > base]
print("200 random graphs agree")

Output:

200 random graphs agree

Removing an isolated vertex doesn't increase the component count (it removes one), so the brute-force definition and Tarjan's method agree even for disconnected graphs.

Practical Notes

  • Recursion depth: Python's default recursion limit is about 1,000, so for large graphs (long paths) either raise it with sys.setrecursionlimit or rewrite the DFS with an explicit stack.
  • Making a network robust: after finding bridges, adding one extra link between the components on each side removes that single point of failure. Critical infrastructure such as power grids, water pipes and fibre networks is analysed this way.
  • Related algorithms: the same low-link idea finds biconnected components (the "blocks" between articulation points) and, in directed graphs, strongly connected components (Tarjan's SCC algorithm).

Summary

  • Bridges and articulation points are the single edges and vertices whose loss disconnects a graph.
  • One DFS records disc[u] (discovery time) and low[u] (earliest time reachable from u's subtree with one back edge).
  • Tree edge u–v is a bridge if low[v] > disc[u]; a non-root u is an articulation point if some child has low[v] ≥ disc[u]; the root is one if it has two or more DFS children.
  • Tarjan's method runs in O(V + E); test it against a brute-force check on random graphs.

Related Tutorials