Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
How to Discover If a Given Graph is Biconnected or Not?
3.
Bridges in Graph
3.1.
How to Discover All Bridges in a Given Graph?
4.
Articulation Points 
4.1.
How to Discover All Articulation Points in a Given Diagram?
5.
Way to Write a C++ Program to Find if a Given Undirected Graph is Bi-Connected
6.
Frequently Asked Questions
6.1.
What do you mean by bi-connectivity in an undirected graph?
6.2.
What do you mean by a graph?
6.3.
What do you understand by a cyclic graph?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Bi-connectivity in Un-directed Graphs

Author Aditya kumar
0 upvote
Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

Introduction

An undirected graph is called Biconnected if there is a  two vertex – disjoint ways between any two vertices. In a Biconnected Graph, there is a basic cycle through any two vertices.

bi connectivity in undirected graphs

By show, two hubs associated by an edge structure a biconnected graph, however, this doesn’t check the above properties. For a chart with in excess of two vertices, the above properties must be there for it to be Bi-connected.

Or in other words/way we can say that:

A graph is supposed to be Biconnected if:

  • It is associated, for example, it is conceivable to arrive at each vertex from each other vertex, by a straightforward way.
  • Even in the wake of eliminating any vertex the chart stays associated.

How to Discover If a Given Graph is Biconnected or Not?

A connected graph is Biconnected in the event that it is associated and doesn’t have any Articulation Point. We mostly need to check two things in it.

  • It must be connected.
  • There isn’t an articulation point in it.

We start from any vertex and do DFS crossing. In DFS crossing, we check if there is an articulation point. On the off chance that we don’t discover any articulation point, at that point the diagram is Biconnected. At last, we have to check if all vertices were reachable in DFS. In the event that all vertices were not reachable, at that point the graph isn’t associated or connected.

Time Complexity: The above capacity is a straightforward DFS with extra arrays. So time intricacy is same as DFS which is O(V+E) for nearness list portrayal of it.

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

Bridges in Graph

An edge in an undirected connected graph is a scaffold if eliminating it disengages it. For a disengaged undirected graph, a definition is comparable, an extension is an edge eliminating which builds a number of detached segments.

Like Articulation Points, spans speak to weaknesses in an associated network and are helpful for planning dependable organisations. For instance, in a wired PC organisation, an explanation point shows the basic PCs and an extension demonstrates the basic wires or associations.

How to Discover All Bridges in a Given Graph?

A straightforward methodology is to individually eliminate all edges and check whether evacuation of an edge causes disengaged diagram. Following are steps of basic methodology for associated with it.

  • For each edge (u, v), do following
  • Remove (u, v) from a diagram
  • See if the diagram stays associated (We can either utilise BFS or DFS)
  • Add (u, v) back to the chart.

Time complexity of above method is O(E*(V+E)) if we are using the adjancy matrix.

We are going to do better this complexity, how?

The thought is like O(V+E) calculation for Articulation Points. We do DFS crossing of the given graph. In DFS tree an edge (u, v) (u is a parent of v in DFS tree) is connected if there doesn’t exist some other choice to arrive at u or a progenitor of u from subtree established with v. As examined in the past post, the worth low[v] demonstrates soonest visited vertex reachable from subtree established with v. The condition for an edge (u, v) to be a bridge is, “low[v] > disc[u]”.

Articulation Points 

A vertex in an undirected associated chart is an articulation point if disposing of it (and edges through it) isolates the graph. Explanation focuses speak to weaknesses in an associated network – single focus whose disappointment would part the organisation into at least 2 segments. They are helpful for planning dependable organisations.

For a confined undirected chart, an explanation point is a vertex taking out which grows number of associated portions.

How to Discover All Articulation Points in a Given Diagram?

A straightforward methodology is to individually eliminate all vertices and check whether the expulsion of a vertex causes disengaged diagram. Following are steps of basic methodology for the associated chart.

  • For each vertex v, do the following
  • Remove v from the graph
  • See if the diagram stays associated (We can either utilise BFS or DFS Algorithm)
  • Add v back to the graph

The time complexity of the above technique is O(V*(V+E)) for a chart spoke to utilising contiguousness list. Would we be able to improve?

An O(V+E) calculation to discover all Articulation Points (APs). The thought is to utilise DFS (Depth First Search). In DFS, we follow vertices in a tree structure called the DFS tree. In DFS tree, a vertex u is a parent of another vertex v if v is found by u (clearly v is nearby of u in the diagram). In DFS tree, a vertex u is the exclamation point in the event that one of the accompanying two conditions is valid.

  • u is the foundation of DFS tree and it has at any rate two kids.
  • u isn’t the foundation of DFS tree and it has a youngster v to such an extent that no vertex in subtree established with v has a back edge to one of the precursors (in DFS tree) of u.

Way to Write a C++ Program to Find if a Given Undirected Graph is Bi-Connected

#include <iostream>
#include <list>
#define NIL -1
using namespace std;

// A class for representing an undirected graph
class Graph
{
	// Number of vertices
	int V; 
	
	// A dynamic array for adjacency list
	list *adj; 
	
	public:
		// Constructor
		Graph(int V); 
		// to add an edge into the graph
		void addEdge(int v, int w); 
		// returns true if the graph is fully Biconnected
		bool isBC(); 
};

Graph::Graph(int V)
{
	this->V = V;
	adj = new list[V];
}

