Find bridges in graph

Given a direct graph, detect bridges in the graph.

An edge is called as bridge edge if 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
bridges in graph

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.
find bridges in a graph

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 i in an array low[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.
bridge edges 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