Thursday, February 19, 2015

Checking if a given graph is Bipartite (BFS) JAVA

Algorithm:

1. Use a queue q.
2. Add any node to q.
3. For all those nodes that are connected to the current node polled from q, check if they have been assigned a color, if they have a color and it is the same as the current node, the graph is not bipartite and we need to stop the procedure else if they don't have any color add them to queue also (only if they have not been added previously [ use a boolean array or a HashSet for checking this ] ).
4. If the queue q is empty in the end it means that the given graph is bipartite.

Note: In case the graph is disjoint, we need to add all the given nodes to the queue and then check for all components connected to the current node popped from the queue.

Source:

import java.util.*;

public class BipartiteCheck {
    public static void main(String[] args) throws Exception{ 
        //Indices start from 1
            int graph[][] = {
                {0,0,0,0,0,0,0,0,0},
                {0,0,1,0,1,0,1,0,0},
                {0,1,0,1,0,1,0,0,0},
                {0,0,1,0,1,0,0,0,0},
                {0,1,0,1,0,1,0,0,0},
                {0,0,1,0,1,0,1,0,0},
                {0,1,0,0,0,1,0,1,0},
                {0,0,0,0,0,0,1,0,1},
                {0,0,0,0,0,0,0,1,0},
            };
            
            int[] color = new int[graph.length]; 
            color[1] = 1;
            
            Queue<Integer> q = new LinkedList<>();
            
            //Can also use a HashSet
            boolean checked[] = new boolean[graph[0].length];
            
            q.add(1); 
            
            boolean check = true;
            
            //In case the graph has disjoint nodes, add all of them to queue
            //This is the case when every node of the graph is reachable from every other node
            while(!q.isEmpty()){
                int node = q.poll(); 
//                System.out.println("Checking node "+node);
                for(int i=node+1;i<graph[0].length;++i){   
                    if(graph[node][i]==1){ 
//                        System.out.println("node "+node+" is connected to node "+i);
                        if(!checked[i]){ q.add(i); checked[i] = true;}
                        if(color[i] == color[node]){
                            check = false;
                            break;
                        } 
//                        System.out.println("Assigning color = "+(-color[node])+" to node "+i);
                        color[i] = -color[node]; 
                    }
                }
                if(!check)break;
            }
            System.out.println(Arrays.toString(color));
            if(check) System.out.println("Given graph is bipartite!");
            else System.out.println("Given graph is NOT bipartite!");
    }
}

Output:

[0, 1, -1, 1, -1, 1, -1, 1, -1]
Given graph is bipartite!

No comments:

Post a Comment