Bridges in a connected graph

Question

I have a programming task(not homework.) where I have to find the bridges in a graph. I worked on it a bit myself, but could not come up with anything satisfactory. So i googled it , I did find something but I am unable to understand the algorithm as it is presented. Could someone please take a look at this code and give me an explanation.?

public Bridge(Graph G) {     low = new int[G.V()];     pre = new int[G.V()];     for (int v = 0; v < G.V(); v++) low[v] = -1;     for (int v = 0; v < G.V(); v++) pre[v] = -1;      for (int v = 0; v < G.V(); v++)         if (pre[v] == -1)             dfs(G, v, v); }  public int components() { return bridges + 1; }  private void dfs(Graph G, int u, int v) {     pre[v] = cnt++;     low[v] = pre[v];     for (int w : G.adj(v)) {         if (pre[w] == -1) {             dfs(G, v, w);             low[v] = Math.min(low[v], low[w]);             if (low[w] == pre[w]) {                 StdOut.println(v + "-" + w + " is a bridge");                 bridges++;             }         }          // update low number - ignore reverse of edge leading to v         else if (w != u)             low[v] = Math.min(low[v], pre[w]);     } } 

Answer 1

Def: Bridge is an edge, when removed, will disconnect the graph (or increase the number of connected components by 1).

One observation regarding bridges in graph; none of the edges that belong to a loop can be a bridge. So in a graph such as A--B--C--A, removing any of the edge A--B, B--C and C--A will not disconnect the graph. But, for an undirected graph, the edge A--B implies B--A; and this edge could still be a bridge, where the only loop it is in is A--B--A. So, we should consider only those loops formed by a back edge. This is where the parent information you've passed in the function argument helps. It will help you to not use the loops such as A--B--A.

Now to identify the back edge (or the loop), A--B--C--A we use the low and pre arrays. The array pre is like the visited array in the dfs algorithm; but instead of just flagging that the vertex as visited, we identify each vertex with a different number (according to its position in the dfs tree). The low array helps to identify if there is a loop. The low array identifies the lowest numbered (from pre array) vertex that the current vertex can reach.

Lets work through this graph A--B--C--D--B.

Starting at A

dfs:   ^                 ^                 ^                 ^              ^ pre:   0 -1 -1 -1 -1  0--1 -1 -1  1  0--1--2 -1  1  0--1--2--3  1  0--1--2--3--1 graph: A--B--C--D--B  A--B--C--D--B  A--B--C--D--B  A--B--C--D--B  A--B--C--D--B low:   0 -1 -1 -1 -1  0--1 -1 -1  1  0--1--2 -1  1  0--1--2--3  1  0--1--2--3->1 

At this point, you've encountered a cycle/loop in graph. In your code if (pre[w] == -1) will be false this time. So, you'll enter the else part. The if statement there is checking if B is the parent vertex of D. It is not, so D will absorb B's pre value into low. Continuing the example,

dfs:            ^ pre:   0--1--2--3 graph: A--B--C--D low:   0--1--2--1    

This low value of D propagates back to C through the code low[v] = Math.min(low[v], low[w]);.

dfs:         ^           ^           ^ pre:   0--1--2--3--1  0--1--2--3--1  0--1--2--3--1 graph: A--B--C--D--B  A--B--C--D--B  A--B--C--D--B low:   0--1--1--1--1  0--1--1--1--1  0--1--1--1--1 

Now, that the cycle/loop is identified, we note that the vertex A is not part of the loop. So, you print out A--B as a bridge. The code low['B'] == pre['B'] means an edge to B will be a bridge. This is because, the lowest vertex we can reach from B is B itself.

Hope this explanation helps.

Answer 2

Not a new answer, but I needed this in Python. Here's a translation of the algorithm for an undirected NetworkX Graph object G:

def bridge_dfs(G,u,v,cnt,low,pre,bridges):     cnt    += 1     pre[v]  = cnt     low[v]  = pre[v]      for w in nx.neighbors(G,v):         if (pre[w] == -1):             bridge_dfs(G,v,w,cnt,low,pre,bridges)              low[v] = min(low[v], low[w])             if (low[w] == pre[w]):                 bridges.append((v,w))          elif (w != u):             low[v] = min(low[v], pre[w])  def get_bridges(G):     bridges = []     cnt     = 0     low     = {n:-1 for n in G.nodes()}     pre     = low.copy()      for n in G.nodes():          bridge_dfs(G, n, n, cnt, low, pre, bridges)      return bridges # <- List of (node-node) tuples for all bridges in G 

Be careful of Python's recursion depth limiter for large graphs...