Skip to content

Bridges and articulation points

Use low-link DFS when an undirected graph asks which single edge or vertex can disconnect connectivity.

  • A bridge is an edge whose removal increases the number of components.
  • An articulation point is a vertex whose removal increases the number of components.

State meaning

  • tin[u]: discovery time of u.
  • low[u]: earliest discovery time reachable from u's DFS subtree using tree edges plus at most one back edge.

For a DFS tree edge u → v:

  • it is a bridge when low[v] > tin[u];
  • non-root u is an articulation point when low[v] >= tin[u] for at least one child v;
  • a DFS root is an articulation point only when it has at least two DFS-tree children.

The strict versus non-strict comparison is deliberate. A back edge from the child subtree to u protects the edge u-v, but removing u still separates that subtree.

flowchart LR
  accTitle: Low-link values distinguish a cycle edge from a bridge
  accDescr: Vertices zero, one, and two form a cycle, so the subtree at two can escape to ancestor zero. Vertex three is a leaf below one with no escape, so edge one-three is a bridge.
  A["0<br/>tin 0"] ---|"DFS tree edge"| B["1<br/>tin 1"]
  B ---|"DFS tree edge"| C["2<br/>tin 2"]
  C -.->|"back edge lowers low to 0"| A
  B ---|"bridge: low of 3 is greater than tin of 1"| D["3<br/>tin 3 · low 3"]
  C --> E["Cycle edge is protected<br/>subtree can reach an ancestor"]
  D --> F["Tail edge is critical<br/>subtree has no escape"]

The question at a DFS child is always: “Can this entire subtree escape above its parent without using the tree edge back to that parent?”

Tested bridge template

def find_bridges(vertex_count: int, edges: Sequence[tuple[int, int]]) -> list[tuple[int, int]]:
    """Return bridge edges in an undirected multigraph."""
    if vertex_count < 0:
        raise ValueError("vertex_count must be nonnegative")
    graph: list[list[tuple[int, int]]] = [[] for _ in range(vertex_count)]
    for edge_id, (left, right) in enumerate(edges):
        _validate_vertex(left, vertex_count, "edge endpoint")
        _validate_vertex(right, vertex_count, "edge endpoint")
        # Edge IDs distinguish parallel edges from the exact parent edge.
        graph[left].append((right, edge_id))
        graph[right].append((left, edge_id))

    entered = [-1] * vertex_count
    low = [0] * vertex_count
    timer = 0
    bridges: list[tuple[int, int]] = []

    def search(node: int, parent_edge: int = -1) -> None:
        nonlocal timer
        entered[node] = low[node] = timer
        timer += 1
        for neighbor, edge_id in graph[node]:
            if edge_id == parent_edge:
                continue
            if entered[neighbor] >= 0:
                # A back edge may connect this subtree to an ancestor.
                low[node] = min(low[node], entered[neighbor])
                continue
            search(neighbor, edge_id)
            low[node] = min(low[node], low[neighbor])
            if low[neighbor] > entered[node]:
                # The child subtree has no route around this tree edge.
                bridges.append((min(node, neighbor), max(node, neighbor)))

    for vertex in range(vertex_count):
        if entered[vertex] < 0:
            search(vertex)
    return sorted(bridges)

inline std::vector<std::pair<int, int>> find_bridges(
    int vertex_count, const std::vector<std::pair<int, int>>& edges) {
  if (vertex_count < 0) {
    throw std::invalid_argument("vertex_count must be nonnegative");
  }
  std::vector<std::vector<std::pair<int, int>>> graph(
      static_cast<std::size_t>(vertex_count));
  for (int id = 0; id < static_cast<int>(edges.size()); ++id) {
    const int left = edges[id].first;
    const int right = edges[id].second;
    validate_vertex(left, graph.size(), "edge endpoint");
    validate_vertex(right, graph.size(), "edge endpoint");
    // Edge IDs distinguish parallel edges from the exact parent edge.
    graph[left].push_back({right, id});
    graph[right].push_back({left, id});
  }
  std::vector<int> entered(vertex_count, -1);
  std::vector<int> low(vertex_count);
  std::vector<std::pair<int, int>> bridges;
  int timer = 0;
  std::function<void(int, int)> search = [&](int node, int parent_edge) {
    entered[node] = low[node] = timer++;
    for (const auto& edge : graph[node]) {
      const int neighbor = edge.first;
      const int edge_id = edge.second;
      if (edge_id == parent_edge) {
        continue;
      }
      if (entered[neighbor] >= 0) {
        // A back edge may connect this subtree to an ancestor.
        low[node] = std::min(low[node], entered[neighbor]);
        continue;
      }
      search(neighbor, edge_id);
      low[node] = std::min(low[node], low[neighbor]);
      if (low[neighbor] > entered[node]) {
        // The child subtree has no route around this tree edge.
        bridges.push_back(std::minmax(node, neighbor));
      }
    }
  };
  for (int node = 0; node < vertex_count; ++node) {
    if (entered[node] < 0) {
      search(node, -1);
    }
  }
  std::sort(bridges.begin(), bridges.end());
  return bridges;
}

inline std::vector<std::pair<int, int>> find_bridges(
    int vertex_count, const std::vector<std::pair<int, int>>& edges) {
  if (vertex_count < 0) {
    throw std::invalid_argument("vertex_count must be nonnegative");
  }
  std::vector<std::vector<std::pair<int, int>>> graph(
      static_cast<std::size_t>(vertex_count));
  for (int id = 0; id < static_cast<int>(edges.size()); ++id) {
    const int left = edges[id].first;
    const int right = edges[id].second;
    validate_vertex(left, graph.size(), "edge endpoint");
    validate_vertex(right, graph.size(), "edge endpoint");
    // Edge IDs distinguish parallel edges from the exact parent edge.
    graph[left].push_back({right, id});
    graph[right].push_back({left, id});
  }
  std::vector<int> entered(vertex_count, -1);
  std::vector<int> low(vertex_count);
  std::vector<std::pair<int, int>> bridges;
  int timer = 0;
  std::function<void(int, int)> search = [&](int node, int parent_edge) {
    entered[node] = low[node] = timer++;
    for (const auto& edge : graph[node]) {
      const int neighbor = edge.first;
      const int edge_id = edge.second;
      if (edge_id == parent_edge) {
        continue;
      }
      if (entered[neighbor] >= 0) {
        // A back edge may connect this subtree to an ancestor.
        low[node] = std::min(low[node], entered[neighbor]);
        continue;
      }
      search(neighbor, edge_id);
      low[node] = std::min(low[node], low[neighbor]);
      if (low[neighbor] > entered[node]) {
        // The child subtree has no route around this tree edge.
        bridges.push_back(std::minmax(node, neighbor));
      }
    }
  };
  for (int node = 0; node < vertex_count; ++node) {
    if (entered[node] < 0) {
      search(node, -1);
    }
  }
  std::sort(bridges.begin(), bridges.end());
  return bridges;
}

Why edge IDs are necessary

In a multigraph, two parallel edges connect the same endpoint pair. If DFS skips every edge back to the parent vertex, it skips the parallel return edge and may falsely report a bridge. Skip only the exact parent edge ID.

Complexity and boundary tests

  • Time: O(V + E).
  • Space: O(V + E) including adjacency.
  • Run DFS from every unvisited vertex; the graph may be disconnected.
  • Test one edge, a cycle, a tail attached to a cycle, parallel edges, and an isolated vertex.
  • Consider iterative DFS or explicit depth constraints for very deep inputs.

Practice

Articulation-point extraction is described here but is not yet exposed as a tested library function.