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.

Example:

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:

Output:

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...

%d bloggers like this: