An edge \(e = uv\) of a connected graph \(G\) is called a bridge if \(G - e\) is disconnected (obviously it increases the number of components)

Undirected graph

In the following undirected graph \(G\) the edges \(v_2v_3\) and \(v_3v_4\) are bridges

  • An edge \(e\) of an undirected graph \(G\) is a bridge if and only if \(e\) lies on no cycle of \(G\)
  • Every edge of an undirected tree is a bridge

Let \(G\) be an undirected graph, by analyzing the properties of the dfs tree we can determine if an edge is a bridge given the following facts:

  • let \(u\) and \(v\) be two vertices of the dfs such that \(u\) is an antecesor of \(v\), also \(u\) and \(v\) are not adjacent
    • if there's a back edge \(vu\) then none of the edges in the \(u-v\) path are bridges, if we remove one of them the graph is still connected because of this edge
    • otherwise the edge is a bridge

Implementation notes

  • to check if a succesor of a vertex \(u\) has a back edge to a predecessor of \(u\) an additional state is stored in each vertex which is the discovery time of the lowest back edge of a successor of \(u\) (by lowest back edge we mean the back edge to a vertex with the lowest discovery time) denoted as \(u_{back}\), initially this state is set to the discovery time of the vertex \(v\) i.e. \(u_{back} = u_{in}\), this state is propagated when the backtracking is performed
  • let \(uv\) be a back edge, when this edge is analyzed the \(v_{back}\) state needs to be updated to be the minimum between the existing \(v_{back}\) and the discovery time of \(u\), i.e. \(v_{back} = min(v_{back}, u_{in})\)
  • let \(v\) be an adjacent successor of \(u\) in the dfs tree, when we've finished analyzing the branch of the tree because of the \(uv\) edge we have to check if the \(v_{back}\) state contains a back edge to some predecessor of \(u\) (\(v_{back}\) is propagated) i.e. \(u_{in} > v_{back}\), if so then \(uv\) is not a bridge
int time_spent;

// the adjacency list representation of `G`
vector<vector<int> > g;
// the time a vertex `i` was discovered first
vector<int> time_in;
// stores the discovery time of the lowest predecessor that vertex `i`'s
// succesor vertices can reach **through a back edge**, initially
// the lowest predecessor is set to the vertex itself
vector<int> back;
// the bridges found during the dfs
vector<pair<int, int> > cut_edge;

void dfs(int v, int parent) {
  // the lowest back edge discovery time of `v` is
  // set to the discovery time of `v` initally
  back[v] = time_in[v] = ++time_spent;

  for (int i = 0; i < g[v].size(); i += 1) {
    int next = g[v][i];

    if (next == parent) {
      continue;
    }

    if (time_in[next] == -1) {
      dfs(next, v);
      // if there's a back edge between a descendant of `next` and
      // a predecessor of `v` then `next` will have a lower back edge discovery time
      // otherwise it's a bridge
      if (back[next] > time_in[v]) {
        cut_edge.push_back(pair<int, int> (v, next));
      }
      // propagation of the lowest back edge discovery time
      back[v] = min(back[v], back[next]);
    } else {
      // *back edge*
      // update the lowest back edge discovery time of `v`
      back[v] = min(back[v], time_in[next]);
    }
  }
}

/**
 * Finds the bridges in an undirected graph `G` of order `n` and size `m`
 *
 * Time complexity: O(n + m)
 * Space complexity: O(n)
 */
void bridges() {
  int n = g.size();
  time_spent = 0;
  time_in.assign(n, -1);
  back.assign(n, -1);
  cut_edge.clear();

  for (int i = 0; i < n; i += 1) {
    if (time_in[i] == -1) {
      dfs(i, -1);
    }
  }
}

Directed graph (strong bridges)

Let \(G\) be a directed graph, an edge \(uv \in E(G)\) is a strong bridge if its removal increases the number of stronly connected components of \(G\)

The following is a connected graph \(G\), every edge but \(v_2v_0\) is a strong bridge because removing it from \(G\) increases the number of strongly connected components, removing \(v_2v_0\) doesn't increase the number of strongly connected components so it's not a bridge

A trivial algorithm to find the strong bridges of a digraph \(G\) of order \(n\) and size \(m\) is as follows:

  • Compute the number of strongly connected componentes of \(G\) denoted as \(k(G)\)
  • For each edge \(e \in E(G)\)
    • remove \(e\) from \(G\)
    • compute the number of strongly connected components of \(G\) denoted as \(k(G - e)\)
    • if \(k(G) < k(G - e)\) then \(e\) is a bridge

The time complexity of the algorithm above is clearly \(O(m(n + m))\)

Let \(uv\) be an edge of a digraph \(G\), we say that \(uv\) is redundant if there's an alternative path from vertex \(u\) to vertex \(v\) avoiding \(uv\), otherwise we say that \(uv\) is not redundant, computing the strong bridges is equivalent to compute the non-redundant edges of a graph

http://www.sofsem.cz/sofsem12/files/presentations/Thursday/GiuseppeItaliano.pdf