Bridges Finder

Pseudocode

Identical machinery to articulation points, with one comparison changed from >= to strictly greater than.

dfs(u, parent):
    disc[u] = low[u] = ++time

    for each neighbor v of u:
        if v == parent: continue      // skip the edge we came on
        if v is visited:
            low[u] = min(low[u], disc[v])    // back edge
        else:
            dfs(v, u)
            low[u] = min(low[u], low[v])
            if low[v] > disc[u]:
                report edge (u, v) as a bridge

The strict inequality is the whole difference from articulation points. low[v] > disc[u] says nothing in the subtree below v can reach u or anything above it, so the edge (u, v) is the only route and removing it disconnects the graph. Articulation points use low[v] >= disc[u], where equality means the subtree can reach u itself but no further, which strands the subtree if you delete the vertex u but not if you delete the single edge.

Worked example, step by step

Run the DFS from A on a triangle with a two-edge tail, the same graph used for articulation points, so the two tests can be compared on identical data.

Example graph: Undirected edges A-B, B-C and C-A forming a triangle, plus C-D and D-E.

1. Assign discovery times. Descending A, B, C, D, E gives discovery times 1, 2, 3, 4 and 5 respectively.
2. E is a dead end. E has only its parent D as a neighbour, so low[E] stays at 5.
3. D-E is a bridge. Returning to D, low[D] = min(4, low[E] = 5) = 4. Test the edge: low[E] = 5 > disc[D] = 4, so D-E is a bridge. Removing it isolates E, which is clearly right.
4. C-D is a bridge. At C the back edge C-A gives low[C] = min(3, disc[A] = 1) = 1, and folding in the child gives min(1, low[D] = 4) = 1. Test the edge to D: low[D] = 4 > disc[C] = 3, so C-D is a bridge too.
5. The triangle edges are not. At B, low[B] = min(2, low[C] = 1) = 1. Test the edge B-C: low[C] = 1 > disc[B] = 2 is false, so B-C is not a bridge. C can reach A without using B-C, so the edge has an alternative route. The same reasoning clears A-B and C-A.

The bridges are C-D and D-E. Note the contrast with articulation points on this identical graph, where the answer was the vertices C and D. Every edge of the triangle lies on a cycle and so has a detour, while every edge of the tail is the sole connection to what lies beyond it. The general rule falls out directly: an edge is a bridge exactly when it lies on no cycle.

Complexity, and where it comes from

Time: O(V + E) · Space: O(V)

One depth-first search with constant extra work per edge, so the cost is that of the traversal. Each vertex is visited once and each edge examined twice, once from each endpoint. The state is two integers per vertex plus the recursion stack, all O(V). The naive approach of removing each edge and testing connectivity costs O(E·(V + E)), so on a graph with 10,000 edges the low-link method is roughly four orders of magnitude faster.

When to use Bridge Finding, and when not to

The same DFS answers several related questions. Pick by whether the fragile thing is an edge, a vertex, or a whole region.

Common pitfalls

• Using >= instead of >. The articulation-point test is low[v] >= disc[u]; the bridge test is strictly low[v] > disc[u]. Using >= reports every tree edge into a vertex that cannot climb past its parent, which over-reports badly. One character separates the two algorithms.
• Skipping the parent by vertex instead of by edge. With parallel edges between u and v, the second edge is a genuine alternative route and neither one is a bridge. Skipping on vertex identity hides it and reports a bridge that does not exist. Track the specific edge you arrived on.
• Using low[v] rather than disc[v] for back edges. When you encounter a visited neighbour, fold in its discovery time, not its low-link. Using low[v] can import a value from an unrelated subtree and silently suppress genuine bridges.
• Applying it to directed graphs. Bridges are defined for undirected graphs. The directed question, which edges whose removal increases the number of strongly connected components, is a different problem needing different machinery.
• Forgetting disconnected components. One DFS covers one component only. Iterate over all vertices and start a fresh search from each unvisited one, or bridges in other components go unreported.

Frequently asked questions

What is a bridge in a graph?

A bridge, also called a cut edge, is an edge whose removal increases the number of connected components. Equivalently it is an edge that lies on no cycle: if there were a cycle through it, the rest of that cycle would provide an alternative route and removing the edge would disconnect nothing.

How do you find bridges in a graph?

Run a single depth-first search recording each vertex discovery time and low-link, the earliest discovery time reachable from its subtree via at most one back edge. A tree edge from u to child v is a bridge exactly when low[v] > disc[u], meaning nothing below v can reach u or above. The whole algorithm is O(V + E).

What is the difference between a bridge and an articulation point?

A bridge is an edge whose removal disconnects the graph; an articulation point is a vertex whose removal does. They come from the same DFS and differ by one comparison: strictly greater for bridges, greater or equal for articulation points. A graph can have one without the other.

Can a bridge be part of a cycle?

No, and this is the cleanest way to think about it. If an edge lies on a cycle, the remainder of that cycle is an alternative path between its endpoints, so removing the edge leaves the graph connected. Bridges are exactly the edges that lie on no cycle.

What are bridges used for?

Finding critical links in telecom backbones and fibre networks, essential roads and rail sections whose closure would split a region, fragile connections in power grids, and risk analysis of dependencies in software. On LeetCode the same problem appears as Critical Connections in a Network.