Articulation Points and Bridges in Graphs — Tarjan's Algorithm

In 2003, a single power line failure in Ohio cascaded into the largest blackout in North American history — 55 million people without power for up to two days. The power grid had articulation points: nodes whose failure disconnected major portions of the network. Finding and hardening these nodes is infrastructure reliability engineering.

Tarjan's bridge-finding algorithm (1972) finds all articulation points and bridges in a single O(V+E) DFS pass. It is one of the most elegant DFS applications: maintaining just two numbers per node (discovery time and low value), you can determine the entire structural vulnerability of a graph. Network engineers use this analysis to identify single points of failure. Social network researchers use it to find 'brokers' — people whose removal splits communities.

Discovery Time and Low Value

Tarjan's algorithm uses two arrays: - disc[u]: The discovery time when vertex u is first visited in DFS - low[u]: The minimum discovery time reachable from the subtree rooted at u (including back edges)

The low value is the key: it tells us if a subtree has a back edge to an ancestor. If it doesn't, the connection to that subtree is a bridge or articulation point.

from collections import defaultdict

def find_articulation_and_bridges(graph: dict):
    visited = {}
    disc = {}
    low = {}
    parent = {}
    articulation = set()
    bridges = []
    timer = [0]

    def dfs(u):
        visited[u] = True
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        children = 0
        for v in graph[u]:
            if v not in visited:
                children += 1
                parent[v] = u
                dfs(v)
                low[u] = min(low[u], low[v])
                # Articulation point conditions:
                # 1. Root with ≥2 children
                if u not in parent and children > 1:
                    articulation.add(u)
                # 2. Non-root: no back edge from subtree to ancestor
                if u in parent and low[v] >= disc[u]:
                    articulation.add(u)
                # Bridge condition: low[v] > disc[u]
                if low[v] > disc[u]:
                    bridges.append((u, v))
            elif v != parent.get(u):  # back edge
                low[u] = min(low[u], disc[v])

    for node in graph:
        if node not in visited:
            dfs(node)
    return articulation, bridges

graph = defaultdict(list)
edges = [(1,2),(1,3),(2,3),(3,4),(4,5),(4,6),(5,6),(6,7)]
for u,v in edges:
    graph[u].append(v)
    graph[v].append(u)

ap, br = find_articulation_and_bridges(graph)
print(f'Articulation points: {ap}')  # {3, 4, 6}
print(f'Bridges: {br}')              # [(3,4),(6,7)]

Understanding the Conditions

Bridge (u,v): Edge (u,v) is a bridge if low[v] > disc[u]. This means the subtree rooted at v has no back edge reaching u or any ancestor of u — the only connection is through edge (u,v).

Articulation point: 1. Root of DFS tree with ≥2 children: removing it disconnects children subtrees from each other. 2. Non-root u where low[v] ≥ disc[u] for some child v: the subtree rooted at v has no back edge to an ancestor of u — it can only reach above u through u itself.

Applications

Network reliability: Articulation points = single points of failure in a network. Removing them disconnects the network — critical routers or hubs.

Social networks: Articulation points = brokers — people whose removal splits communities.

Biconnected components: Maximal subgraphs with no articulation points — 2-connected components with redundant paths between all vertex pairs.

Electronic circuits: Bridges = single connections whose failure breaks the circuit.

Frequently Asked Questions