Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction🤔
2.
Check If Removing a Given Edge Disconnects a Graph🎯
2.1.
Algorithm👨‍💻
2.2.
Implementation🦾
2.2.1.
Code in C++📄
2.2.2.
Code in Java📋
2.2.3.
Code in Python📋
3.
Frequently Asked Questions
3.1.
What is a graph data structure?
3.2.
What are the primary elements of a graph?
3.3.
What is the difference between a directed graph and an undirected graph?
3.4.
What are the types of data structures used for BFS vs DFS?
3.5.
Is a tree a graph?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check If Removing a Given Edge Disconnects a Graph

Author Sanchit Kumar
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction🤔

Sometimes, when dealing with graph data structure, we often witness an edge in a graph on removal, which disconnects the graph. But the question arises of how to check if removing a given edge disconnects a graph or not.

So, let us learn to check if removing a given edge disconnects a graph or not.

Check if removing a given edge disconnects a graph

Are you ready❓

Check out also Application of graph data structure

Check If Removing a Given Edge Disconnects a Graph🎯

An edge is a bridge in an undirected connected graph, if removed, disconnects the graph.

For example1🪢 - 

graph1

In the above graph, the bridge (highlighted with red) is between (0,4), which means 0 and 4.

For example2🪢 - 

graph2

In the above graph, the bridge (highlighted with red colour) is between (0,1), (1,2), and (2,3).
 

One way to check whether removing a given edge disconnects a graph is by determining whether or not a specific edge is a bridge.

We can always find if an undirected graph is connected or not by finding all reachable vertices from any vertex (say, the first vertex). The graph is connected if the count of reachable vertices equals the number of vertices in the graph. Else, it is disconnected. All the reachable vertices can be found either using the BFS or the DFS Algorithm.

Algorithm👨‍💻

Let us look at the algorithm

  1. Remove the given edge 
  2. Find all the reachable vertices from any vertex.
  3. If the count of reachable nodes is not V, return 'Yes'. Else return 'No' [not a bridge].

Implementation🦾

graph

In the above graph, we need to check if removing a given edge disconnects a graph using code implementation.

Code in C++📄

/*C++ program to check if removing a given edge disconnects a graph*/
 
#include<bits/stdc++.h>
using namespace std;
 
/* A directed graph using representation -> adjacency list */
class Graph{
	/* vertices*/
	int Vert; 
	list<int> *adj_adjacent;
	void DFS(int vert, bool visited[]);
	public:
	/* The constructor*/
	Graph(int Vert); 
 
	/*Add an edge to the graph using the function*/
	void add_an_edge(int vert, int next_vert);
 
	/* if graph is connected -> Returns true*/
	bool isConnected();
 
	bool isBridge(int vert_prev, int vert);
};
Graph::Graph(int Vert){
	this->Vert = Vert;
	adj_adjacent = new list<int>[Vert];
}
 
void Graph::add_an_edge(int vert_prev, int vert){	
	adj_adjacent[vert_prev].push_back(vert);
	adj_adjacent[vert].push_back(vert_prev);
}
 
void Graph::DFS(int vert, bool visited[]){
	/*Marking and printing the current node as visited*/
	visited[vert] = true;
 
	/* Recur for all the vertices adjacent to this vertex*/
	list<int>::iterator i;
 
	/* Loop*/
	for (i = adj_adjacent[vert].begin(); i != adj_adjacent[vert].end(); ++i)
		if (!visited[*i])
			DFS(*i, visited);
}
 
/* If a given graph is connected return true else return false*/
bool Graph::isConnected(){
	bool visited[Vert];
	memset(visited, false, sizeof(visited));
 
	/*Find all reachable vertices  from the first vertex*/
	DFS(0, visited);
 
	/*If the set of reachable vertices includes all, return true.*/
	for (int i=1; i<Vert; i++)
	if (visited[i] == false)
		return false;
 
	return true;
}
 
/* This function assumes that edge (vert_prev, vert) exists in graph*/
bool Graph::isBridge(int vert_prev, int vert){
	/* Remove edge from the undirected graph*/
	adj_adjacent[vert_prev].remove(vert);
	adj_adjacent[vert].remove(vert_prev);
 
	bool res = isConnected();
 
	/* Adding-> edge back*/
	add_an_edge(vert_prev, vert);
 
	/* Return true if graph gets disconnected after removing the edge.*/
	return (res == false);
}
 
/* Main code- the driver*/
int main(){
	/*Creating a graph as given above*/
	Graph g(5);
	g.add_an_edge(0, 1);
	g.add_an_edge(0, 3);
	g.add_an_edge(0, 4);
	g.add_an_edge(1, 2);
	g.add_an_edge(2, 3);
 
	cout << "\n Is there a bridge between (0,4)- ";
	g.isBridge(0, 4)? cout << "Yes" : cout << "No";
	cout << "\n";
	cout << "\n Is there a bridge between (1,2)- ";
	g.isBridge(1, 2)? cout << "Yes" : cout << "No";
	cout << "\n";
	return 0;
}


Output📋

Is there a bridge between (0,4)- Yes
Is there a bridge between (1,2)- No


Time Complexity🌐 - O(V + E) [Where V-vertices and E-edges in the graph]

Code in Java📋

/*Java program to Check if removing a given edge disconnects a graph*/

import java.util.*;

/*A directed graph Using representation -> adjacency list*/

