Skip to content
Tutorials Center
My learning

Topics

Lesson 144 of 225 ยท Shortest Paths and Spanning Trees

Bridges and Articulation Points

Find bridges, articulation points and biconnected components in an undirected graph with one DFS and low-link values, including an iterative version for big graphs.

A network is only as strong as its weakest link. In a road map there may be a single bridge that connects an island to the mainland; in a computer network there may be one router whose failure splits the network in two. Finding these single points of failure is a classic graph problem.

  • A bridge (or cut edge) is an edge whose removal makes the graph less connected: some vertices that could reach each other no longer can.
  • An articulation point (or cut vertex) is a vertex whose removal, together with its edges, does the same.

A graph with no bridges is called 2-edge-connected; one with no articulation points is biconnected (2-vertex-connected). You will learn how to detect both in a single depth-first search in O(V + E), using a quantity called the low-link value. The idea is the same one that powers Tarjan's strongly connected components, applied to undirected graphs. This lesson assumes you know DFS and adjacency lists.

An example graph

TEXT
   0 ----- 1 ----------- 3 ----- 4
   |      /               |      |
   |     /                |      |
   +--- 2                 +----- 5 ----- 6 ----- 7

edges: 0-1  1-2  2-0   1-3   3-4  4-5  5-3   5-6   6-7

Triangles {0, 1, 2} and {3, 4, 5} are solid blocks: remove any one edge or vertex inside a triangle and the rest stays connected. The edges 1-3, 5-6 and 6-7 are different: each is the only link between two parts of the graph, so each is a bridge. The articulation points are the vertices where those bridges attach: 1, 3, 5 and 6. Vertex 7 is a leaf; removing it only removes itself.

Brute force

Remove each edge in turn and count components with a DFS; if the count goes up, that edge is a bridge. Do the same for each vertex to find articulation points. Each test costs O(V + E) and there are E edges and V vertices to test, so the total is O(E ยท (V + E)), which is far too slow for large graphs but easy to trust.

Python Brute force: remove one thing at a time

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For a vertex, the removed vertex disappears from the count, so we compare with the original number of components: if removing v leaves more components than the graph had before, v held things together. (If v was an isolated vertex, removing it reduces the count and is correctly not reported.)

DFS tree and back edges

Run a DFS and look at the edges it sees. In an undirected graph every edge is one of just two kinds:

  • a tree edge, used to discover a new vertex, or
  • a back edge, pointing from a vertex to one of its ancestors in the DFS tree. (There are no cross edges in undirected DFS.)
TEXT
DFS tree from 0   (tree edges: |   back edges: listed on the right)

   0                 back edge 2 -> 0   (2 reaches an ancestor)
   |
   1                 back edge 5 -> 3
  / \
 2   3
     |
     4
     |
     5
     |
     6
     |
     7

A back edge is a bypass: it lets a subtree reach "above" itself without using the tree edge that leads into it. An edge is a bridge precisely when no bypass exists for the subtree below it.

For each vertex v, record

  • disc[v]: the time at which DFS first visits v (0, 1, 2, ...), and
  • low[v]: the smallest disc value that can be reached from the subtree of v using any number of tree edges down and then at most one back edge up.

Compute low as DFS returns:

TEXT
low[u] = min( disc[u],
              disc[w]    for every back edge u ~ w (w is an ancestor of u),
              low[v]     for every child v of u in the DFS tree )

Then:

  • A tree edge u -> v is a bridge if low[v] > disc[u]: the subtree of v cannot reach u or anything above u except through this very edge.
  • A non-root vertex u is an articulation point if it has a child v with low[v] >= disc[u]: the subtree of v can reach u at best, but never above it, so removing u cuts that subtree off. Note the >=, which differs from the bridge condition by one character. A back edge landing exactly on u saves the edge, but not the vertex.
  • The root is an articulation point if and only if it has two or more DFS children. (With one child, removing the root leaves a connected tree.)

One more detail: when exploring from u you must not treat the edge you just came along as a back edge to u's parent, or every edge would look like a bypass of itself. Skip the edge (by id), not the parent vertex, so that parallel edges between the same two vertices are handled correctly (two parallel edges between a pair mean neither is a bridge).

Python Bridges and articulation points with one DFS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the disc and low rows together. Inside the first triangle, vertices 1 and 2 have low = 0: the back edge 2 ~ 0 lets them reach the root's time. Vertex 3 is discovered at time 3 and its low is also 3, because nothing in its subtree reaches above 3. That is exactly the bridge test low[3] > disc[1] for the tree edge 1 -> 3. The same happens for the edges 5 -> 6 and 6 -> 7.

