Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Bredath First Search
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment