Bridge-Finding & Articulation Points

A Bit of History

The remarkable part is not only the $O(V+E)$ bound. During the ordinary return phase of DFS, each subtree summarizes whether it has an alternate route to an ancestor. One integer per vertex turns traversal history into a certificate of structural vulnerability.

What Does “Single Point of Failure” Mean?

These definitions apply to the whole undirected graph, including disconnected graphs. Removing an item is critical only if the number of components increases relative to the graph before removal.

Discovery Times and Low-Link Values

When DFS first visits $v$, assign a strictly increasing discovery time $disc[v]$. On return, compute the earliest-discovered vertex reachable from $v$’s DFS subtree by descending through tree edges and using at most one back edge:

start at $disc[v]$back edge uses $disc[w]$child return uses $low[x]$

The distinction in the last two updates matters. A visited neighbor contributes its own discovery time, while a completed DFS child contributes the child’s already-aggregated low value.

1. Enter a vertex. Set $disc[u]=low[u]=timer$ and increment the timer.
2. Explore each edge. Skip only the exact edge used to enter $u$. An unvisited neighbor becomes a DFS child; an already visited neighbor is a back-edge endpoint.
3. Return from a child. Apply $low[u]\leftarrow\min(low[u],low[v])$, then evaluate the bridge and articulation inequalities for tree edge $(u,v)$.
4. Restart as needed. Run DFS from every still-unvisited vertex so disconnected components are all covered.

Visual DFS Walkthrough

The graph below has two cyclic regions and a leaf. Solid lines form one possible DFS tree; dashed crimson curves are back edges. Each node shows $disc/low$. Low values propagate upward only after children finish.

The Three Tests

Seeing the Failure Impact

Correctness Intuition

In an undirected DFS, every non-tree edge connects a vertex to an ancestor. Therefore $low[v]$ exactly summarizes the highest ancestor reachable from the subtree rooted at $v$ without using its parent tree edge. If $low[v]>disc[u]$, no alternate route reconnects the child subtree even to $u$, so $(u,v)$ is a bridge. If $low[v]\ge disc[u]$, no route reaches a strict ancestor of $u$; deleting non-root $u$ separates that subtree. The root has no ancestor to bypass, so only the number of independent DFS children matters.

Implementation

The implementations below take an undirected edge list and assign each edge a unique ID. DFS skips the parent edge ID, not every edge leading to the parent vertex. That distinction makes parallel edges work correctly: the second parallel edge becomes an alternate back edge, so neither copy is falsely reported as a bridge.

def find_critical(n, edges):
    """Return (bridges, articulation vertices) for an undirected multigraph."""
    adj = [[] for _ in range(n)]
    for edge_id, (u, v) in enumerate(edges):
        adj[u].append((v, edge_id))
        adj[v].append((u, edge_id))

    disc = [-1] * n
    low = [0] * n
    bridges = []
    is_articulation = [False] * n
    timer = 0

    def dfs(u, parent_edge):
        nonlocal timer
        disc[u] = low[u] = timer
        timer += 1
        children = 0

        for v, edge_id in adj[u]:
            if edge_id == parent_edge:
                continue
            if disc[v] == -1:
                children += 1
                dfs(v, edge_id)
                low[u] = min(low[u], low[v])

                if low[v] > disc[u]:
                    bridges.append((min(u, v), max(u, v)))
                if parent_edge != -1 and low[v] >= disc[u]:
                    is_articulation[u] = True
            else:
                low[u] = min(low[u], disc[v])

        if parent_edge == -1 and children >= 2:
            is_articulation[u] = True

    for start in range(n):
        if disc[start] == -1:
            dfs(start, -1)

    articulation = [v for v in range(n) if is_articulation[v]]
    return sorted(bridges), articulation

edges = [(0,1), (1,2), (2,0), (2,3), (3,4)]
print(find_critical(5, edges))  # ([(2, 3), (3, 4)], [2, 3])

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int timer_;
vector<int> disc, low;
vector<bool> isArticulation;
vector<vector<pair<int,int>>> adj;  // (neighbor, edge ID)
vector<pair<int,int>> bridges;

