Bipartite Graphs BFS

Bipartite Graphs OR Bigraphs is a graph whose vertices can be divided into two independent groups or sets so that for every edge in the graph, each end of the edge belongs to a separate group. There should not be any edge where both ends belong to the same set.


public class BipartiteGraph {

    public BipartiteGraph() {

    }

    void addEdge(ArrayList<ArrayList<Integer>> adj, int v, int u){
         adj.get(v).add(u);
         adj.get(u).add(v);
     }

    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for(int i=0;i<10;i++){
            adj.add(new ArrayList<>());
        }
        BipartiteGraph g = new BipartiteGraph();
        g.addEdge(adj,1, 2);
        g.addEdge(adj,2, 3);
        g.addEdge(adj,2, 8);
        g.addEdge(adj,3, 4);
        g.addEdge(adj,4, 6);
        g.addEdge(adj,5, 7);
        g.addEdge(adj,5, 9);
        g.addEdge(adj,8, 9);
     //   g.addEdge(adj,2, 4);

       if( g.BFS(1,adj)){
           System.out.println("Bipartite Graphs");
       }else{
           System.out.println("not Bipartite Graphs");
       }

    }

    boolean BFS(int v,ArrayList<ArrayList<Integer>> adj){
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(v);

        boolean[] visited = new boolean[adj.size()];
        int[] level = new int[adj.size()];
        level[v]=0;
        visited[v]=true;

        while (!queue.isEmpty()){
            v = queue.poll();
            //System.out.println(v);
            ArrayList<Integer> list = adj.get(v);
            Iterator<Integer> iterator = list.iterator();
            while (iterator.hasNext()){
                Integer i = iterator.next();
               // System.out.println("i is:"+i);
                if(!visited[i]){
                    level[i]=level[v]+1;
                    visited[i] = true;
                    queue.add(i);
                }
                else if (level[v]==level[i]){
                   return false;
                }
            }

        }
        return true;
    }

}

output:

Bipartite Graphs

if if add 2 to 4 in adjacent list then it will not Bipartite graph