Check if given undirected graph is connected or not

Objective: Given an undirected graph, write an algorithm to find out whether the graph is connected or not. 

Graph Connectivity: If each vertex of a graph is connected to one or multiple vertices then the graph is called a Connected graph whereas if there exists even one vertex which is not connected to any vertex of the graph then it is called Disconnect or not connected graph.

Example:

Approach: Use Depth-First Search (DFS)

Create a boolean visited [] array. Start DFS from any vertex and mark the visited vertices in the visited[] array. Once DFS is completed check the iterate the visited [] and count all the true’s. If this count is equal to no of vertices means all vertices are traveled during DFS implies graph is connected if the count is not equal to no of vertices implies all the vertices are not traveled means graph is not connected or disconnected.

Complete Code:

Output:

Given graph is not connected
Given graph is connected

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

%d bloggers like this: