Bridge-Finding & Articulation Points

A Bit of History

Robert Tarjan — already met twice in this series for Tarjan's SCC algorithm and the Chu-Liu/Edmonds refinement from the previous deep dive — introduced the low-link-value DFS technique in the very same landmark 1972 paper, "Depth-First Search and Linear Graph Algorithms," that gave the field Tarjan's SCC algorithm. Part 8 defined bridges (edges whose removal disconnects the graph) and articulation points (vertices whose removal disconnects the graph) conceptually, but deferred the actual linear-time detection algorithm to this dedicated deep dive.

Working Principle: Low-Link Values

Run a single DFS, assigning each vertex a discovery time \(disc[v]\) (the order it was first visited) exactly as in Tarjan's SCC algorithm. Alongside this, compute a low-link value \(low[v]\): the smallest discovery time reachable from \(v\)'s DFS subtree using at most one "back edge" (an edge to an ancestor in the DFS tree).

$$low[v] = \min\Big(disc[v],\ \min_{(v,w) \text{ back edge}} disc[w],\ \min_{(v,u) \text{ tree edge}} low[u]\Big)$$

Once every vertex's \(low\) value is computed, two simple tests reveal every bridge and articulation point:

• Bridge test: a tree edge \((u,v)\) (with \(v\) a DFS-child of \(u\)) is a bridge if and only if \(low[v] > disc[u]\) — meaning \(v\)'s entire subtree has no back edge reaching \(u\) or higher, so removing \((u,v)\) truly disconnects it.
• Articulation point test: a non-root vertex \(u\) is an articulation point if it has some DFS-child \(v\) with \(low[v] \geq disc[u]\) (the subtree can reach back to \(u\) itself but no further up, so removing \(u\) strands it); the DFS root is a special case, an articulation point only if it has 2 or more DFS-children.

Worked Example

On a graph shaped like two triangles sharing a single vertex \(C\) (as in the Blossom Algorithm's worked example), a DFS from any starting vertex assigns \(C\) a low-link value that cannot escape below its own discovery time via either triangle alone — marking \(C\) as an articulation point (removing it disconnects the two triangles), while every edge within either triangle fails the bridge test (each triangle offers an alternate back-edge route around any single edge), correctly identifying zero bridges but one articulation point in this graph.

Correctness

The correctness argument mirrors Tarjan's SCC algorithm's own low-link reasoning: \(low[v]\) precisely captures "the highest ancestor \(v\)'s subtree can reach without going through \(v\)'s parent edge." If that value never climbs above \(u\)'s own discovery time, no back edge from \(v\)'s subtree bypasses \(u\) — meaning \(u\) (for articulation points) or the edge \((u,v)\) (for bridges) is structurally essential to keeping that subtree connected to the rest of the graph, exactly the definitions from Part 8.

Complexity Analysis

A single DFS pass computes both discovery times and low-link values together, with each edge examined a constant number of times:

$$\text{Time: } O(V + E) \qquad \text{Space: } O(V)$$

Linear time — matching Tarjan's SCC algorithm's own bound, and confirming that finding every single point of failure in a network costs no more than simply traversing it once.

Implementation

def find_bridges_and_articulation_points(n, adj):
    """
    n: number of vertices. adj[v]: list of neighbors (undirected graph).
    Returns (bridges, articulation_points).
    """
    disc = [-1] * n
    low = [0] * n
    bridges = []
    articulation_points = set()
    timer = [0]

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

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

                if low[v] > disc[u]:
                    bridges.append((u, v))
                if parent != -1 and low[v] >= disc[u]:
                    articulation_points.add(u)
            else:
                low[u] = min(low[u], disc[v])

        if parent == -1 and children >= 2:
            articulation_points.add(u)

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

    return bridges, articulation_points

adj = [[1,2],[0,2],[0,1,3],[2,4],[3]]  # two triangles-ish shape with a tail
print(find_bridges_and_articulation_points(5, adj))

#include <vector>
#include <set>
#include <iostream>
using namespace std;

int timer_ = 0;
vector<int> disc, low;
vector<vector<int>> adj;
vector<pair<int,int>> bridges;
set<int> articulationPoints;

void dfs(int u, int parent) {
    disc[u] = low[u] = timer_++;
    int children = 0;

    for (int v : adj[u]) {
        if (v == parent) continue;
        if (disc[v] == -1) {
            children++;
            dfs(v, u);
            low[u] = min(low[u], low[v]);

            if (low[v] > disc[u]) bridges.push_back({u, v});
            if (parent != -1 && low[v] >= disc[u]) articulationPoints.insert(u);
        } else {
            low[u] = min(low[u], disc[v]);
        }
    }
    if (parent == -1 && children >= 2) articulationPoints.insert(u);
}

int main() {
    int n = 5;
    adj.assign(n, {});
    vector<pair<int,int>> edges = {{0,1},{0,2},{1,2},{2,3},{3,4}};
    for (auto& [u, v] : edges) { adj[u].push_back(v); adj[v].push_back(u); }

    disc.assign(n, -1);
    low.assign(n, 0);
    for (int i = 0; i < n; i++) if (disc[i] == -1) dfs(i, -1);

    for (auto& [u, v] : bridges) cout << "Bridge: " << u << "-" << v << endl;
    for (int v : articulationPoints) cout << "Articulation point: " << v << endl;
    return 0;
}

import java.util.*;

class BridgesArticulation {
    static int timer = 0;
    static int[] disc, low;
    static List<List<Integer>> adj;
    static List<int[]> bridges = new ArrayList<>();
    static Set<Integer> articulationPoints = new HashSet<>();

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

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

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

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

        disc = new int[n];
        low = new int[n];
        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]);
        System.out.println("Articulation points: " + articulationPoints);
    }
}

Real-World Applications

Exercises

1. Trace through the worked example (two triangles sharing vertex \(C\)) by hand, computing discovery times and low-link values for every vertex.
2. Explain in your own words why the DFS root needs a special-case rule (articulation point only if it has 2+ children) that non-root vertices don't need.
3. Construct a small graph with exactly one bridge and no articulation points, and explain why this combination is impossible (hint: think about what a bridge implies about its endpoints).
4. Challenge: Modify the implementation to also compute the block-cut tree (previewed in Part 8) directly from the articulation points and 2-edge-connected components found.

Limitations