void Graph::addEdge(int v, int w)
{
	adj[v].push_back(w);
	// the graph is undirected
	adj[w].push_back(v); 
}

/* A recursive function is that returns true if there is an articulation point
   in given graph, otherwise it returns false. This function almost same as 
   isAPUtil() */

// u –> The vertex to be visited next in the graph

// visited[] –> keeps tract of visited vertices in graph

// disc[] –> Stores discovery times of visited vertices in graph

// parent[] –> Stores the parent vertices in DFS tree

/* A static variable that is used for simplicity, we can avoid use of static 
variable by passing the pointer. */

static int time = 0;

// Counts the children in DFS Tree 
int children = 0; 

// Marks the current node as visited in code
visited[u] = true; 

// Initialize the discovery time and low value 
disc[u] = low[u] = ++time; 

// Going through the all vertices adjacent to this 
list<int>::iterator i; 
for (i = adj[u].begin(); i != adj[u].end(); ++i) 
{ 
	// v is a current adjacent of u
    int v = *i;  

    //If v is not visited yet, then we make it a child of u in DFS tree and recursion for it
    if (!visited[v]) 
    { 
        children++; 
        parent[v] = u; 

    	// check if subgraph rooted with v has an articulation point in it  
        if(isBCUtil(v, visited, disc, low, parent))
        return true; 

        // Check the subtree rooted with v has a connection to one of ancestors of u
        low[u] = min(low[u], low[v]); 

        // u is articulation point in following case: 

        // (1) u is root of DFS tree and can have two or more children. 
        if (parent[u]  ==  NILL  &&  children > 1) 
        	return true; 

        /* (2) If u is not the root and low value of one of its child is more than the 
        discovery value of u. */
        if (parent[u] != NIL && low[v] >= disc[u]) 
        	return true; 
    } 

    // Update the low value of u for parent function call. 
    else if (v != parent[u]) 
    	low[u] = min(low[u], disc[v]); 
	} 
	return false; 
}

/* The function that returns true if graph is Biconnected, otherwise it is false. 
   It uses the recursion function isBCUtil() */
bool Graph::isBC()
{
	// Mark all the vertices as not visited in graph
	bool *visited = new bool[V];
	int *disc = new int[V];
	int *low = new int[V];
	int *parent = new int[V];
	
	// Initialising the parent and visited, and ap(articulation point) array
	For (int i=0; i<V; i++)
	{
		parent[j] = NIL;
		visited[j] = false;
	}
	
	/* Call the function recursive helper function to find if there is an 
	articulation point in given graph. We do the DFS traversal of graph 
	starring from vertex 0 */
	if ( isBCUtil (0, visited, disc, low,parent)==true)
		return false;
		
	/* Now check whether the given graph is connected or not in manner. 
	An undirected graph is connected if all vertices are reachable and also 
	from any starting point (we have taken this 0 as starting point) */
	for (int i=0; i<V; i++)
		if (visited[j] == false)
			return false;
	return true; 
}
// Main function program to test above function
int main()
{
	// Creating the graphs given in above diagrams
	Graph g1(2);
	g1.addEdge(0, 1);
	g1.isBC()? cout << “done\n” : cout << “Not\n”;
	Graph g2(5); 
	g2.addEdge(1, 0); 
	g2.addEdge(0, 2); 
	g2.addEdge(2, 1); 
	g2.addEdge(0, 3); 
	g2.addEdge(3, 4); 
	g2.addEdge(2, 4); 
	g2.isBC()? cout << "done\n" : cout << "Not\n"; 

	Graph g3(3); 
	g3.addEdge(0, 1); 
	g3.addEdge(1, 2); 
	g3.isBC()? cout << "done\n" : cout << "Not\n"; 

	Graph g4(5); 
	g4.addEdge(1, 0); 
	g4.addEdge(0, 2); 
	g4.addEdge(2, 1); 
	g4.addEdge(0, 3); 
	g4.addEdge(3, 4); 
	g4.isBC()? cout << "done\n" : cout << "Not\n"; 

	Graph g5(3); 
	g5.addEdge(0, 1); 
	g5.addEdge(1, 2); 
	g5.addEdge(2, 0); 
	g5.isBC()? cout << "done\n" : cout << "Not\n"; 

	return 0; 
}

Frequently Asked Questions

What do you mean by bi-connectivity in an undirected graph?

In an undirected graph, a vertex is biconnected if its removal does not disconnect the graph. A graph is biconnected if it has no articulation points. An articulation point is a vertex whose removal increases the number of connected components in a graph. In other words, an undirected graph is biconnected if there are two vertex-disjoint paths between any two vertices in the graph.

What do you mean by a graph?

A graph is a data structure that is used to model relationships between objects or entities. It is a collection of vertices, also known as nodes, and edges that connect these vertices. The edges can be directed or undirected, depending on whether they have a specific direction or not.

What do you understand by a cyclic graph?

A cyclic graph is a graph in which at least one cycle, or closed path, exists. This means that there is a sequence of edges that connects a set of vertices in such a way that the first and last vertices in the sequence are the same.

Conclusion

In this article, we have discussed bi-connectivity in undirected graph. We have also discussed its implementation in C++. You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScript, and many more! If you wish to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! 

But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Recommended Problems:

Previous article
Flood Fill Algorithm
Next article
Floyd Warshall Algorithm At a Glance
Live masterclass