Bredath First Search

BreadthFirstSearch.java

public class BreadthFirstSearch<K> {

    final Integer WHITE=0; //Not yet discovered
    final Integer GRAY=1;  //Discovered by not all adjacent vertices are discovered.
    final Integer BLACK=2; //Discovered and all adjacent vertices are discovered.

    HashMap<K,Integer> colour = new HashMap<K, Integer>();
    HashMap<K,Integer> distance = new HashMap<K, Integer>();
    HashMap<K, K> predecessor = new HashMap<K, K>();

    /**
     * @param graph Adjacency List of the graph
     * @param s Source vertex
     * @param d Destination vertex
     * @return HashMap[2] containing Distance and Predecessor. Search is not done through the entire graph, but
     * till the destination is reached. So the values for the unreached vertices will be wrong.
     */

    public <P extends K, Q extends ArrayList<P>> HashMap[] BFS(HashMap<P,Q> graph, P s, P d){
        Set keySet = graph.keySet();
        Iterator iterator = keySet.iterator();
        //Initialize
        while (iterator.hasNext()){
            P u = (P)iterator.next();
            if(u!=s){
                colour.put(u,WHITE);
                distance.put(u,Integer.MAX_VALUE);
                predecessor.put(u,null);
            }
        }
        colour.put(s,GRAY);
        distance.put(s,0);
        predecessor.put(s,null);
        LinkedList<P> queue = new LinkedList<P>();
        queue.push(s);
        while (!queue.isEmpty()){
            P u = (P)queue.removeFirst();
            ArrayList adjU= graph.get(u);
            for (int i = 0; i < adjU.size(); i++) {
                P adjVertex = (P)adjU.get(i);
                if(colour.get(adjVertex)==WHITE) {
                    colour.put(adjVertex,GRAY);
                    distance.put(adjVertex,distance.get(u)+1);
                    predecessor.put(adjVertex,u);
                    queue.push(adjVertex);
                    if(adjVertex==d){
                        HashMap[] returnValue = new HashMap[2];
                        returnValue[0] = distance;
                        returnValue[1] = predecessor;
                        return returnValue;
                    }
                }
            }
            colour.put(u,BLACK);
        }
        return null;
    }
}