Given a direct graph, detect bridges in the graph.

An edge is called as

bridge edgeif and only if on removal of that edge will increases number of components increase by one.

For example, in the below graphs, bridges are shown in green

The concept of detecting bridges in a graph will be useful in solving the Euler path or tour problem.

Depth First Search of graph can be used to see if graph is connected or not. We can use the same concept, one by one remove each edge and see if the graph is still connected using DFS. If yes, then the edge is not bridge edge, if not, then edge is **bridge edge**.

However, this method entails quite a complexity of `O(E * (V+E))` where `E` is number of edges and `V` is number of vertices.

Let’s think something better. Consider that we are looking at the edge (u,v) in a graph. In what condition, we can say that it is a bridge edge?

If we can somehow reach node `u` or any ancestor of `u` from any node which is a decedent of `v`, that means the graph is still connected and **(u,v)** is not a bridge edge. If the above condition is not possible, then **(u,v)** is the bridge.

How can we determine that there is no edge from decedent of `v` to `u` or its ancestor? For that we need to maintain time when a node was discovered during the depth-first search, call it ` tin[]`.

`tin[u]` is time when node `u` was discovered using DFS. If d[u] < d[v], means `u` was discovered before `v`.

Below is a graph with `tin[u]` filled for each node.

Now, figure out the lowest `tin[x]` which can be reached from each node. Reason to find that is to see if there is a node `x` which is reachable from children of `v` and has `tin[x]` less than `tin[u]`, i.e. `x` is ancestor of `u` reachable from children of `v`.

Store lowest DFS ancestor reachable from a node

iin an arraylow[u].

low[u] = min(low[u], low[v]) for edge (u,v)

Idea here is that if **(u,v)** is an edge, then either there is no back edge from subtree of `v` to `u` and ancestor of `u`.

If there is a back edge to `x` from subtree of `v`, then minimum `tin[x]` reached by node in subtree will be assigned to the `low[u]`.

The diagram shows the calculation of low[] in a graph.

Finally, if `low[v]` > `tin[u]` that means if discovery time of u is less than least ancestor that can be reached from subtree of `v`, we have a bridge, because there is no way we can reach to an ancestor of u once we disconnect edge (u,v).

Lots of theory, let’s code it. We will be modifying Depth First Search implementation to keep track of tin[] and low[].

### Bridges in a graph implementation

package AlgorithmsAndMe; import java.util.*; public class Bridges { Set<Integer> visited = new HashSet<>(); /* This map stores the time when the current node is visited */ Map<Integer, Integer> tin = new HashMap<>(); /* low will store minimum on tin[v] tin[p] for all p for which (v,p) is a back edge low[to] for all to for which (v,to) is a tree edge */ Map<Integer, Integer> low = new HashMap<>(); //To maintain monotonic increasing order. int timer; void dfs(Graph g, int u, int parent) { visited.add(u); //Put the current timer. tin.put(u, timer); //Low is the time of entry to start with low.put(u,timer); timer++; /* Go through all the neighbors */ for (int to : g.getNeighbors(u)) { //If it is parent, nothing to be done if (to == parent) continue; /* If the neighbor was already visited get the minimum of the neighbor entry time or the current low of the node. */ if (visited.contains(to)) { low.put(u, Math.min(low.getOrDefault(u, Integer.MAX_VALUE), tin.getOrDefault(to, Integer.MAX_VALUE))); } else { //Else do the DFS dfs(g, to, u); /* Normal edge scenario, take the minimum of low of the parent and the child. */ low.put(u, Math.min(low.getOrDefault(u, Integer.MAX_VALUE), low.getOrDefault(to, Integer.MAX_VALUE))); /* If low of the child node is less than time of entry of current node, then there is a bridge. */ if (low.get(to) > tin.get(u)) System.out.println(u + "->" + to); } } } public void findBridges(Graph g) { timer = 0; Iterator it = g.getNodes().iterator(); while(it.hasNext()){ int i = (int) it.next(); if (!visited.contains(i)) dfs(g, i, -1); } } }

The complexity of *finding bridges in a graph* is `O(V+E)` where `V` is number of vertices and `E` is number of edges in graph.

Problems you can solve using this concept:

796 – Critical Links