void dfs(int u, int parentEdge) {
    disc[u] = low[u] = timer_++;
    int children = 0;
    for (auto [v, edgeId] : adj[u]) {
        if (edgeId == parentEdge) continue;
        if (disc[v] == -1) {
            ++children;
            dfs(v, edgeId);
            low[u] = min(low[u], low[v]);
            if (low[v] > disc[u]) bridges.push_back(minmax(u, v));
            if (parentEdge != -1 && low[v] >= disc[u]) isArticulation[u] = true;
        } else {
            low[u] = min(low[u], disc[v]);
        }
    }
    if (parentEdge == -1 && children >= 2) isArticulation[u] = true;
}

int main() {
    int n = 5;
    vector<pair<int,int>> edges = {{0,1},{1,2},{2,0},{2,3},{3,4}};
    adj.assign(n, {});
    for (int id = 0; id < (int)edges.size(); ++id) {
        auto [u, v] = edges[id];
        adj[u].push_back({v, id});
        adj[v].push_back({u, id});
    }
    timer_ = 0;
    disc.assign(n, -1);
    low.assign(n, 0);
    isArticulation.assign(n, false);
    for (int v = 0; v < n; ++v) if (disc[v] == -1) dfs(v, -1);

    sort(bridges.begin(), bridges.end());
    for (auto [u, v] : bridges) cout << "Bridge: " << u << "-" << v << '\n';
    for (int v = 0; v < n; ++v)
        if (isArticulation[v]) cout << "Articulation point: " << v << '\n';
}

import java.util.*;

class BridgesArticulation {
    static int timer;
    static int[] disc, low;
    static boolean[] isArticulation;
    static List<List<int[]>> adj; // entries are {neighbor, edge ID}
    static List<int[]> bridges;

    static void dfs(int u, int parentEdge) {
        disc[u] = low[u] = timer++;
        int children = 0;

        for (int[] next : adj.get(u)) {
            int v = next[0], edgeId = next[1];
            if (edgeId == parentEdge) continue;
            if (disc[v] == -1) {
                children++;
                dfs(v, edgeId);
                low[u] = Math.min(low[u], low[v]);

                if (low[v] > disc[u])
                    bridges.add(new int[]{Math.min(u, v), Math.max(u, v)});
                if (parentEdge != -1 && low[v] >= disc[u]) isArticulation[u] = true;
            } else {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
        if (parentEdge == -1 && children >= 2) isArticulation[u] = true;
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0,1},{1,2},{2,0},{2,3},{3,4}};
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int id = 0; id < edges.length; id++) {
            int u = edges[id][0], v = edges[id][1];
            adj.get(u).add(new int[]{v, id});
            adj.get(v).add(new int[]{u, id});
        }

        timer = 0;
        disc = new int[n];
        low = new int[n];
        isArticulation = new boolean[n];
        bridges = new ArrayList<>();
        Arrays.fill(disc, -1);
        for (int i = 0; i < n; i++) if (disc[i] == -1) dfs(i, -1);

        for (int[] b : bridges) System.out.println("Bridge: " + b[0] + "-" + b[1]);
        for (int v = 0; v < n; v++)
            if (isArticulation[v]) System.out.println("Articulation point: " + v);
    }
}

Complexity Analysis

Each vertex is discovered once, and each undirected edge appears in two adjacency entries examined a constant number of times:

The $O(V+E)$ space includes the adjacency list, discovery and low arrays, output, and a recursion or explicit DFS stack. If the graph storage is considered part of the input, the additional working memory is $O(V)$ excluding the returned bridges.

Pitfalls and Useful Variants

After removing all bridges, the remaining connected components are 2-edge-connected components. Tracking a stack of traversed edges during the same DFS can produce vertex-biconnected blocks and the block–cut tree, which represents how articulation points connect those blocks.

Real-World Applications

Topology alone measures structural redundancy, not operational risk. A bridge with a rarely used backup outside the modeled graph may be less serious than it appears, while a non-bridge high-capacity link may still be operationally critical. Combine these results with capacities, demand, failure probabilities, and domain constraints.

Exercises

Limitations

For a static undirected topology, however, the low-link DFS is unusually powerful: one traversal produces a complete inventory of all single-edge and single-vertex connectivity failures.