Watch out: the root of the DFS tree needs the special rule. Using low[v] >= disc[u] for the root is always true (nothing is discovered before the root), which would flag every root with a child. That is why the code checks parent_edge != -1 for non-roots and counts children for the root.

Doing it iteratively

For big graphs (say a long road network with hundreds of thousands of vertices) recursion will exceed Python's default limit of about a thousand frames, and raising the limit risks crashing the interpreter. Keep an explicit stack that remembers (vertex, parent edge, next neighbor index). When a vertex finishes, push its low up to its parent, which is exactly what the recursive version does after the call returns.

Python Iterative bridge finding on 5000 vertices

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every edge of a path is a bridge (cut any one and the path falls apart). In a ring no single edge is critical because there is a second way around. All three runs take O(V + E).

Biconnected components

A biconnected component (BCC, also called a block) is a maximal group of edges such that any two of them lie on a common simple cycle, plus bridge edges as one-edge blocks. Blocks share only articulation points, and the blocks of a graph form a tree structure (the block-cut tree). To list them, keep a stack of edges during the DFS; whenever a child v of u satisfies low[v] >= disc[u], pop edges down to (u, v); those edges form one block.

Python Listing biconnected components

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two triangles appear as blocks of three vertices, and each bridge appears as a block of two. Vertices that appear in more than one block (1, 3, 5, 6) are exactly the articulation points.

2-edge-connected components and the bridge tree

If you only delete the bridges, the graph falls apart into 2-edge-connected components: groups where every pair of vertices is joined by two edge-disjoint paths. Contract each group into a single node and add the bridges between them, and you get the bridge tree, which is always a tree (a cycle in it would mean those edges are not bridges). It makes questions about bridges easy: for example, adding edges to make the whole graph bridge-free needs ceil(leaves / 2) new edges.

Python Bridge tree and the edges needed to remove all bridges

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The bridge tree here is a chain of four nodes, so it has two leaves, and a single new edge between its ends closes it into a cycle with no bridges left.

Complexity

One DFS visits each vertex and each edge a constant number of times, so bridges, articulation points and biconnected components all take O(V + E) time. Space is O(V) for disc, low and the recursion or explicit stack (plus O(E) for the edge stack when listing blocks). Compare this with the brute force at O(E ยท (V + E)); on a graph with 100,000 edges the difference is between a blink and never finishing.

Common mistakes

  • Using >= for bridges or > for articulation points. Bridges need low[v] > disc[u]; articulation points need low[v] >= disc[u].
  • Skipping the parent vertex instead of the parent edge. This misses parallel edges: two edges between the same vertices are not bridges.
  • Forgetting the root rule. The root is a cut vertex only with two or more DFS children.
  • Applying it to directed graphs. The directed analog is the SCC computation in Strongly Connected Components. Treat undirected input only.
  • Forgetting disconnected graphs. Start a DFS from every unvisited vertex, as in all the code above.
  • Hitting the recursion limit on long chains; use the iterative form.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. When is a tree edge u -> v in the DFS tree a bridge?

    If low[v] > disc[u], the subtree of v cannot reach u or above except through this edge, so removing the edge disconnects it.
  2. 2. When is the root of the DFS tree an articulation point?

    With two or more children, those subtrees are only connected through the root. With one child, removing the root leaves a connected tree.
  3. 3. Why should the DFS skip the parent edge by id instead of skipping the parent vertex?

    With two parallel edges, the second one is a legitimate back edge to the parent; skipping the whole parent vertex would hide it.
  4. 4. What is the time complexity of finding all bridges with the low-link DFS?

    A single DFS processes each vertex and edge a constant number of times.
  5. 5. A tree on n vertices (no cycles) has how many bridges?

    Every edge of a tree is the only connection between its two sides, so all n - 1 edges are bridges.

Summary

  • A bridge is an edge, an articulation point a vertex, whose removal disconnects part of the graph.
  • One DFS with disc and low finds both in O(V + E).
  • Tree edge u -> v is a bridge if low[v] > disc[u]; non-root u is an articulation point if some child has low[v] >= disc[u]; the root needs two or more children.
  • Skip the parent edge, not the parent vertex.
  • An edge stack yields the biconnected components; removing bridges yields the 2-edge-connected components and the bridge tree.
  • Use an explicit stack for deep graphs.

Next: Maximum Flow and Matching