This post is completed by 2 users

  • 0
Add to List
Beginner

424. 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.

Output:

Given graph is not connected
Given graph is connected