Bridges in a connected graph

by

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.

More Related Contents:

  1. Cycles in an Undirected Graph
  2. Millions of 3D points: How to find the 10 of them closest to a given point?
  3. Graph auto-layout algorithm
  4. Find connected components in a graph [closed]
  5. Finding all the shortest paths between two nodes in unweighted undirected graph
  6. Algorithm for “nice” grid line intervals on a graph
  7. How to implement depth first search for graph with a non-recursive approach
  8. Longest acyclic path in a directed unweighted graph
  9. help in the Donalds B. Johnson’s algorithm, i cannot understand the pseudo code (PART II)
  10. Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?
  11. What algorithm to use to determine minimum number of actions required to get the system to “Zero” state?
  12. Enumerating all paths in a directed acyclic graph
  13. How does Dijkstra’s Algorithm and A-Star compare?
  14. Find cycle of shortest length in a directed graph with positive weights
  15. graph – Dijkstra for The Single-Source Longest Path
  16. Planar Graph Layouts
  17. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  18. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  19. Finding connected components of adjacency matrix graph
  20. Complete graph with only two possible costs. What’s the shortest path’s cost from 0 to N – 1
  21. Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction)
  22. What is tail recursion?
  23. Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping
  24. How do you detect Credit card type based on number?
  25. How does finding a cycle start node in a cycle linked list work?
  26. How to efficiently build a tree from a flat structure?
  27. What would cause an algorithm to have O(log log n) complexity?
  28. Unbiased random number generator using a biased one
  29. maximum subarray of an array with integers [duplicate]
  30. CUDA stream compaction algorithm

Leave a Comment