2-Edge Connectivity in the graph

Given a undirected connected graph, check if the graph is 2-edge connected or not.

A connected graph is 2-edge-connected if it remains connected whenever any edges is removed. A bridge or cut arc is an edge of a graph whose deletion increases its number of connected components. i.e. whose removal disconnects the graph. So if any such bridge exists, the graph is not 2-edge-connected.

For example,
Below graph has 6 vertices and 3 bridges (highlighted in red)

  2 edge connected
 

Prerequisite:
Types of edges involved in DFS and relation between them
Arrival and Departure Time of Vertices in DFS


 

A simple approach is to remove each edge from the graph one by one and run DFS or BFS starting from any vertex. If the DFS or BFS covers all nodes in the graph, then the removed edge cannot be a bridge. If not, that edge is bridge. The time complexity of above solution is O(E(V + E)) where V is number of vertices and E is number of edges in the graph.

We can solve this problem efficiently in one pass of DFS. When we do a DFS from vertex v in an undirected graph, there could be edges which are going out of the sub tree i.e back edges. We can say that the graph is 2-edge connected if and only if for every edge u->v in the graph, there is at-least one back-edge that is going out of subtree rooted at v to some anscestor of u. When we say subtree rooted at v, we mean all v’s descendants including the vertex itself.

In other words, when we backtrack from a vertex v, we need to ensure that there is some back-edge from some descendent of v (including v) to some proper ancestor(parent or above) of v.

How should we modify DFS so that we can check if there is a back-edge going out of every sub tree?

We can modify DFS such that DFS(v) returns the smallest arrival time to which there is an back edge from the sub tree rooted at v. For example, let arrival(v) be the arrival time of vertex v in the DFS. Then if there is a back out of the sub tree rooted at v, it’s to something visited before v & therefore with a smaller arrival value. Remember for a back edge u -> v in a graph,

arrival[u] > arrival[v]

Suppose there are four edges going out of sub-tree rooted at v to vertex a, b, c and d and with arrival time arrival(a), arrival(b), arrival(c) and arrival(d) respectively. We look at their four arrival times & consider the smallest among them and that will be the value returned by DFS(v). i.e. DFS(v) returns min of arrival(a), arrival(b), arrival(c) and arrival(d). But before returning, we have to check that min (arrival(a), arrival(b), arrival(c), arrival(d)) is less than the arrival(v). If min (arrival(a), arrival(b), arrival(c), arrival(d)) is less than the arrival(v), then that means that at-least one back-edge is going out of the sub tree rooted at v. If not, we can say that (parent[v], v) is a bridge.

 
C++ implementation –
 

Download   Run Code

Output:

2, 1
3, 5
3, 5
0, 2

Please note that the same edges might end up printed twice. We can use a std::map avoid that with key as vertex number and value as std::set. i.e. std::map>.

Time complexity of above solution is O(n + m) where n is number of vertices and e is number of edges in the graph.

Reference: Dr. Naveen garg, IIT-D (Lecture – 28 Applications of DFS)
Image credits: http://mathworld.wolfram.com/GraphBridge.html

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz