This post is completed by 1 user

  • 0
Add to List
Medium

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

Output:

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