Blog Archives

Bridges a.k.a. Cut Edges

iCode

Hey folks,
Today we are going to learn that how to compute the edges of importance or essential edges or bridges or cut edges. The bridges are very similar to articulation points that we discussed in the last post.

Bridges :
These are those edges which are essential for the graphs connectivity i.e. If I remove a bridge from the graph the rest of the graph will remain disconnected.

Now how to find the bridges in a graph
Naive’s Approach
remove edges one by one and do a DFS/BFS on the remaining graph if a single DFS/BFS results spanning the full graph than the edge was a waste and it was not a bridge otherwise it is a bridge.

PsuedoCode

Time Complexity : O(E*(V+E))

Better Approach
This approach highly resembles with the approach that we discussed to find the articulation points. Here we claim that in a DFS tree…

View original post 41 more words