Is The Graph Connected or Not? (Implementation of BFS)

Today we are going to solve a very important problem of graph theory. It is to determine whether a given graph is connected or not. We use a very popular and important algorithm to solve this challenge called BFS(Breadth First Search) 

Problem Statement:

Given a graph with V nodes and E edges, we must find out whether it is connected or not.
From wikipedia: "A graph is connected when there is a path between every pair of vertices. In a connected graph, there are no unreachable vertices. A graph that is not connected is disconnected. A graph G is said to be disconnected if there exist two nodes in G such that no path in G has those nodes as endpoints."

Link To a Broader Description of Graph Connectivity

If you feel more comfortable learning the concept from a video, you can watch this youtube video:

BFS:

In order to solve this problem, we use BFS (Breadth First Search) algorithm. BFS is one of the most important and basic algorithms in graph theory.

Wikipedia link for BFS 

You can also watch this youtube video to understand the graph path finding algorithm more clearly.

Link to Youtube video 

I will take help of  the Java code for BFS provided in geeksforgeeks.com. You can see the code in their website in this link.

I hope you clearly understand graph connectivity and BFS algorithm now. If you do, we can proceed to the solution building section.

Solution Approach:

If the graph is connected, BFS will traverse the whole graph i.e. all the nodes in a graph will be visited. But what if we encounter a disconnected graph. Suppose we have a graph of 5 vertices numbered 1,2,3,4,5. We suppose 1,2 and 3 are connected (component no. 1) and 4 and 5 are connected (component no. 2). The 2 components are disconnected. In this case, if the BFS starts from 1/2/3 it'll only traverse component 1 and if   the BFS starts from 4/5 it'll only traverse component 2. 

So in the algorithm to determine connectivity, we traverse all the nodes in a loop and start BFS every time we find a non-visited node. This ensures we can reach all the components. Also starting BFS from every non-visited node in the loop means, we have encountered a new component. 

Complete Code Link 

In the code n is the number of vertices while m is the number of edges. The next m lines consists of u and v - the 2 vertices of edge (the edges are bidirectional here.). Vertices are number from 1 to n here.

Then we call the BFS function to determine the number of components / clusters. Here we have for loop from 1 to n referring to all the vertices. If we find a non-visited node , we have reached a new cluster and so we increment clusterNumber (number of components). This variable is returned to main and it's determined if it is equal to 1 or not. If it is 1, we have only one component meaning the graph is connected , otherwise, disconnected.