|
This post is completed by 1 user
|
Add to List |
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 -----------------------------------------