Check if given an edge is a bridge in the graph

Objective – Given a graph and an edge, write a program to check if the edge is a bridge.

Bridge in Graph: An edge is called a bridge if connects two subgraphs and removing the edge will disconnect the graph. 

In this article, we will take the Graph represented by Adjacency List.


Approach: Depth-First Search(DFS)

  • Do the DFS to count the number of connected components (If the graph is fully connected then count would be 1).
  • Remove the given edge.
  • Do the DFS again and count the number of connected components, if the count is the same then given edge is not a bridge. If count is increased by 1 then given edge is a bridge.

Complete Code:


Given Edge (0-1) is not a BRIDGE
Given Edge (3-4) is not a BRIDGE
Given Edge (2-3) is a BRIDGE

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: