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

Advertisements

About Khuram Ali

Programming... Programming and Programming...!!!

Posted on June 3, 2013, in Algorithms and tagged , . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: