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
