Given an undirected graph, the task is to check if the given graph is connected or not using DFS.
A connected graph is a graph that is connected in the sense of a topological space, i.e., there is always a path from any node to any other node in the graph. A graph that is not connected is said to be disconnected.
Examples:
Input:
Output: Graph is connected
Input:
Output: Graph is disconnected
Approach:
- Take a boolean visited [] array.
- Start DFS(Depth First Search) from any of the vertexes and mark the visited vertices as True in the visited[] array.
- After completion of DFS check if all the vertices in the visited [] array is marked as True.
- If yes then the graph is connected, or else the graph is not connected or disconnected.
Code:
Java
// Java Program to check if // an undirected graph is connected or not// using DFS import java.util.*; public class checkConnectivity { // Graph class static class Graph{ int vertices; // Linked list for adjacency list of a vertex LinkedList<Integer> adjacencyList []; @SuppressWarnings("unchecked") public Graph(int vertices) { this.vertices = vertices; adjacencyList = new LinkedList[vertices]; for (int i = 0; i<vertices ; i++) { adjacencyList[i] = new LinkedList<>(); } } // Function for adding edges public void addEdge(int source, int dest) { adjacencyList.addFirst(dest); adjacencyList[dest].addFirst(source); } } // Function to check if the graph is connected or not public void isConnected(Graph graph){ int vertices = graph.vertices; LinkedList<Integer> adjacencyList [] = graph.adjacencyList; // Take a boolean visited array boolean[] visited = new boolean[vertices]; // Start the DFS from vertex 0 DFS(0, adjacencyList, visited); // Check if all the vertices are visited // Set connected to False if one node is unvisited boolean connected = true; for (int i = 0; i <visited.length ; i++) { if(!visited[i]){ connected = false; break; } } if(connected){ System.out.println("Graph is connected"); }else{ System.out.println("Graph is disconnected"); } } public void DFS(int source, LinkedList<Integer> adjacencyList [], boolean[] visited){ // Mark the vertex visited as True visited = true; // Travel the adjacent neighbours for (int i = 0; i <adjacencyList.size() ; i++) { int neighbour = adjacencyList.get(i); if(visited[neighbour]==false){ // Call DFS from neighbour DFS(neighbour, adjacencyList, visited); } } } // Driver code public static void main(String[] args) { // Given graph 1 Graph graph = new Graph(5); graph.addEdge(0,1); graph.addEdge(0,4); graph.addEdge(1,4); graph.addEdge(1,3); graph.addEdge(3,4); graph.addEdge(2,1); graph.addEdge(2,3); // Check if it's connected System.out.print("Graph 1:- "); checkConnectivity c = new checkConnectivity(); c.isConnected(graph); // Given graph 2 graph = new Graph(5); graph.addEdge(0,1); graph.addEdge(0,4); graph.addEdge(1,4); graph.addEdge(1,3); graph.addEdge(3,4); // Check if it's connected System.out.print("Graph 2:- "); c = new checkConnectivity(); c.isConnected(graph); }} |
Output
Graph 1:- Graph is connected Graph 2:- Graph is disconnected
