Lab7q6.java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Lab7q6 {
    public static void main(String[] args) {
        // graph (undirected) given in adjacency matrix
        // check if its connected

        int[][] matrix = {
                {0, 0, 1, 0},
                {0, 0, 1, 1},
                {1, 1, 0, 0},
                {0, 1, 0, 0}
        };

//        int[][] matrix = {
//                {0, 0, 1, 0},
//                {0, 0, 0, 1},
//                {1, 0, 0, 0},
//                {0, 1, 0, 0}
//        };

        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        list = convertMatrixToList(matrix);

        int vertices = matrix.length;
        boolean[] visited =  new boolean[vertices];
        Queue<Integer> q = new LinkedList<>();
        q.add(0);

        while(!q.isEmpty()){
            int node = q.peek();
            q.remove();
            visited[node] = true;
            for(Integer element : list.get(node)){
                if(!visited[element]){
                    q.add(element);
                }
            }
        }

        boolean isConnected =true;
        for(int i = 0 ; i < vertices ; i++){
            if(!visited[i]){
                isConnected = false;
            }
        }

        if(isConnected){
            System.out.println("Graph is CONNECTED!!");
        }else{
            System.out.println("Graph is NOT CONNECTED");
        }

    }

    private static ArrayList<ArrayList<Integer>> convertMatrixToList(int[][] matrix) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        int vertices = matrix.length;

        for(int i = 0 ; i < vertices ; i++){
            list.add(new ArrayList<Integer>());
        }

        for(int i = 0 ; i < vertices ; i++){
            for(int j = 0 ; j < vertices ; j++){
                if(matrix[i][j] == 1 && i > j){
                    list.get(i).add(j);
                    list.get(j).add(i);
                }
            }
        }
        return list;
    }
}