class Graph {
	/*vertices*/
	int Vert;
	ArrayList<ArrayList<Integer> > adj;
	private void DFS(int vert, boolean[] visited){
		/*Marking and printing the current node as visited*/

		visited[vert] = true;
		/* Recur for all the vertices adjacent to this vertex*/

		for (Integer i : adj.get(vert)) {
			if (!visited[i]) {
				DFS(i, visited);
				
			}
			
		}
		
	}
	public Graph(int Vert){
		this.Vert = Vert;
		adj = new ArrayList<>();
		for (int i = 0; i < Vert; i++) {
			adj.add(new ArrayList<>());
			
		}
		
	}
	public void add_an_edge(int vert_prev, int vert){
		adj.get(vert_prev).add(vert);
		adj.get(vert).add(vert_prev);
		
	}
	/*Returns true if Given graph is connected else return false*/
	public boolean isConnected()
	{
		boolean[] visited = new boolean[Vert];
		/*Find all reachable vertices from the first vertex*/
		DFS(0, visited);
		
		/* return true. if the set of reachable vertices includes all*/
		
		for (int i = 1; i < Vert; i++)
		if (visited[i] == false)
		return false;
		return true;
	}
	
	/*Function assumes that edge (vert_prev, vert) exists in graph*/
	public boolean isBridge(int vert_prev, int vert){
		/* From undirected graph -> Remove edge*/
		adj.get(vert_prev).remove(Integer.valueOf(vert));
		adj.get(vert).remove(Integer.valueOf(vert_prev));

		boolean res = isConnected();

		/*Adding-> edge back*/
		add_an_edge(vert_prev, vert);

		/*Return true if graph gets disconnected after removing the edge.*/
		return (res == false);
		
	}
	/*Driver code*/
	public static void main(String[] args){
				
		/*Creating a graph as given above*/
		Graph g = new Graph(5);
		g.add_an_edge(0, 1);
		g.add_an_edge(0, 3);
		g.add_an_edge(0, 4);
		g.add_an_edge(1, 2);
		g.add_an_edge(2, 3);
	
		System.out.print("Is there a bridge between (0,4) - ");
		if (g.isBridge(0, 4)) {
		System.out.println("Yes");
		}
		else {
		System.out.println("No");
		}
		
		System.out.print("Is there a bridge between (1,2) - ");
		if (g.isBridge(1, 2)) {
		System.out.println("Yes");
		}
		else {
		System.out.println("No");
		}
	}
}


Output📋

Is there a bridge between (0,4) - Yes
Is there a bridge between (1,2) - No

Code in Python📋

# Python program to 
# check if removing 
# a given edge
# disconnects a graph

# A directed graph
# using representation
# -> adjacency list

class Graph:

	def __init__(self, Vert):
		self.Vert = Vert
		self.adj = [[] for i in range(Vert)]
	
	def add_an_edge(self, vert_prev, vert):
		self.adj[vert_prev].append(vert)
		self.adj[vert].append(vert_prev)
	
	def DFS(self, vert, visited):
		
		# Marking and printing
		# the current node
		# as visited
		visited[vert] = True
	
		# Recur for all 	
		# the vertices adjacent
		# to this vertex
		i = 0
		while i != len(self.adj[vert]):
			if (not visited[self.adj[vert][i]]):
				self.DFS(self.adj[vert][i], visited)
			i += 1
	
	# Returns true if 
	# the given graph
	# is connected
	# else return false
	def isConnected(self):
		visited = [False] * self.Vert
	
		# Find all reachable 
		# vertices from the 
		# first vertex
		self.DFS(0, visited)
	
		# If the set of 
		# reachable vertices
		# includes all
		# then return true.
		for i in range(1, self.Vert):
			if (visited[i] == False):
				return False
	
		return True

	# This function assumes
	# that edge (vert_prev, vert)
	# exists in the graph
	def isBridge(self, vert_prev, vert):
		
		# From undirected graph
		# -> remove edge 
		indU = self.adj[vert].index(vert_prev)
		indVert = self.adj[vert_prev].index(vert)
		del self.adj[vert_prev][indVert]
		del self.adj[vert][indU]
	
		res = self.isConnected()
	
		# Adding -> edge back
		self.add_an_edge(vert_prev, vert)
	
		# Return true if graph 
		# gets disconnected after 
		# removing the edge.
		return (res == False)

# Driver code
if __name__ == '__main__':

	# Creating the graph
	# as given above
	g = Graph(5)
	g.add_an_edge(0, 1);
	g.add_an_edge(0, 3);
	g.add_an_edge(0, 4);
	g.add_an_edge(1, 2);
	g.add_an_edge(2, 3);

	print("\n Is there a bridge between (0,4)- ")
	if g.isBridge(0, 4):
		print("Yes")
	else:
		print("No")
		
	print("\n Is there a bridge between (1,2)- ")
	if g.isBridge(1, 2):
		print("Yes")
	else:
		print("No")


Output📋

Is there a bridge between (0,4) - Yes
Is there a bridge between (1,2) - No


Now we have understood how to check if removing a given edge disconnects a graph or not.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is a graph data structure?

A non-linear data structure consisting of vertices and edges is called a graph.

What are the primary elements of a graph?

The primary elements of a graph are the vertices and the edges.

What is the difference between a directed graph and an undirected graph?

In a directed graph, the edges are assigned a specified direction. On the other hand, an undirected graph has no direction associated with its edges, allowing them to be traversed in any way.

What are the types of data structures used for BFS vs DFS?

The queue type data structure is used in the breadth-first search(BFS) to store nodes of different levels, and the stack type data structure is used in the depth-first search(DFS).

Is a tree a graph?

The tree is an undirected graph in which two vertices are connected by exactly one path or a connected acyclic undirected graph.

Conclusion

In this article, we discussed a scenario related to the bridge. We learnt how to check if removing a given edge disconnects a graph with code implementation in C++, Java and Python.

We believe this article on the check if removing a given edge disconnects a graph was helpful. You can refer to other similar articles as well - 

 

Recommended Problems:

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enrol in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Happy Learning Ninja! 🥷

Live masterclass